Document Open Access Logo

Delegation for Search Problems

Authors Justin Holmgren, Andrea Lincoln, Ron D. Rothblum

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.73.pdf
  • Filesize: 0.78 MB
  • 18 pages

Document Identifiers

Author Details

Justin Holmgren
  • NTT Research, Sunnyvale, CA, USA
Andrea Lincoln
  • University of California Berkeley, CA, USA
Ron D. Rothblum
  • Technion, Haifa, Israel

Funding

  • Rothblum, Ron D.: Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

Acknowledgements

We thank Benny Applebaum for helpful discussions.

Cite AsGet BibTex

Justin Holmgren, Andrea Lincoln, and Ron D. Rothblum. Delegation for Search Problems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 73:1-73:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.73

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
Keywords
  • Interactive Proofs
  • Fine-Grained Complexity
  • Delegation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 59-78. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.14.
  2. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is valiant’s parser. SIAM J. Comput., 47(6):2527-2555, 2018. URL: https://doi.org/10.1137/16M1061771.
  3. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 522-539. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  4. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. From secrecy to soundness: Efficient verification via secure computation. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, volume 6198 of Lecture Notes in Computer Science, pages 152-163. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-14165-2_14.
  5. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput., 47(3):1087-1097, 2018. URL: https://doi.org/10.1137/15M1053128.
  6. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 252-260. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/CCC.2006.6.
  7. Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, and Aviad Rubinstein. Fine-grained complexity meets IP = PSPACE. CoRR, abs/1805.02351, 2018. URL: http://arxiv.org/abs/1805.02351.
  8. Kai-Min Chung, Yael Tauman Kalai, and Salil P. Vadhan. Improved delegation of computation using fully homomorphic encryption. In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science, pages 483-501. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-14623-7_26.
  9. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  10. Rosario Gennaro, Craig Gentry, and Bryan Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. IACR Cryptol. ePrint Arch., page 547, 2009. URL: http://eprint.iacr.org/2009/547.
  11. Oded Goldreich. Computational complexity - A conceptual perspective. Cambridge University Press, 2008. URL: https://doi.org/10.1017/CBO9780511804106.
  12. Oded Goldreich, Tom Gur, and Ron D. Rothblum. Proofs of proximity for context-free languages and read-once branching programs. Inf. Comput., 261:175-201, 2018. URL: https://doi.org/10.1016/j.ic.2018.02.003.
  13. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186-208, 1989. URL: https://doi.org/10.1137/0218012.
  14. Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick. Faster k-sat algorithms using biased-ppsz. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 578-589. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316359.
  15. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006. Google Scholar
  16. Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In STOC, pages 723-732, 1992. URL: https://doi.org/10.1145/129712.129782.
  17. Lillian Lee. Fast context-free grammar parsing requires fast boolean matrix multiplication. J. ACM, 49(1):1-15, 2002. URL: https://doi.org/10.1145/505241.505242.
  18. Philip M. Lewis, Richard Edwin Stearns, and Juris Hartmanis. Memory bounds for recognition of context-free and context-sensitive languages. In SWCT (FOCS), pages 191-202, 1965. URL: https://doi.org/10.1109/FOCS.1965.14.
  19. Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane. An improved exponential-time algorithm for k-sat. J. ACM, 52(3):337-364, 2005. URL: https://doi.org/10.1145/1066100.1066101.
  20. Leslie G. Valiant. General context-free recognition in less than cubic time. J. Comput. Syst. Sci., 10(2):308-315, 1975. URL: https://doi.org/10.1016/S0022-0000(75)80046-8.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact