  We prove that a sufficiently strong parallel repetition theorem for a special
case of multiplayer (multiprover) games implies super-linear lower bounds for
multi-tape Turing machines with advice. To the best of our knowledge, this is
the first connection between parallel repetition and lower bounds for time
complexity and the first major potential implication of a parallel repetition
theorem with more than two players.
  Along the way to proving this result, we define and initiate a study of block
rigidity, a weakening of Valiant's notion of rigidity. While rigidity was
originally defined for matrices, or, equivalently, for (multi-output) linear
functions, we extend and study both rigidity and block rigidity for general
(multi-output) functions. Using techniques of Paul, Pippenger, Szemer\'edi and
Trotter, we show that a block-rigid function cannot be computed by multi-tape
Turing machines that run in linear (or slightly super-linear) time, even in the
non-uniform setting, where the machine gets an arbitrary advice tape.
  We then describe a class of multiplayer games, such that, a sufficiently
strong parallel repetition theorem for that class of games implies an explicit
block-rigid function. The games in that class have the following property that
may be of independent interest: for every random string for the verifier
(which, in particular, determines the vector of queries to the players), there
is a unique correct answer for each of the players, and the verifier accepts if
and only if all answers are correct. We refer to such games as independent
games. The theorem that we need is that parallel repetition reduces the value
of games in this class from $v$ to $v^{\Omega(n)}$, where $n$ is the number of
repetitions.
  As another application of block rigidity, we show conditional size-depth
tradeoffs for boolean circuits, where the gates compute arbitrary functions
over large sets.
