Document Open Access Logo

Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines

Authors Kunal Mittal, Ran Raz

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.71.pdf
  • Filesize: 452 kB
  • 15 pages

Document Identifiers

Author Details

Kunal Mittal
  • Department of Computer Science, Princeton University, NJ, USA
Ran Raz
  • Department of Computer Science, Princeton University, NJ, USA

Funding

Research supported by the Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462.

Cite As Get BibTex

Kunal Mittal and Ran Raz. Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 71:1-71:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.71

Abstract

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 [Valiant, 1977]. 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 [Paul et al., 1983], 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • Block-rigidity
  • Matrix Rigidity
  • Parallel Repetition
  • Size-depth tradeoffs
  • Turing Machines

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Josh Alman and Lijie Chen. Efficient construction of rigid matrices using an NP oracle. In FOCS, pages 1034-1055, 2019. Google Scholar
  2. Josh Alman and Ryan Williams. Probabilistic rank and matrix rigidity. In STOC, pages 641-652, 2017. Google Scholar
  3. Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In STOC, pages 113-131, 1988. Google Scholar
  4. Amey Bhangale, Prahladh Harsha, Orr Paradise, and Avishay Tal. Rigid matrices from rectangular PCPs. In FOCS, 2020. accepted. Google Scholar
  5. Mark Braverman and Ankit Garg. Small value parallel repetition for general games. In STOC, pages 335-340, 2015. Google Scholar
  6. Martin Dietzfelbinger, Wolfgang Maass, and Georg Schnitger. The complexity of matrix transposition on one-tape off-line Turing machines. Theoret. Comput. Sci., 82:113-129, 1991. Google Scholar
  7. Irit Dinur, Prahladh Harsha, Rakesh Venkat, and Henry Yuen. Multiplayer parallel repetition for expanding games. In ITCS, volume 67 of LIPIcs, pages Art. No. 37, 16, 2017. Google Scholar
  8. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In STOC, pages 624-633, 2014. Google Scholar
  9. Zeev Dvir, Alexander Golovnev, and Omri Weinstein. Static data structure lower bounds imply rigidity. In STOC, pages 967-978, 2019. Google Scholar
  10. Uriel Feige. On the success probability of the two provers in one-round proof systems. In Structure in Complexity Theory Conference, pages 116-123, 1991. Google Scholar
  11. Uriel Feige and Oleg Verbitsky. Error reduction by parallel repetition - a negative result. Combinatorica, 22(4):461-478, 2002. Google Scholar
  12. Lance Fortnow, Richard Lipton, Dieter van Melkebeek, and Anastasios Viglas. Time-space lower bounds for satisfiability. J. ACM, 52(6):835-865, 2005. Google Scholar
  13. Lance Fortnow, John Rompel, and Michael Sipser. On the power of multi-prover interactive protocols. Theoret. Comput. Sci., 134(2):545-557, 1994. Google Scholar
  14. Lance Jeremy Fortnow. Complexity theoretic aspects of interactive proof systems. PhD thesis, MIT, 1989. Google Scholar
  15. Joel Friedman. A note on matrix rigidity. Combinatorica, 13(2):235-239, 1993. Google Scholar
  16. H. Furstenberg and Y. Katznelson. A density version of the Hales-Jewett theorem. J. Anal. Math., 57:64-119, 1991. Google Scholar
  17. Oded Goldreich and Avishay Tal. Matrix rigidity of random Toeplitz matrices. Comput. Complexity, 27(2):305-350, 2018. (also in STOC 2016). Google Scholar
  18. J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms. Trans. Amer. Math. Soc., 117:285-306, 1965. Google Scholar
  19. Thomas Holenstein. Parallel repetition: simplifications and the no-signaling case. Theory Comput., 5:141-172, 2009. (also in STOC 2007). Google Scholar
  20. John Hopcroft, Wolfgang Paul, and Leslie Valiant. On time versus space. J. Assoc. Comput. Mach., 24(2):332-337, 1977. (also in FOCS 1975). Google Scholar
  21. Stasys Jukna and Georg Schnitger. Min-rank conjecture for log-depth circuits. J. Comput. System Sci., 77(6):1023-1038, 2011. Google Scholar
  22. Kiran S. Kedlaya and Christopher Umans. Fast polynomial factorization and modular composition. SIAM J. Comput., 40(6):1767-1802, 2011. (also in STOC 2008). Google Scholar
  23. Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, and M. N. Jayalal Sarma. Using elimination theory to construct rigid matrices. Comput. Complexity, 23(4):531-563, 2014. (also in FSTTCS 2009). Google Scholar
  24. Satyanarayana V. Lokam. On the rigidity of Vandermonde matrices. Theoret. Comput. Sci., 237(1-2):477-483, 2000. Google Scholar
  25. Satyanarayana V. Lokam. Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity. J. Comput. System Sci., 63(3):449-473, 2001. Google Scholar
  26. Satyanarayana V. Lokam. Quadratic lower bounds on matrix rigidity. In Theory and Applications of Models of Computation, pages 295-307, 2006. Google Scholar
  27. Wolfgang Paul and Rüdiger Reischuk. On alternation. II. A graph-theoretic approach to determinism versus nondeterminism. Acta Inform., 14(4):391-403, 1980. Google Scholar
  28. Wolfgang J. Paul, Nicholas Pippenger, Endre Szemeredi, and William T. Trotter. On determinism versus non-determinism and related problems. In FOCS, pages 429-438, 1983. Google Scholar
  29. D. H. J. Polymath. A new proof of the density Hales-Jewett theorem. Ann. of Math. (2), 175(3):1283-1327, 2012. Google Scholar
  30. Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. (also in STOC 1995). Google Scholar
  31. Ran Raz. A counterexample to strong parallel repetition. SIAM J. Comput., 40(3):771-777, 2011. (also in FOCS 2008). Google Scholar
  32. Alexander Razborov. On rigid matrices (in russian). Unpublished Manuscript, 1989. Google Scholar
  33. Rahul Santhanam. On separators, segregators and time versus space. In CCC, pages 286-294, 2001. Google Scholar
  34. M. A. Shokrollahi, D. A. Spielman, and V. Stemann. A remark on matrix rigidity. Inform. Process. Lett., 64(6):283-285, 1997. Google Scholar
  35. Victor Shoup and Roman Smolensky. Lower bounds for polynomial evaluation and interpolation problems. Comput. Complexity, 6(4):301-311, 1996/97. Google Scholar
  36. Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In MFCS, volume 53 of Lecture Notes in Computer Science, pages 162-176, 1977. Google Scholar
  37. Dieter van Melkebeek and Ran Raz. A time lower bound for satisfiability. Theoret. Comput. Sci., 348(2-3):311-320, 2005. (also in ICALP 2004). Google Scholar
  38. Oleg Verbitsky. Towards the parallel repetition conjecture. Theoret. Comput. Sci., 157(2):277-282, 1996. Google Scholar
  39. Henning Wunderlich. On a theorem of Razborov. Comput. Complexity, 21(3):431-477, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact