Query Complexity

Momentum

3 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 23

Oct 6, 2026cs.DS

Lower Bounds for Parallel Diffusion Sampling

Standard diffusion samplers generate samples through repeated evaluations of a learned score function. Parallel sampling methods seek to accelerate generation by trading additional evaluations for fewer sequential rounds. This raises the question of how much sequential dependence is unavoidable, even when many score queries can be made simultaneously. We establish the first polynomial parallel-round lower bounds for diffusion sampling with approximate scores. Specifically, we prove (1) a

\widetildeΩ(d^{1/3})

-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in

R^d

, and (2) an

Ω(d)

-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball. Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy. The linear bound is tight for our box family. Our constructions use fixed approximate score oracles that enforce sequential access to hidden information while satisfying the accuracy guarantee at every noise level.

Yiwen Kou, Yimeng Wang

UCLA

Diffusion Sampling Query Complexity

Ask PDF

Sep 30, 2026cs.DS

Query-efficient winner prediction in district-based elections

In a district-based election, N voters are partitioned into k districts, and each voter votes for one of m candidates. Each district elects a winner using the plurality rule (i.e. the candidate getting the largest number of votes is declared the winner, breaking ties as per some fixed rule), and the overall winner is determined by applying plurality to the district winners; we assume that there is a unique winner amongst the district winners. The margin of victory of such an election is the minimum number of votes that must be altered so that the current winner ceases to be the unique district winner. We study the problem of predicting the winner of a district-based election in the query complexity model, where one has query access to individual votes. The objective is to minimise the number of queries. This setting captures exit polling, where queries correspond to interviewing voters, and is closely related to problems in query complexity and property testing. Assuming that the margin of victory of the election is at least eps N, Dey, Kar and Sanyal (AAMAS 2023) gave algorithms for the case of two candidates with error probability del and query complexity tilde{O}(1/eps^6 log^2 1/del), which improves to tilde{O}(1/eps^4 log^2 1/del) under the additional assumption that district populations are balanced. Our main result is an adaptive randomised algorithm that, for an arbitrary district-based election and any error parameter del, with probability at least 1-del, predicts the winner correctly using tilde{O}(1/eps^2 log m/del log 1/del) queries. In particular, we improve the bounds of Dey et al. for arbitrary district populations and extend their results to any number of candidates. Furthermore, for constantly many candidates, our algorithm nearly matches a lower bound of Omega(1/eps^2 log 1/del) on the query complexity that holds even for two candidates and a single district.

Koustav De, Debajyoti Kar, Swagato Sanyal

Department of Computer Science and Engineering, Indian Institute of Technology Kharagpur, India · Department of Computer Science and Automation, Indian Institute of Science Bengaluru, India · School of Computer Science, University of Sheffield, United Kingdom

Query Complexity Social Choice Theory

Ask PDF

Sep 9, 2026cs.LG

An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order

Attias, Hanneke and Ramaswami (NeurIPS 2025) asked whether randomization provably reduces the oracle calls needed for online learning when the class is accessible only through an oracle. We study the instance they singled out: transductive online learning of thresholds on an unknown total order of T instances, with a consistency-type ERM oracle that returns a full concept consistent with a queried labeled set (or reports non-realizability). Our main result is a separation for a fixed natural oracle. When the oracle is the minimal-prefix rule (or the maximal-prefix rule), every deterministic learner makes M mistakes and Q calls with

M+Q\ge T-\varepsilon

on some instance (

\varepsilon\in\{0,1\}

, according to whether the empty prefix is a concept), and the constant is exact; hence

O(\log T)

mistakes cost

T-\varepsilon-O(\log T)

calls, whereas that paper's randomized learner achieves

O(\log T)

expected calls and mistakes under the same rule. The randomized order is optimal: on an explicit hard distribution under the minimal-prefix rule, every learner has expected mistakes at least

((T+1-\varepsilon)\,128^{-\mathbb{E}[Q]}-1)/2

, so

Ω(\log T)

expected calls are necessary for polylogarithmic mistakes. The separation is governed by the oracle's selection rule, not by the class alone: for a legal feasible-median ERM rule a deterministic learner achieves

O(\log T)

