Query Complexity

Follow this topic Ask about this topic

Query complexity measures the information an algorithm must obtain through queries to an oracle, such as labels, comparisons, gradients, or subset counts. Researchers design adaptive and non-adaptive algorithms, randomized sampling methods, and learning procedures, then prove lower bounds that show when fewer queries cannot suffice. These ideas apply to learning and clustering, convex optimization and sampling, combinatorial problems, and social choice. A central tension is how query needs change with the access model, rounds, memory, and whether guarantees are worst-case or distribution-specific.

Latest papers

31 papers5 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Query Complexity of Learning Axis-Aligned Partitions
Oct 26, 2026Hadley Black, Arya Mazumdar, Barna Saha +1Query Complexity Active Learning
Baruch College, CUNY. · UC San Diego. · ETH Zürich.
Pre-Query Retention with Bounded Bit and Word Retrieval
Oct 18, 2026Pranav Singh, Prashant SinghAgent Memory Query Complexity
Indian Institute of Technology Ropar, Department of Mathematics, Rupnagar, Punjab, India
Exact Cut Complexity of Equal-Length Proportional Cake Cutting
Oct 14, 2026Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin SanpuiFair Resource Allocation Query Complexity
Chuo University, Tokyo, Japan · Indian Institute of Technology Kharagpur, Kharagpur, West Bengal, India
Verification with Transfer: Exact Information Frontiers and Their Price in Calls
Oct 8, 2026Hazar YuekselInformation-Theoretic Lower Bounds Query Complexity
Lower Bounds for Parallel Diffusion Sampling
Oct 6, 2026Yiwen Kou, Yimeng WangDiffusion Sampling Query Complexity
UCLA
Query-efficient winner prediction in district-based elections
Sep 30, 2026Koustav De, Debajyoti Kar, Swagato SanyalQuery Complexity Social Choice Theory
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
An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order
Sep 9, 2026Xuan LiQuery Complexity Oracle Complexity
University of New South Wales, Sydney, Australia
A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse
Sep 9, 2026Shi Fu, Qixin Zhang, Dacheng TaoSubmodular Optimization Query Complexity
Nanyang Technological University, Singapore
Sorting from Counterexamples
Aug 21, 2026Noga Alon, Shay Moran, Shlomo MoranQuery Complexity Pairwise Ranking
Princeton University, Princeton, NJ 08544, USA, and Tel Aviv University, Tel Aviv 69978, Israel. · Technion – Israel Institute of Technology and Google Research. · Technion – Israel Institute of Technology.
Quality Control Algorithms for Pattern Counting
Aug 4, 2026Cassandra Marcussen, Ronitt Rubinfeld, Madhu SudanQuery Complexity
School of Engineering and Applied Sciences, Harvard University, Cambridge, Massachusetts, USA. · Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, Massachusetts, USA.
Optimal Unambiguous DNFs and Alon-Saks-Seymour
Aug 3, 2026Chirag PabbarajuQuery Complexity Sample Compression
Stanford University.
Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds
Aug 3, 2026Deeparnab Chakrabarty, Aditi Dudeja, David SaulpicQuery Complexity Clustering
Dartmouth College · The Chinese University of Hong Kong (Shenzhen) · CNRS and Universit´e Paris Cit´e
Windowed thinning and query complexity for the bouncy particle and Zigzag samplers
Jul 30, 2026Jianfeng Lu, Yinchen LuoMarkov Chain Monte Carlo Query Complexity
Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory
Jul 21, 2026Michael Menart, Aleksandar Nikolov, Ohad ShamirQuery Complexity Oracle Complexity
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
Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model
Jun 18, 2026Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2Query Complexity Oracle Complexity
University of New South Wales · University of California, Berkeley · University of Sydney
Mathematical perspective on genetic algorithms with optimization guided operators
Jun 10, 2026Anna Brandenberger, Ilan Doron-Arad, Elchanan MosselQuery Complexity Genetic Algorithms
Department of Mathematics, MIT
Optimal Reconstruction from Linear Queries
May 19, 2026Yuval Filmus, Shay Moran, Elizaveta NesterovaQuery Complexity Inverse Problems
Technion – Israel Institute of Technology · Google Research
Min-Max Optimization Requires Exponentially Many Queries
May 13, 2026Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1Query Complexity Oracle Complexity
Bocconi University · Politecnico di Milano · University of Oxford
Reproducing Complex Set-Compositional Information Retrieval
May 5, 2026Vincent Degenhart, Dewi Timman, Arjen P. de Vries +2Query Complexity Lexical Retrieval
Radboud University · Nijmegen, NL
Matroid Algorithms Under Size-Sensitive Independence Oracles
Apr 30, 2026Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +1Query Complexity Oracle Complexity
*Equal contribution 1Department of Computer Science, University of Maryland, College Park, USA.
How Hard is it to Decide if a Fact is Relevant to a Query?
Apr 24, 2026Meghyn Bienvenu, Diego Figueira, Pierre LafourcadeQuery Complexity Relational Databases
Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400, Talence, France
Learning Unanimously Acceptable Lotteries via Queries
Apr 19, 2026Davin Choo, Paul W. Goldberg, Nicholas TehQuery Complexity Learning-Augmented Algorithms
Harvard University, USA · University of Oxford, UK
Optimal algorithmic complexity of inference in quantum kernel methods
Apr 16, 2026Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi +2Query Complexity Quantum Kernel Methods
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 Lower Bounds for Diffusion Sampling
Apr 12, 2026Zhiyang Xun, Eric PriceQuery Complexity Diffusion Sampling
UT Austin
Are LLMs Overkill for Databases?: A Study on the Finiteness of SQL
Mar 26, 2026Yue Li, David Mimno, Unso Eun Seo JoText-to-SQL Query Complexity
Cornell University
Finding Common Ground in a Sea of Alternatives
Mar 17, 2026Jay Chooi, Paul Gölz, Ariel D. Procaccia +2Query Complexity
Paulson School of Engineering and Applied Sciences, Harvard University · School of Operations Research and Information Engineering, Cornell University · Department of Statistics, Harvard University
The $\mathbf{P}$ -Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs
Jan 26, 2026Amir AavaniQuery Complexity Information Retrieval
Apple Inc., USA
On the Gradient Complexity of Private Optimization with Private Oracles
Nov 17, 2025Michael Menart, Aleksandar NikolovQuery Complexity Oracle Complexity
Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto
Actively Learning Halfspaces without Synthetic Data
Sep 25, 2025Hadley Black, Kasper Green Larsen, Arya Mazumdar +2Query Complexity Boolean Function Learning
Baruch College, CUNY · Aarhus University · University of California, San Diego
Quality control in sublinear time: a case study via random graphs
Aug 22, 2025Cassandra Marcussen, Ronitt Rubinfeld, Madhu SudanQuery Complexity
School of Engineering and Applied Sciences, Harvard University, Cambridge, Massachusetts, USA. · Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, Massachusetts, USA.

