Abstract
We construct a PCP for NTIME(2n) with constant soundness, 2n poly(n) proof length, and poly(n) queries where the verifier’s computation is simple: the queries are a projection of the input randomness, and the computation on the prover’s answers is a 3CNF. The previous upper bound for these two computations was polynomial-size circuits. Composing this verifier with a proof oracle increases the circuit-depth of the latter by 2. Our PCP is a simple variant of the PCP by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (CCC 2005). We also give a more modular exposition of the latter, separating the combinatorial from the algebraic arguments.
If our PCP is taken as a black box, we obtain a more direct proof of the result by Williams, later with Santhanam (CCC 2013) that derandomizing circuits on n bits from a class C in time 2n/n ω(1) yields that NEXP is not in a related circuit class C′. Our proof yields a tighter connection: C is an And-Or of circuits from C′. Along the way we show that the same lower bound follows if the satisfiability of the And of any 3 circuits from C′ can be solved in time 2n/n ω(1).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Constraint Satisfaction Problem
- Satisfying Assignment
- Probabilistic Polynomial Time
- Parity Gate
- Probabilistically Checkable Proof
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms 3(3), 289–304 (1992)
Alon, N., Spencer, J.H., Erdős, P.: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley and Sons, Inc. (1992)
Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. In: ACM Innovations in Theoretical Computer Science Conf. (ITCS), pp. 401–414 (2013)
Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete efficiency of probabilistically-checkable proofs. In: ACM Symp. on the Theory of Computing (STOC), pp. 585–594 (2013)
Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Short PCPs verifiable in polylogarithmic time. In: IEEE Conf. on Computational Complexity (CCC), pp. 120–134 (2005)
Blum, N.: A boolean function requiring 3n network size. Theoretical Computer Science 28, 337–345 (1984)
Ben-Sasson, E., Sudan, M.: Short PCPs with polylog query complexity. SIAM J. on Computing 38(2), 551–607 (2008)
Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. on Computing 36(4), 889–974 (2006)
Cook, S.A.: A hierarchy for nondeterministic time complexity. J. of Computer and System Sciences 7(4), 343–353 (1973)
Dinur, I.: The PCP theorem by gap amplification. J. of the ACM 54(3), 12 (2007)
Demenkov, E., Kulikov, A.S.: An elementary proof of a 3n − o(n) lower bound on the circuit complexity of affine dispersers. In: Symp. on Math. Foundations of Computer Science (MFCS), pp. 256–265 (2011)
Dinur, I., Reingold, O.: Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM J. on Computing 36(4), 975–1024 (2006)
Fefferman, B., Shaltiel, R., Umans, C., Viola, E.: On beating the hybrid argument. Theory of Computing 9, 809–843 (2013)
Gopalan, P., Meka, R., Reingold, O.: DNF sparsification and a faster deterministic counting algorithm. Computational Complexity 22(2), 275–310 (2013)
Hertli, T.: 3-SAT faster and simpler - unique-SAT bounds for PPSZ hold in general. In: IEEE Symp. on Foundations of Computer Science (FOCS), pp. 277–284 (2011)
Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: Exponential time vs. probabilistic polynomial time. In: IEEE Conf. on Computational Complexity (CCC) (2001)
Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: exponential time vs. probabilistic polynomial time. J. of Computer and System Sciences 65(4), 672–694 (2002)
Jahanjou, H., Miles, E., Viola, E.: Local reductions (2013), http://www.ccs.neu.edu/home/viola/
Karp, R.M., Lipton, R.J.: Some connections between nonuniform and uniform complexity classes. In: ACM Symp. on the Theory of Computing (STOC), pp. 302–309 (1980)
Luby, M., Veličković, B., Wigderson, A.: Deterministic approximate counting of depth-2 circuits. In: 2nd Israeli Symposium on Theoretical Computer Science (ISTCS), pp. 18–24 (1993)
Mie, T.: Short pcpps verifiable in polylogarithmic time with o(1) queries. Ann. Math. Artif. Intell. 56(3-4), 313–338 (2009)
Makino, K., Tamaki, S., Yamamoto, M.: Derandomizing HSSW algorithm for 3-SAT. CoRR, abs/1102.3766 (2011)
NEU. From RAM to SAT (2012), http://www.ccs.neu.edu/home/viola/
Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. In: 22nd ACM Symp. on the Theory of Computing (STOC), pp. 213–223. ACM (1990)
Oliveira, I.C.: Algorithms versus circuit lower bounds. CoRR, abs/1309.0249 (2013)
Seiferas, J.I., Fischer, M.J., Meyer, A.R.: Separating nondeterministic time complexity classes. J. of the ACM 25(1), 146–167 (1978)
Santhanam, R., Williams, R.: On medium-uniformity and circuit lower bounds. In: IEEE Conf. on Computational Complexity (CCC) (2013)
Viola, E.: Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM J. on Computing 36(5), 1387–1403 (2007)
Viola, E.: Challenges in computational lower bounds (2013), http://www.ccs.neu.edu/home/viola/
Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science 348(2-3), 357–365 (2005)
Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: 42nd ACM Symp. on the Theory of Computing (STOC), pp. 231–240 (2010)
Williams, R.: Non-uniform ACC circuit lower bounds. In: IEEE Conf. on Computational Complexity (CCC), pp. 115–125 (2011)
Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. SIAM J. on Computing 42(3), 1218–1244 (2013)
Williams, R.: New algorithms and lower bounds for circuits with linear threshold gates. In: ACM Symp. on the Theory of Computing, STOC (2014)
Zák, S.: A turing machine time hierarchy. Theoretical Computer Science 26, 327–333 (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ben-Sasson, E., Viola, E. (2014). Short PCPs with Projection Queries. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43948-7_14
Download citation
DOI: https://doi.org/10.1007/978-3-662-43948-7_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43947-0
Online ISBN: 978-3-662-43948-7
eBook Packages: Computer ScienceComputer Science (R0)