calls and mistakes, while a global-median rule again forces linear total cost. The same linear bound holds when the oracle's answers are chosen adversarially and then frozen into a memoryless oracle. We add partial tradeoff results for fixed query budgets (the middle regime is open) and an interface contrast: with only a weak consistency oracle, returning a realizability bit, both deterministic and randomized learners need

Θ(T)

calls.

Xuan Li

University of New South Wales, Sydney, Australia

Query Complexity Oracle Complexity Online Learning Empirical Risk Minimization

Ask PDF

Sep 9, 2026cs.DS

A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse

Consistent submodular maximization studies the tradeoff between solution quality and stability when elements arrive over time. For a monotone submodular objective, which models diminishing returns, an algorithm maintains a set of at most

k

available elements and changes only

O(1)

elements after each insertion. Dütting et al. [2025] established a tight

2/3

approximation with unrestricted computation and a polynomial-time

0.51

approximation. They left open at STOC 2025 whether efficient algorithms can match the offline

1-1/e

guarantee. We resolve this problem by proving that the supremum approximation achievable with polynomially many value queries and worst-case constant recourse is

β=2-\sqrt2\approx0.5858<1-1/e.

For every

\varepsilon>0

, our randomized algorithm attains

β-\varepsilon

with

O(\varepsilon^{-2})

changes per insertion. Any fixed improvement requires exponentially many queries before one critical insertion or linear recourse of

Ω(k)

changes at that insertion, even with unlimited queries afterwards. This gap quantifies the cost of consistency: the current oracle hides which elements will be needed after an arrival. We also determine the exact curvature-dependent threshold

1-(\sqrt2-1)\vartheta

, attain

1-1/e-\varepsilon

for weighted coverage with

O(\varepsilon^{-1})

recourse, and separate the existence of universal future-price certificates from their efficient computation. Our algorithm has a bounded-bit polynomial-time implementation for polynomial-bit rational oracle answers; the lower bound uses only logarithmic-bit rational answers.

Shi Fu, Qixin Zhang, Dacheng Tao

Nanyang Technological University, Singapore

Submodular Optimization Query Complexity Approximation Algorithms

Ask PDF

Aug 4, 2026cs.DS

Quality Control Algorithms for Pattern Counting

In recent work, Marcussen, Rubinfeld, and Sudan introduced the notion of quality control problems, which aim to capture the task of determining if a given input is truly random. Formally, their goal is to accept typical inputs from the specified distribution while rejecting every input whose value of a specified statistic is far from the distributional baseline. This captures the empirical practice of using specified statistics as a proxy for the quality of randomness. Empirical algorithms, however, have not exploited the asymmetry in the definition of quality control problems, which require soundness guarantees in the worst-case while only seeking average-case completeness. Their work abstracted a problem definition emphasizing this asymmetry and used it to give efficient quality control algorithms for assessing the randomness of graphs. In this work, we introduce and study quality control problems over sequences, where the goal is to distinguish a sequence of i.i.d. characters from sequences where some specified pattern appears too often (or too infrequently) as a subsequence. We consider this problem in both the finite-alphabet setting and for real-valued sequences. We refer to the former setting as the pattern counting problem. In the latter case, the natural notion of a pattern is to consider the relative ordering of the characters in the subsequence, and we refer to this as the permutation pattern counting problem. Algorithms to approximately count (permutation) patterns of length

k

in a worst-case sequence of length

n

can provably require exponential in

k

queries into the sequence. In contrast, we show that by taking advantage of the asymmetry in the definition of quality control, we give algorithms that run in poly

(k)

time to solve these problems. We also prove that any quality control algorithm (over some natural distributions) requires superlinear queries in

k

Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan

School of Engineering and Applied Sciences, Harvard University, Cambridge, Massachusetts, USA. · Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, Massachusetts, USA.

Query Complexity

Ask PDF

Aug 3, 2026cs.CC

Optimal Unambiguous DNFs and Alon-Saks-Seymour

We construct unambiguous DNFs having width

O(n)

but

0

-certificate complexity

Ω(n^2)

