DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.69

QMA Lower Bounds for Batch Verification via Approximate Degree

Authors: Mark Bun, Mandar Juvekar, and Samuel King

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

We study batch verification in QMA query and communication complexity, where the goal is to understand how the resources needed to verify m copies of a Boolean function f depend on m. We give a general technique for proving lower bounds on the witness-query tradeoff needed to batch verify a function f in terms of its approximate degree. Applying this technique to an explicit family of DNF formulas f, we show that attempting to save even a constant factor on the witness length of the baseline approach to batch verifying f necessitates a large polynomial increase in the query cost. We also obtain new lower bounds on the QMA query complexity of read-once CNF formulas and on the surjectivity and k-element distinctness functions. Our lower bounds also lift to give communication analogs of these results.

Cite as

Mark Bun, Mandar Juvekar, and Samuel King. QMA Lower Bounds for Batch Verification via Approximate Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 69:1-69:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bun_et_al:LIPIcs.APPROX/RANDOM.2026.69,
  author =	{Bun, Mark and Juvekar, Mandar and King, Samuel},
  title =	{{QMA Lower Bounds for Batch Verification via Approximate Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{69:1--69:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.69},
  URN =		{urn:nbn:de:0030-drops-277861},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.69},
  annote =	{Keywords: QMA, approximate degree, query complexity, communication complexity, quantum computation}
}

Document

DOI: 10.4230/LIPIcs.ITC.2024.5

On the Power of Adaptivity for Function Inversion

Authors: Karthik Gajulapalli, Alexander Golovnev, and Samuel King

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract

We study the problem of function inversion with preprocessing where, given a function f : [N] → [N] and a point y in its image, the goal is to find an x such that f(x) = y using at most T oracle queries to f and S bits of preprocessed advice that depend on f. The seminal work of Corrigan-Gibbs and Kogan [TCC 2019] initiated a line of research that shows many exciting connections between the non-adaptive setting of this problem and other areas of theoretical computer science. Specifically, they introduced a very weak class of algorithms (strongly non-adaptive) where the points queried by the oracle depend only on the inversion point y, and are independent of the answers to the previous queries and the S bits of advice. They showed that proving even mild lower bounds on strongly non-adaptive algorithms for function inversion would imply a breakthrough result in circuit complexity. We prove that every strongly non-adaptive algorithm for function inversion (and even for its special case of permutation inversion) must have ST = Ω(N log (N) log (T)). This gives the first improvement to the long-standing lower bound of ST = Ω(N log N) due to Yao [STOC 90]. As a corollary, we conclude the first separation between strongly non-adaptive and adaptive algorithms for permutation inversion, where the adaptive algorithm by Hellman [TOIT 80] achieves the trade-off ST = O(N log N). Additionally, we show equivalence between lower bounds for strongly non-adaptive data structures and the one-way communication complexity of certain partial functions. As an example, we recover our lower bound on function inversion in the communication complexity framework.

Cite as

Karthik Gajulapalli, Alexander Golovnev, and Samuel King. On the Power of Adaptivity for Function Inversion. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gajulapalli_et_al:LIPIcs.ITC.2024.5,
  author =	{Gajulapalli, Karthik and Golovnev, Alexander and King, Samuel},
  title =	{{On the Power of Adaptivity for Function Inversion}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{5:1--5:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.5},
  URN =		{urn:nbn:de:0030-drops-205137},
  doi =		{10.4230/LIPIcs.ITC.2024.5},
  annote =	{Keywords: Function Inversion, Non-Adaptive lower bounds, Communication Complexity}
}

Search Results

Documents authored by King, Samuel

QMA Lower Bounds for Batch Verification via Approximate Degree

Abstract

Cite as

On the Power of Adaptivity for Function Inversion

Abstract

Cite as

Thanks for your feedback!

Could not send message