Proofs of proximity for context-free languages and read-once branching programs
From MaRDI portal
Publication:1640993
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Uses Software
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