. By utilizing the special structure of these DNFs, we prove a lifting theorem with a constant-sized gadget that lifts the DNF to a communication problem, while losslessly translating the separation in certificate complexity to a separation in communication complexity. This leads to an optimal refutation of the Alon-Saks-Seymour conjecture, as well as an optimal communication lower bound for the Clique versus Independent Set problem, improving the previous results of Balodis, Ben-David, Göös, Jain and Kothari (FOCS 2021, SICOMP 2023) by several doubly logarithmic factors. As further applications of our construction to query complexity and learning theory, we exhibit: (a) a family of Boolean functions that has an optimal quartic separation between certificate complexity and approximate degree, and (b) a sample compression lower bound of

Ω(\sqrt{\log c})

for multiclass concept classes over

c

labels.

Chirag Pabbaraju

Stanford University.

Query Complexity Communication Complexity

Ask PDF

Aug 3, 2026cs.DS

Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds

We study the round complexity of learning a hidden partition

\mathcal{P}

of an

n

-element universe using PAIR queries: PAIR(

x,y

) tells us whether

x

and

y

belong to the same part of the partition or not. While it is easy to learn using

n|\mathcal{P}|

queries using a basic algorithm and this query complexity is optimal, this basic algorithm is highly sequential. Black, Mazumdar, and Saha [COLT 2025] recently gave tight deterministic round/query tradeoffs when the number of parts of

\mathcal{P}

is known. In particular they prove

Θ(\log\log n)

rounds are sufficient and necessary to limit the number of queries to

n|\mathcal{P}|

. They leave proving a randomized lower bound as an open direction. We show that randomization dramatically changes the picture. When the number of parts

k = |\mathcal{P}|

is known, we give a simple 3-round randomized algorithm using

O(nk\log n)

queries with high probability, and prove that 2 rounds require

Ω(n^{4/3}k^{2/3})

queries -- the same as deterministic algorithms. We also study a more general setting where the number of parts is unknown. In this case, we give a 4-round randomized algorithm using

O(n|\mathcal P|\log^2 n)

queries with high probability, and prove that 3-rounds cannot achieve near-optimal query complexity. Furthermore, we show an even bigger separation in this regime between randomized and deterministic algorithms: for the latter,

Θ(\log n/\log\log n)

rounds are necessary and sufficient to obtain near-optimal query complexity.

Deeparnab Chakrabarty, Aditi Dudeja, David Saulpic

Dartmouth College · The Chinese University of Hong Kong (Shenzhen) · CNRS and Universit´e Paris Cit´e

Query Complexity Clustering

Ask PDF

Jul 30, 2026math.NA

Windowed thinning and query complexity for the bouncy particle and Zigzag samplers

Let

μ(d x)\propto e^{-U(x)} d x

\R^d

, where

U

m

-strongly convex and

L

-smooth, and denote by

κ=L/m

the condition number. We consider windowed thinning, an exact simulation method for the bouncy particle sampler and the coordinate Zigzag process. The method divides a trajectory into deterministic windows and uses a gradient evaluation at the beginning of each window to construct a tractable local envelope for the event rate. Combining this construction with quantitative mixing estimates and finite-time bounds on the expected numbers of bounces and flips yields query complexity guarantees from a Gaussian cold start. For total-variation error

\varepsilon

, the expected query counts are

O(κ^{1/2}d\,(d\logκ+\log\frac1\varepsilon))

gradient queries for the bouncy particle sampler and

O(κd^{1/4}(d\logκ+\log\frac1\varepsilon))

full-gradient equivalents for Zigzag, where

d

coordinate-partial queries count as one equivalent.

Jianfeng Lu, Yinchen Luo

Markov Chain Monte Carlo Query Complexity

Ask PDF

Jul 21, 2026cs.DS

Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

We prove two lower bounds for the first order oracle complexity of minimizing a

d

-dimensional

1

-Lipschitz convex function over the unit ball with

m

bits of memory. We first show that any such (possibly randomized) algorithm must make

\tildeΩ(\frac{d^2}{\sqrt{m}})

oracle queries. For deterministic optimization algorithms, we show that

\tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\})

queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of

\tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\})

and

\tildeΩ(\frac{d^{5/3}}{m^{1/3}})

for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around

m\approx d^2

, where a polylogarithmic change in memory leads to a

\mathsf{poly}(d)

