Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
From MaRDI portal
Publication:3448824
DOI10.1007/978-3-662-47672-7_54zbMath1395.68168OpenAlexW2462227731WikidataQ130371181 ScholiaQ130371181MaRDI QIDQ3448824
Tom Gur, Ron D. Rothblum, Oded Goldreich
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/116112/1/WRAP-proofs-proximity-context-free-branching-Gur-2015.pdf
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (10)
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Delegating RAM Computations ⋮ Zero-Knowledge Proofs of Proximity ⋮ Proofs of Proximity for Distribution Testing ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Non-interactive proofs of proximity ⋮ Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP ⋮ Unnamed Item ⋮ Constant-Round Interactive Proofs for Delegating Computation
Cites Work
- Unnamed Item
- Unnamed Item
- On uniform circuit complexity
- 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
- Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
- Arguments of Proximity
- Lower bounds on the complexity of real-time branching programs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Fundamentals of Computation Theory
- Interactive proofs of proximity
- 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
