Proofs of proximity for context-free languages and read-once branching programs

DOI10.1016/j.ic.2018.02.003zbMath1395.68169OpenAlexW3021472282WikidataQ113872846 ScholiaQ113872846MaRDI QIDQ1640993

Tom Gur, Oded Goldreich, Ron D. Rothblum

Publication date: 14 June 2018

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2018.02.003

zbMATH Keywords

interactive proofsproperty testingprobabilistic proof systems

Mathematics Subject Classification ID

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• One way functions and pseudorandom generators
• On uniform circuit complexity
• Modern cryptography, probabilistic proofs and pseudo-randomness
• Fast approximate probabilistically checkable proofs
• Regular Languages are Testable with a Constant Number of Queries
• Partial tests, universal tests and decomposability
• Non-Interactive Proofs of Proximity
• On Proximity-Oblivious Testing
• Testing Membership in Languages that Have Small Width Branching Programs
• Property testing and its connection to learning and approximation
• Two-Sided Error Proximity Oblivious Testing
• Lower bounds on the complexity of real-time branching programs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Property Testing of Massively Parametrized Problems – A Survey
• Constant-round interactive proofs for delegating computation
• Fundamentals of Computation Theory
• Interactive proofs of proximity
• Two Families of Languages Related to ALGOL
• The complexity of theorem-proving procedures
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem

This page was built for publication: Proofs of proximity for context-free languages and read-once branching programs