change in the number of required oracle calls. Further, when the suboptimality is polynomially small in

d

, our lower bound randomized algorithms is the first to show that

\tildeΩ(d^2)

memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in

d

Michael Menart, Aleksandar Nikolov, Ohad Shamir

Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto · Weizmann Institute of Science and University of Toronto +1

Query Complexity Oracle Complexity Memory-Efficient Optimization Constrained Optimization

Ask PDF

Jun 18, 2026math.OC

Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model

The John ellipsoid of a symmetric polytope

P=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{A}\mathbf{x}\|_\infty\le1\}

\mathbf{A}\in\mathbb{R}^{n\times d}

, is computed by a long line of leverage-score algorithms, from Cohen, Cousins, Lee and Yang (COLT 2019) to its successors [WY24, CLS+25], all reaching a

(1+\varepsilon)

-approximation in

Θ(\varepsilon^{-1}\log(n/d))

iterations. We separate this complexity into three costs the modern line conflates (certification, identification, and accuracy) and locate the historical

\varepsilon^{-1}

in the first alone. In the equivalent D-optimal-design form

\min_{\mathbf{p}\inΔ_n}-\log\det(\sum_i p_i\mathbf{a}_i\mathbf{a}_i^\top)

, the leverage-score oracle is exactly the first-order oracle and the

(1+\varepsilon)

-John guarantee the Frank-Wolfe gap

g(\mathbf{p})\le\varepsilon d

; through this dictionary the costs come apart. The

\varepsilon^{-1}

is a certification artifact: the uniform average of the iterates, the certificate used throughout the line, has gap exactly

Θ(1/T)

, however cheap each iteration is made. Pointed instead at the last iterate the same oracle is fast: a warm-started accelerated method reaches the guarantee in

C(\mathbf{A})+O(\sqrtκ\log(1/\varepsilon))

queries after an

\varepsilon

-independent setup

C(\mathbf{A})

, and once the optimal face is identified the facial problem is an unconstrained self-concordant minimization whose Hessian the oracle recovers exactly, so damped Newton needs only

O(\log\log(1/\varepsilon))

steps, for a total of

C(\mathbf{A})+O(d^2\log\log(1/\varepsilon))

queries. The accuracy dependence is thus doubly logarithmic after an

\varepsilon

-independent, condition-dependent setup; the open problem is the remaining identification cost (a condition-free bound on reaching the optimal face) and lower bounds. Accuracy is not the obstruction.

Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2

University of New South Wales · University of California, Berkeley · University of Sydney

Query Complexity Oracle Complexity Constrained Optimization

Ask PDF

Jun 10, 2026cs.NE

Mathematical perspective on genetic algorithms with optimization guided operators

Recent work in ML applies genetic algorithms at inference time to iteratively improve solutions to optimization problems. The basic mutation and recombination operators involved are qualitatively different from those studied classically. Mutations are no longer random; an ML algorithm mutates a solution with the goal of improving an objective. Similarly, recombination is not based on random collages of parent solutions. Instead, it is an ML optimization-based operator whose goal is to synthesize improved solutions from its inputs. Thus, these mutation and recombination operators are more likely to improve the objective, but their computational cost is much higher. We introduce a general model of genetic algorithms and formulating optimization in this model as a query-complexity problem, using the language of reinforcement learning. We then study specialized models. We show that some optimization problems require generation, mutation, and recombination to be solved. We then obtain qualitatively tight algorithms for a family of problems within this framework that captures the nontrivial role of diversity in the solution pool, a key feature of practical ML genetic algorithms.

Anna Brandenberger, Ilan Doron-Arad, Elchanan Mossel

Department of Mathematics, MIT

Query Complexity Genetic Algorithms

Ask PDF

May 19, 2026cs.LG

Optimal Reconstruction from Linear Queries

We study the problem of reconstructing an unknown point in

\mathbb{R}^d

from approximate linear queries. This setting arises naturally in applications ranging from low-dimensional remote sensing and signal recovery to high-dimensional data analysis and privacy-sensitive inference. Our main goal is to characterize the optimal reconstruction error as a function of the number of queries

T

, the ambient dimension

d

, and the noise parameter

δ

. We first analyze the limit

T \to \infty

