
The Library
Proofs of proximity for context-free languages and read-once branching programs
Tools
Goldreich, Oded, Gur, Tom and Rothblum, Ron D. (2015) Proofs of proximity for context-free languages and read-once branching programs. In: The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 6-10 Jul 2015. Published in: Automata, Languages, and Programming. ICALP 2015, 9134 pp. 666-677. ISBN 9783662476710. doi:10.1007/978-3-662-47672-7_54 ISSN 0302-9743.
|
PDF
WRAP-proofs-proximity-context-free-branching-Gur-2015.pdf - Accepted Version - Requires a PDF viewer. Download (1134Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-662-47672-7_54
Abstract
Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity ( MAP ), the verifier receives, in addition to query access to the input, also free access to an explicitly given short (sub-linear) proof. A more general notion is that of an interactive proof of proximity ( IPP ), in which the verifier is allowed to interact with an all-powerful, yet untrusted, prover. MAP s and IPP s may be thought of as the NP and IP analogues of property testing, respectively.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computer science, Computer programs | ||||||
Journal or Publication Title: | Automata, Languages, and Programming. ICALP 2015 | ||||||
Publisher: | Springer | ||||||
ISBN: | 9783662476710 | ||||||
ISSN: | 0302-9743 | ||||||
Book Title: | Automata, Languages, and Programming | ||||||
Official Date: | 2015 | ||||||
Dates: |
|
||||||
Volume: | 9134 | ||||||
Page Range: | pp. 666-677 | ||||||
DOI: | 10.1007/978-3-662-47672-7_54 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 11 April 2019 | ||||||
Date of first compliant Open Access: | 11 April 2019 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Kyoto, Japan | ||||||
Date(s) of Event: | 6-10 Jul 2015 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year