  We introduce and study q-randomized Robinson-Schensted-Knuth (RSK)
correspondences which interpolate between the classical (q=0) and geometric
(q->1) RSK correspondences (the latter ones are sometimes also called
tropical).
  For 0<q<1 our correspondences are randomized, i.e., the result of an
insertion is a certain probability distribution on semistandard Young tableaux.
Because of this randomness, we use the language of discrete time Markov
dynamics on two-dimensional interlacing particle arrays (these arrays are in a
natural bijection with semistandard tableaux). Our dynamics act nicely on a
certain class of probability measures on arrays, namely, on q-Whittaker
processes (which are t=0 versions of Macdonald processes). We present four
Markov dynamics which for q=0 reduce to the classical row or column RSK
correspondences applied to a random input matrix with independent geometric or
Bernoulli entries.
  Our new two-dimensional discrete time dynamics generalize and extend several
known constructions: (1) The discrete time q-TASEPs arise as one-dimensional
marginals of our "column" dynamics. In a similar way, our "row" dynamics lead
to discrete time q-PushTASEPs - new integrable particle systems in the
Kardar-Parisi-Zhang universality class. We employ these new one-dimensional
discrete time systems to establish a Fredholm determinantal formula for the
two-sided continuous time q-PushASEP conjectured by Corwin-Petrov (2013). (2)
In a certain Poisson-type limit (from discrete to continuous time), our
two-dimensional dynamics reduce to the q-randomized column and row
Robinson-Schensted correspondences introduced by O'Connell-Pei (2012) and
Borodin-Petrov (2013), respectively. (3) In a scaling limit as q->1, two of our
four dynamics on interlacing arrays turn into the geometric RSK correspondences
associated with log-Gamma or strict-weak directed random polymers.
