Overview

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

CardsList

33 papers3 papers in the last four weeks, down 40% on the four weeks before. 0.0% of all new papers.

  1. Sketching Language Models for Context Attribution

    Nov 12, 2026Christopher Liaw, Aranyak Mehta, Grigoris Velegkas +1Query ComplexityRandomized Sketching

  2. Randomized Parallel Complexity of Weakly Convex Optimization

    Nov 5, 2026Kang LiuQuery ComplexityNonconvex Optimization

  3. Query Complexity of Learning Axis-Aligned Partitions

    Oct 26, 2026Hadley Black, Arya Mazumdar, Barna Saha +1Query ComplexityActive Learning

  4. Pre-Query Retention with Bounded Bit and Word Retrieval

    Oct 18, 2026Pranav Singh, Prashant SinghAgent MemoryQuery Complexity

  5. Exact Cut Complexity of Equal-Length Proportional Cake Cutting

    Oct 14, 2026Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin SanpuiFair Resource AllocationQuery Complexity

  6. Query-efficient winner prediction in district-based elections

    Sep 30, 2026Koustav De, Debajyoti Kar, Swagato SanyalQuery ComplexitySocial Choice Theory

  7. Sorting from Counterexamples

    Aug 21, 2026Noga Alon, Shay Moran, Shlomo MoranQuery ComplexityPairwise Ranking

  8. Quality Control Algorithms for Pattern Counting

    Aug 4, 2026Cassandra Marcussen, Ronitt Rubinfeld, Madhu SudanQuery Complexity

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

    Aug 3, 2026Deeparnab Chakrabarty, Aditi Dudeja, David SaulpicQuery ComplexityClustering

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

    Jul 21, 2026Michael Menart, Aleksandar Nikolov, Ohad ShamirQuery ComplexityOracle Complexity

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

    Jun 18, 2026Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2Query ComplexityOracle Complexity

  12. Mathematical perspective on genetic algorithms with optimization guided operators

    Jun 10, 2026Anna Brandenberger, Ilan Doron-Arad, Elchanan MosselQuery ComplexityGenetic Algorithms

  13. Optimal Reconstruction from Linear Queries

    May 19, 2026Yuval Filmus, Shay Moran, Elizaveta NesterovaQuery ComplexityInverse Problems

  14. Min-Max Optimization Requires Exponentially Many Queries

    May 13, 2026Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1Query ComplexityOracle Complexity

  15. Reproducing Complex Set-Compositional Information Retrieval

    May 5, 2026Vincent Degenhart, Dewi Timman, Arjen P. de Vries +2Query ComplexityLexical Retrieval

  16. Matroid Algorithms Under Size-Sensitive Independence Oracles

    Apr 30, 2026Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +1Query ComplexityOracle Complexity

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

    Apr 24, 2026Meghyn Bienvenu, Diego Figueira, Pierre LafourcadeQuery ComplexityRelational Databases

  18. Learning Unanimously Acceptable Lotteries via Queries

    Apr 19, 2026Davin Choo, Paul W. Goldberg, Nicholas TehQuery ComplexityLearning-Augmented Algorithms

  19. Optimal algorithmic complexity of inference in quantum kernel methods

    Apr 16, 2026Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi +2Query ComplexityQuantum Kernel Methods

  20. Are LLMs Overkill for Databases?: A Study on the Finiteness of SQL

    Mar 26, 2026Yue Li, David Mimno, Unso Eun Seo JoText-to-SQLQuery Complexity

  21. Finding Common Ground in a Sea of Alternatives

    Mar 17, 2026Jay Chooi, Paul Gölz, Ariel D. Procaccia +2Query Complexity

  22. On the Gradient Complexity of Private Optimization with Private Oracles

    Nov 17, 2025Michael Menart, Aleksandar NikolovQuery ComplexityOracle Complexity