Abstract
Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (\({\mathcal {MAP}}\)), the verifier receives, in addition to query access to the input, also free access to an explicitly given short (sub-linear) proof. A more general notion is that of an interactive proof of proximity (\({\mathcal {IPP}}\)), in which the verifier is allowed to interact with an all-powerful, yet untrusted, prover. \({\mathcal {MAP}}\)s and \({\mathcal {IPP}}\)s may be thought of as the \({\mathcal {NP}}\) and \({\mathcal {IP}}\) analogues of property testing, respectively.
In this work we construct proofs of proximity for two natural classes of properties: (1) context-free languages, and (2) languages accepted by small read-once branching programs. Our main results are:
-
1.
\({\mathcal {MAP}}\)s for these two classes, in which, for inputs of length \(n\), both the verifier’s query complexity and the length of the \({\mathcal {MAP}}\) proof are \(\widetilde{O}(\sqrt{n})\).
-
2.
\({\mathcal {IPP}}\)s for the same two classes with constant query complexity, poly-logarithmic communication complexity, and logarithmically many rounds of interaction.
Full version can be found in ECCC TR15-024 [GGR15].
This research was partially supported by the Israel Science Foundation (grant No. 671/13).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Krivelevich, M., Newman, I., Szegedy, M.: Regular languages are testable with a constant number of queries. SIAM J. Comput. 30(6), 1842–1862 (2000)
Bollig, B.: Property testing and the branching program size of boolean functions. In: Liśkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 258–269. Springer, Heidelberg (2005)
Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput. 36(4), 889–974 (2006)
Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151–158. ACM (1971)
Dinur, I., Reingold, O.: Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM J. Comput. 36(4), 975–1024 (2006)
Ergün, F., Kumar, R., Rubinfeld, R.: Fast approximate probabilistically checkable proofs. Inf. Comput. 189(2), 135–159 (2004)
Fischer, E., Goldhirsh, Y., Lachish, O.: Partial tests, universal tests and decomposability. In: Innovations in Theoretical Computer Science, ITCS 2014, Princeton, NJ, USA, January 12–14, pp. 483–500 (2014)
Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM (JACM) 45(4), 653–750 (1998)
Goldreich, O., Gur, T., Rothblum, R.D.: Proofs of proximity for context-free languages and read-once branching programs. Electronic Colloquium on Computational Complexity (ECCC) 22, 24 (2015)
Goldreich, O., Ron, D.: On proximity-oblivious testing. SIAM Journal on Computing 40(2), 534–566 (2011)
Gur, T., Rothblum, R.D.: Non-interactive proofs of proximity. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, pp. 133–142. ACM (2015)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley Longman Publishing Co. Inc., Boston (2006)
Tauman Kalai, Y., Rothblum, R.D.: Arguments of proximity (2014) (manuscript)
Kriegel, K., Waack, S.: Lower bounds on the complexity of real-time branching programs. ITA 22(4), 447–459 (1988)
Lewis, P.M., Stearns, R.E., Hartmanis, J.: Memory bounds for recognition of context-free and context-sensitive languages. In: SWCT (FOCS), pp. 191–202 (1965)
Newman, I.: Testing membership in languages that have small width branching programs. SIAM Journal on Computing 31(5), 1557–1570 (2002)
Parnas, M., Ron, D., Rubinfeld, R.: Testing parenthesis languages. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM-APPROX 2001. LNCS, vol. 2129, pp. 261–272. Springer, Heidelberg (2001)
Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252–271 (1996)
Ruzzo, W.L.: On uniform circuit complexity. J. Comput. Syst. Sci. 22(3), 365–383 (1981)
Rothblum, G.N., Vadhan, S., Wigderson, A.: Interactive proofs of proximity: Delegating computation in sublinear time. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC) (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goldreich, O., Gur, T., Rothblum, R.D. (2015). Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_54
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_54
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)