The Library
Proofs of proximity for context-free languages and read-once branching programs
Tools
Tools
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
