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

DOI10.1016/J.IC.2018.02.003MaRDI QIDQ1640993zbMATH OpenOpenAlexWikidataFDO

Authors Oded Goldreich, Tom Gur, 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

property testinginteractive proofsprobabilistic proof systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Complexity of proofs (03F20)

Recommendations

• Proofs of proximity for context-free languages and read-once branching programs
• Non-interactive proofs of proximity
• Non-interactive proofs of proximity
• An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
• An exponential separation between MA and AM proofs of proximity

Cites work

• scientific article; zbMATH DE number 5485522 (Why is no real title available?)
• scientific article; zbMATH DE number 1833419 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Constant-round interactive proofs for delegating computation
• Fast approximate probabilistically checkable proofs
• Fundamentals of Computation Theory
• Interactive proofs of proximity: delegating computation in sublinear time
• Lower bounds on the complexity of real-time branching programs
• Modern cryptography, probabilistic proofs and pseudo-randomness
• Non-interactive proofs of proximity
• On Proximity-Oblivious Testing
• On uniform circuit complexity
• One way functions and pseudorandom generators
• Partial tests, universal tests and decomposability
• Property testing and its connection to learning and approximation
• Property testing of massively parametrized problems -- a survey
• Regular languages are testable with a constant number of queries
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Testing Membership in Languages that Have Small Width Branching Programs
• The complexity of theorem-proving procedures
• Two Families of Languages Related to ALGOL
• Two-sided error proximity oblivious testing (extended abstract)

Cited in

(4)

• An exponential separation between MA and AM proofs of proximity
• An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
• Non-interactive proofs of proximity
• Proofs of proximity for context-free languages and read-once branching programs

Describes a project that uses

Uses Software

• ALGOL 60

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1640993)