论文标题
块刚度：强大的多人平行重复重复意味着图灵机的超级线性下限
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines
论文作者
论文摘要
我们证明，对于多人游戏（Multiprover）游戏的特殊情况，一个足够强大的并行重复定理意味着带有建议的多磁带图灵机的超级线性下限。据我们所知，这是时间复杂性的平行重复与下限之间的第一个联系，以及与超过两个播放器的平行重复定理的第一个主要潜在含义。 在证明这一结果的过程中，我们定义并启动了一项研究块刚度的研究，这是Valiant刚性概念的减弱。虽然最初针对矩阵定义了刚性，或者（多输出）线性函数等效地定义了刚性，但我们扩展和研究一般（多输出）函数的刚度和阻断刚度。使用Paul，Pippenger，Szemerédi和Trotter的技术，我们表明无法通过以线性（或稍微超级线性）时间运行的多磁带Turing机器来计算一个块状函数，即使在不均匀的设置中，该机器会获得任意建议胶带。 然后，我们描述了一类多人游戏，这样，该类别的游戏具有足够强的并行重复定理，这意味着明确的块状函数。该课程中的游戏具有以下属性可能具有独立关注的属性：对于验证者的每个随机字符串（尤其是确定对玩家的查询向量），每个播放器都有一个唯一的正确答案，而验证者才能在所有答案都是正确的情况下接受且仅在所有答案时接受。我们指的是独立游戏等游戏。我们需要的定理是，并行重复将游戏中的游戏值从$ v $减少到$ v^{ω（n）} $，其中$ n $是重复的数量。 作为块刚度的另一种应用，我们显示了布尔电路的条件大小深度折衷，其中大门在大集合上计算任意功能。
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édi 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^{Ω(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.
