Abstract
We prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies superlinear lower bounds for multitape 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 [Valiant, 1977]. While rigidity was originally defined for matrices, or, equivalently, for (multioutput) linear functions, we extend and study both rigidity and block rigidity for general (multioutput) functions. Using techniques of Paul, Pippenger, Szemerédi and Trotter [Paul et al., 1983], we show that a blockrigid function cannot be computed by multitape Turing machines that run in linear (or slightly superlinear) time, even in the nonuniform 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 blockrigid 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^Ω(n), where n is the number of repetitions.
As another application of block rigidity, we show conditional sizedepth tradeoffs for boolean circuits, where the gates compute arbitrary functions over large sets.
BibTeX  Entry
@InProceedings{mittal_et_al:LIPIcs.ITCS.2021.71,
author = {Kunal Mittal and Ran Raz},
title = {{Block Rigidity: Strong Multiplayer Parallel Repetition Implies SuperLinear Lower Bounds for Turing Machines}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {71:171:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13610},
URN = {urn:nbn:de:0030drops136101},
doi = {10.4230/LIPIcs.ITCS.2021.71},
annote = {Keywords: Blockrigidity, Matrix Rigidity, Parallel Repetition, Sizedepth tradeoffs, Turing Machines}
}
Keywords: 

Blockrigidity, Matrix Rigidity, Parallel Repetition, Sizedepth tradeoffs, Turing Machines 
Collection: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021) 
Issue Date: 

2021 
Date of publication: 

04.02.2021 