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

DOI10.1016/J.IC.2018.02.003zbMATH Open1395.68169OpenAlexW3021472282WikidataQ113872846 ScholiaQ113872846MaRDI QIDQ1640993FDOQ1640993

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

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

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)

Cites Work

• On uniform circuit complexity
• Property testing and its connection to learning and approximation
• 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
• Robust Characterizations of Polynomials with Applications to Program Testing
• One way functions and pseudorandom generators
• Two Families of Languages Related to ALGOL
• Title not available (Why is that?)
• Non-interactive proofs of proximity
• Property testing of massively parametrized problems -- a survey
• Regular languages are testable with a constant number of queries
• Testing Membership in Languages that Have Small Width Branching Programs
• Title not available (Why is that?)
• Fundamentals of Computation Theory
• Modern cryptography, probabilistic proofs and pseudo-randomness
• Title not available (Why is that?)
• Constant-round interactive proofs for delegating computation
• Lower bounds on the complexity of real-time branching programs
• Fast approximate probabilistically checkable proofs
• Partial tests, universal tests and decomposability
• On Proximity-Oblivious Testing
• Two-sided error proximity oblivious testing (extended abstract)
• Interactive proofs of proximity: delegating computation in sublinear time

Cited In (4)

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

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)