Query Complexity

Ask about this topic

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
View on map

Latest papers 23

All topics
CardsList

  1. Lower Bounds for Parallel Diffusion Sampling

    Oct 6, 2026Yiwen Kou, Yimeng WangDiffusion SamplingQuery Complexity

    UCLA

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

    Sep 30, 2026Koustav De, Debajyoti Kar, Swagato SanyalQuery ComplexitySocial 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

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

    Sep 9, 2026Xuan LiQuery ComplexityOracle Complexity

    University of New South Wales, Sydney, Australia

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

    Sep 9, 2026Shi Fu, Qixin Zhang, Dacheng TaoSubmodular OptimizationQuery Complexity

    Nanyang Technological University, Singapore

  5. 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.

  6. Optimal Unambiguous DNFs and Alon-Saks-Seymour

    Aug 3, 2026Chirag PabbarajuQuery ComplexityCommunication Complexity

    Stanford University.

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

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

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

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

    Jul 30, 2026Jianfeng Lu, Yinchen LuoMarkov Chain Monte CarloQuery Complexity

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

    Jul 21, 2026Michael Menart, Aleksandar Nikolov, Ohad ShamirQuery ComplexityOracle 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

  10. 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

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

  11. Mathematical perspective on genetic algorithms with optimization guided operators

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

    Department of Mathematics, MIT

  12. Optimal Reconstruction from Linear Queries

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

    Technion – Israel Institute of Technology · Google Research

  13. Min-Max Optimization Requires Exponentially Many Queries

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

    Bocconi University · Politecnico di Milano · University of Oxford

  14. Reproducing Complex Set-Compositional Information Retrieval

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

    Radboud University · Nijmegen, NL

  15. Matroid Algorithms Under Size-Sensitive Independence Oracles

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

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

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

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

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

  17. Learning Unanimously Acceptable Lotteries via Queries

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

    Harvard University, USA · University of Oxford, UK

  18. Optimal algorithmic complexity of inference in quantum kernel methods

    Apr 16, 2026Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi +2Query ComplexityQuantum 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

  19. Query Lower Bounds for Diffusion Sampling

    Apr 12, 2026Zhiyang Xun, Eric PriceQuery ComplexityDiffusion Sampling

    UT Austin

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

    Jan 26, 2026Amir AavaniQuery ComplexityInformation Retrieval

    Apple Inc., USA

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

    Nov 17, 2025Michael Menart, Aleksandar NikolovQuery ComplexityOracle Complexity

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

  22. Actively Learning Halfspaces without Synthetic Data

    Sep 25, 2025Hadley Black, Kasper Green Larsen, Arya Mazumdar +2Query ComplexityBoolean Function Learning

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

  23. Clustering with Non-adaptive Subset Queries

    Sep 17, 2024Hadley Black, Euiwoong Lee, Arya Mazumdar +1Query ComplexityClustering

    CUNY Baruch College · University of Michigan · UC San Diego