and show that the optimal reconstruction error converges to the explicit value

\sqrt{2d/(d+1)} δ

, which plays a role analogous to the Bayes optimal error in supervised learning. When the dimension is fixed, we show that the excess error above this limit decays doubly exponentially fast as

T \to \infty

, a rate that is significantly faster than those typically encountered in learning curves. When the dimension grows, we show that a number of queries on the order of

\exp(d)

is necessary and sufficient to achieve vanishing excess error. Finally, we introduce and analyze an improper variant of the reconstruction problem. From a technical perspective, our main contribution is a generalization of Jung's theorem (1901). The classical theorem bounds the maximum possible radius of a set of diameter 1 and characterizes extremal bodies. Our generalization provides a robust variant that characterizes near-extremal bodies and is proved via geometric and dynamical arguments exploiting symmetry and Lie group actions.

Yuval Filmus, Shay Moran, Elizaveta Nesterova

Technion – Israel Institute of Technology · Google Research

Query Complexity Inverse Problems

Ask PDF

May 13, 2026cs.DS

Min-Max Optimization Requires Exponentially Many Queries

We study the query complexity of min-max optimization of a nonconvex-nonconcave function

f

over

[0,1]^d \times [0,1]^d

. We show that, given oracle access to

f

and to its gradient

\nabla f

, any algorithm that finds an

\varepsilon

-approximate stationary point must make a number of queries that is exponential in

1/\varepsilon

d

Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1

Bocconi University · Politecnico di Milano · University of Oxford

Query Complexity Oracle Complexity Min-Max Optimization Nonconvex Optimization

Ask PDF

May 5, 2026cs.CL

Reproducing Complex Set-Compositional Information Retrieval

