2026-07-21T14:14:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16414 2024-03-06T10:57:25Z ddc:004 open_access

Delegation for Search Problems Holmgren, Justin Lincoln, Andrea Rothblum, Ron D. Interactive Proofs Fine-Grained Complexity Delegation The theory of proof systems in general, and interactive proofs in particular, has been immensely influential. Such proof systems allow a prover to convince a verifier whether a given statement is true or not - namely to solve a decision problem. In this work we initiate a study of interactive proofs for search problems. More precisely, we consider a setting in which a client C, given an input x, would like to find a solution y satisfying (x,y) ∈ R, for a given relation R. The client wishes to delegate this work to an (untrusted) advisor A, who has more resources than C. We seek solutions in which the communication from A is short, and, in particular, shorter than the length of the output y. (In particular, this precludes the trivial solution of the advisor sending y and then proving that (x,y) ∈ R using a standard interactive proof.) We show that such search delegation schemes exist for several problems of interest including (1) longest common subsequence (LCS) and edit distance, (2) parsing context-free grammars and (3) k-SAT. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Justin Holmgren and Andrea Lincoln and Ron D. Rothblum 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.73 urn:nbn:de:0030-drops-164146 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.73 eng https://creativecommons.org/licenses/by/4.0/legalcode