Oct 26, 2026J/K move · Enter open · S save

Query Complexity of Learning Axis-Aligned Partitions

Hadley Black, Arya Mazumdar, Barna Saha, Geelon So

Baruch College, CUNY. · UC San Diego. · ETH Zürich.

Query Complexity Active Learning

Open paper AskPDF arXiv

This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let

X \subset \mathbb{R}^d

be a set of

n

points, labeled by a collection of

k

boxes: the label of each point in

X

is determined by the unique box containing it. A learner aims to exactly recover the labels for every point in

X

given access to a label oracle. We consider three increasingly-structured settings. In the most general setting, there are no conditions on the boxes, and they may overlap. We show that CAL (Cohn-Atlas-Ladner 1994), a classical active learning algorithm, is minimax-optimal with query complexity

Θ(kd \log (n/kd))

. When the boxes are disjoint, we examine two regimes. In the large-

k

regime, CAL remains minimax-optimal. For the constant-

k

regime, an optimized variant of the Halving algorithm (Hegedüs 1995) can beat CAL by a

\log(d)

factor. Finally, in the most-structured settings, the boxes correspond to the leaves of a constant-sized decision tree. We prove a tight query complexity of

Θ(d + \log n)

that is additive in

d

and

\log n

, generalizing a recent result (Black-Larsen-Mazumdar-Saha-So 2026) that establishes the query complexity of learning decision stumps.