Complex information needs may involve set-compositional queries using conjunction, disjunction, and exclusion, yet it remains unclear whether current retrieval paradigms genuinely satisfy such constraints or exploit `semantic shortcuts'. We conduct a reproducibility study to benchmark major retrieval families and reasoning-targeted methods on QUEST and QUEST+Variants, and introduce LIMIT+, a controlled benchmark where relevance depends on arbitrary attribute predicates and constraint satisfaction, and less on pretrained knowledge. Our findings show that (i) on QUEST, the best neural retrievers achieve an effectiveness that is more than double what can be achieved with BM25 (Recall@100

{>}

0.41 vs.\ 0.20), but reasoning-targeted methods like ReasonIR and Search-R1 do not outperform general-purpose retrievers uniformly; (ii) on LIMIT+, gains fail to transfer, where the strongest QUEST method collapses from Recall@100

{\approx}

0.42 to below 0.02, while classic lexical retrieval gains to

{\sim}

0.96. Lastly, (iii) stratifying by compositional depth reveals a consistent degradation across all methods, where algebraic sparse and lexical methods show more stable performance while dense approaches collapse. We release code and LIMIT+ data generation scripts to support future reproducibility and controlled evaluation.

Vincent Degenhart, Dewi Timman, Arjen P. de Vries +2

Radboud University · Nijmegen, NL

Query Complexity Lexical Retrieval Information Retrieval IR Evaluation Dense Retrieval

Ask PDF

Apr 30, 2026cs.DS

Matroid Algorithms Under Size-Sensitive Independence Oracles

The standard oracle model for matroid algorithms assumes that each independence query can be answered in constant time, regardless of the size of the queried set. While this abstraction has underpinned much of the theoretical progress in matroid optimization, it masks the true computational effort required by these algorithms. In particular, for natural and widely studied classes such as graphic matroids, even a single independence query can require work linear in the size of the set, making the constant-time assumption implausible. We address this gap by introducing a size-sensitive cost model where the cost of a query

Q

scales with

|Q|

. Nearly linear-time oracle implementations exist for broad families of matroids, and this refined abstraction therefore captures the true cost of query evaluation while allowing for a more faithful comparison between general matroids and their natural special cases. Within this framework we study three fundamental algorithmic tasks: finding a basis of a matroid, approximating its rank, and approximating its partition size. We establish tight results, proving nearly matching upper and lower bounds that show the optimal query cost is (up to logarithmic factors) quadratic in the size of the matroid. On the algorithmic side, our upper bounds are realized by explicit procedures that construct the desired solution. On the complexity side, our lower bounds are unconditional and already hold even for weaker distinguishing formulations of the problems. Finally, for matroids with maximum circuit size at most

c

, we show that the quadratic barrier can be broken, providing an algorithm that calculates the maximum-weight basis with expected query cost

\mathcal{O}(n^{2-1/c} \log n)

Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +1

*Equal contribution 1Department of Computer Science, University of Maryland, College Park, USA.

Query Complexity Oracle Complexity Combinatorial Optimization Approximation Algorithms

Ask PDF

Apr 24, 2026cs.DB

How Hard is it to Decide if a Fact is Relevant to a Query?

We consider the following fundamental problem: given a database D, Boolean conjunctive query (CQ) q, and fact f in D, decide whether f is relevant to q wrt. D, i.e., does f belong to a minimal subset S of D such that S |= q. Despite being of central importance to query answer explanation, the combined complexity of deciding query relevance has not been studied in detail, leaving open what makes this problem hard, and which restrictions can yield lower complexity. Relevance has already been shown to be harder than query evaluation: namely,

Σ^p_2

-complete for CQs, even over a binary signature. We further observe that NP-hardness applies already to (acyclic) chain CQs. Our work identifies self-joins (multiple atoms with the same relation) as the culprit. Indeed, we prove that if we forbid or bound the occurrence of self-joins, then relevance has the same complexity as query evaluation, namely, NP (without structural restrictions) and LogCFL (for bounded hypertreewidth classes). In the ontology setting, we establish an analogous result for ontology-mediated queries consisting of a CQ and DL-Lite_R ontology, namely that relevance is no harder than query answering provided that we bound the interaction width (which generalizes both self-join width and a recently introduced 'interaction-free' condition). Our results thus pinpoint what makes relevance harder than query evaluation and identify natural classes of queries which admit efficient relevance computation.

Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade

Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400, Talence, France

Query Complexity Relational Databases

Ask PDF

Apr 19, 2026cs.GT

Learning Unanimously Acceptable Lotteries via Queries

Many high-stakes AI deployments proceed only if every stakeholder deems the system acceptable relative to their own minimum standard. With randomization over a finite menu of options, this becomes a feasibility question: does there exist a lottery over options that clears all stakeholders' acceptability bars? We study a query model where the algorithm proposes lotteries and receives only binary accept/reject feedback. We give deterministic and randomized algorithms that either find a unanimously acceptable lottery or certify infeasibility; adaptivity can avoid eliciting many stakeholders' constraints, and randomization further reduces the expected elicitation cost relative to full elicitation. We complement these upper bounds with worst-case lower bounds (in particular, linear dependence on the number of stakeholders and logarithmic dependence on precision are unavoidable). Finally, we develop learning-augmented algorithms that exploit natural forms of advice (e.g., likely binding stakeholders or a promising lottery), improving query complexity when predictions are accurate while preserving worst-case guarantees.

Davin Choo, Paul W. Goldberg, Nicholas Teh

Harvard University, USA · University of Oxford, UK

Query Complexity Learning-Augmented Algorithms Preference Learning Preference Elicitation

Ask PDF

Apr 16, 2026quant-ph

Optimal algorithmic complexity of inference in quantum kernel methods

Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained model on new data requires estimating a weighted sum

\sum_{i=1}^N α_i k(x,x_i)

N

kernel values to additive precision

\varepsilon

, where

α

is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of

O(N\lVertα\rVert_2^2/\varepsilon^2)

. In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of

O(\lVertα\rVert_1/\varepsilon)

, removing the dependence on

N

from the query count and yielding a quadratic improvement in both

\lVertα\rVert_1

and

\varepsilon

. We prove a matching lower bound of

Ω(\lVertα\rVert_1/\varepsilon)

, establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.

Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi +2

Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany · Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany · Department of Quantum Information Science and Engineering, Sejong University, 209 Neungdong-ro, Gwangjin-gu, 05006, Seoul, Republic of Korea +1

Query Complexity Quantum Kernel Methods

Ask PDF

Apr 12, 2026cs.LG

Query Lower Bounds for Diffusion Sampling

Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the first score query lower bounds for diffusion sampling. We prove that for

d

-dimensional distributions, given access to score estimates with polynomial accuracy

\varepsilon=d^{-O(1)}

(in any

L^p

sense), any sampling algorithm requires

\widetildeΩ(\sqrt{d})

adaptive score queries. In particular, our proof shows that, within any polynomial total-query budget, successful sampling requires searching over

\widetildeΩ(\sqrt{d})

distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.

Zhiyang Xun, Eric Price

UT Austin

Query Complexity Diffusion Sampling Information-Theoretic Lower Bounds Diffusion Models

Ask PDF

Jan 26, 2026cs.IR

The $\mathbf{P}$ -Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs

Modern AI agents increasingly rely on search infrastructure to execute complex, neuro-symbolic reasoning workflows. These workflows often compile into deeply nested, non-monotonic Boolean queries over text fields. However, standard query evaluation strategies over inverted indices face severe theoretical limits when handling these structures. Stateful iterator models (Document-at-a-Time) are structurally bounded by

\text{NC}^1

formula evaluation, suffering a worst-case

O(2^{|Q|})

exponential blowup in query complexity when unrolling re-convergent logic. Conversely, recursive materialization models (Term-at-a-Time) incur an

Ω(|U|)

space complexity penalty (the Universal Scan) when evaluating logical negation over the document universe. In this paper, we establish the theoretical boundaries of executing complex logic natively over an inverted index. We formalize a retrieval language (

\mathcal{L}_R

) based on Directed Acyclic Graphs (DAGs) and prove that its evaluation problem is strictly \textbf{

\mathbf{P}

-Complete}. To make evaluation tractable, we introduce \texttt{ComputePN}, a deterministic, sparsity-aware evaluation algorithm. By decoupling logical negation from universe-scale materialization via a novel Positive-Negative dual representation, and utilizing native DAG memoization, \texttt{ComputePN} strictly bounds evaluation time to

O(|Q| \cdot |U_{\mathit{active}}|)

. This approach successfully evaluates

\mathbf{P}

-Complete queries natively over the index, avoiding both the combinatorial tree-expansion bottleneck and the universal scan penalty, laying the formal foundation for computational retrieval.

Amir Aavani

Apple Inc., USA

Query Complexity Information Retrieval IR Evaluation

Ask PDF

Nov 17, 2025cs.LG

On the Gradient Complexity of Private Optimization with Private Oracles

We study the running time, in terms of first order oracle queries, of differentially private empirical/population risk minimization of Lipschitz convex losses. We first consider the setting where the loss is non-smooth and the optimizer interacts with a private proxy oracle, which sends only private messages about a minibatch of gradients. In this setting, we show that expected running time

Ω(\min\{\frac{\sqrt{d}}{α^2}, \frac{d}{\log(1/α)}\})

is necessary to achieve

α

excess risk on problems of dimension

d

when

d \geq 1/α^2

. Upper bounds via DP-SGD show these results are tight when

d>\tildeΩ(1/α^4)

. We further show our lower bound can be strengthened to

Ω(\min\{\frac{d}{\bar{m}α^2}, \frac{d}{\log(1/α)} \})

for algorithms which use minibatches of size at most

\bar{m} < \sqrt{d}

. We next consider smooth losses, where we relax the private oracle assumption and give lower bounds under only the condition that the optimizer is private. Here, we lower bound the expected number of first order oracle calls by

\tildeΩ\big(\frac{\sqrt{d}}α + \min\{\frac{1}{α^2}, n\}\big)

, where

n

is the size of the dataset. Modifications to existing algorithms show this bound is nearly tight. Compared to non-private lower bounds, our results show that differentially private optimizers pay a dimension dependent runtime penalty. Finally, as a natural extension of our proof technique, we show lower bounds in the non-smooth setting for optimizers interacting with information limited oracles. Specifically, if the proxy oracle transmits at most

Γ

-bits of information about the gradients in the minibatch, then

Ω\big(\min\{\frac{d}{α^2Γ}, \frac{d}{\log(1/α)}\}\big)

oracle calls are needed. This result shows fundamental limitations of gradient quantization techniques in optimization.

Michael Menart, Aleksandar Nikolov

Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto

Query Complexity Oracle Complexity Differentially Private Stochastic Gradient Descent Differential Privacy Nonsmooth Convex Optimization Empirical Risk Minimization

Ask PDF

Sep 25, 2025cs.DS

Actively Learning Halfspaces without Synthetic Data

In the classic point location problem, one is given an arbitrary dataset

X \subset \mathbb{R}^d

n

points with query access to an unknown halfspace

f : \mathbb{R}^d \to \{0,1\}

, and the goal is to learn the label of every point in

X

. This problem is extremely well-studied and a nearly-optimal

\widetilde{O}(d \log n)

query algorithm is known due to Hopkins-Kane-Lovett-Mahajan (FOCS 2020). However, their algorithm is granted the power to query arbitrary points outside of

X

(point synthesis), and in fact without this power there is an

Ω(n)

query lower bound due to Dasgupta (NeurIPS 2004). In this work our goal is to design efficient algorithms for learning halfspaces without point synthesis. To circumvent the

Ω(n)

lower bound, we consider learning halfspaces whose normal vectors come from a set of size

D

, and show tight bounds of

Θ(D + \log n)

. As a corollary, we obtain an optimal

O(d + \log n)

query deterministic learner for axis-aligned halfspaces, closing a previous gap of

O(d \log n)

vs.

Ω(d + \log n)

. In fact, our algorithm solves the more general problem of learning a Boolean function

f

over

n

elements which is monotone under at least one of

D

provided orderings. Our technical insight is to exploit the structure in these orderings to perform a binary search in parallel rather than considering each ordering sequentially, and we believe our approach may be of broader interest. Furthermore, we use our exact learning algorithm to obtain nearly optimal algorithms for PAC-learning. We show that

O(\min(D + \log(1/\varepsilon), 1/\varepsilon) \cdot \log D)

queries suffice to learn

f

within error

\varepsilon

, even in a setting when

f

can be adversarially corrupted on a

c\varepsilon

-fraction of points, for a sufficiently small constant

c

. This bound is optimal up to a

\log D

factor, including in the realizable setting.

Hadley Black, Kasper Green Larsen, Arya Mazumdar +2

Baruch College, CUNY · Aarhus University · University of California, San Diego

Query Complexity Boolean Function Learning Active Learning PAC Learning

Ask PDF

Sep 17, 2024cs.DS

Clustering with Non-adaptive Subset Queries

Recovering the underlying

k

-clustering of a set

U

n

points by asking pair-wise same-cluster queries has garnered significant interest in the past few years. Given a query

S \subset U

|S|=2

, the oracle returns "yes" if the points are in the same cluster and "no" otherwise. For adaptive algorithms, the query complexity is known to be

Θ(nk)

, while non-adaptive algorithms are extremely limited: even for

k=3

, such algorithms require

Ω(n^2)

queries, matching the trivial upper bound. However, non-adaptivity is highly desirable since it allows queries to be asked in parallel. To break the quadratic barrier for non-adaptive queries, we study a natural generalization of this problem to subset queries for

|S|>2

, where the oracle returns the number of clusters intersecting

S

. Previous work obtained an

O(n)

query adaptive algorithm, but the realm of non-adaptive algorithms remained completely unknown. In this paper, we give the first non-adaptive algorithms for clustering with subset queries. Our main result is a non-adaptive algorithm making

O(n \log k \cdot (\log k + \log\log n)^2)

queries, improving to

O(n \log \log n)

when

k

is constant. In addition to non-adaptivity, we make other practical considerations, such as enforcing a bound,

s

, on the query size. We show

Ω(\max(n^2/s^2,n))

queries are necessary and obtain algorithms making

\smash{\widetilde{O}(n^2k/s^2)}

queries for any

s \leq \sqrt{n}

and

\smash{\widetilde{O}(n^2/s)}

queries for any

s \leq n

. Finally, we obtain improved upper bounds when the clusters are roughly balanced, and when the algorithm is allowed two rounds of adaptivity.

Hadley Black, Euiwoong Lee, Arya Mazumdar +1

CUNY Baruch College · University of Michigan · UC San Diego

Query Complexity Clustering

Ask PDF

Momentum

Related topics

Latest papers 23