Randomized query complexity can beat certificate complexity

• URL: http://arxiv.org/abs/2609.15063v1
• Date: Mon, 14 Sep 2026 05:29:42 GMT
• Title: Randomized query complexity can beat certificate complexity
• Abstract summary: We construct a function with R(f) = O(sqrtC(f)), which is optimal up to log factors.<n>The same function also has $Q(f) = O(C(f)1/4), where Q(f) is the bounded-error quantum query complexity of f.
• Score: 1.7889544416325804
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also has $Q(f) = O~(C(f)^{1/4}), where Q(f) is the bounded-error quantum query complexity of f, which is also nearly optimal.

Related papers

• A Near-Quartic Separation Between Certificate Complexity and Quantum Query Complexity [0.0]
  We construct a total Boolean function $f$ for which $Q(f) = widetildeO(sqrt[4]C(f))$, where $Q(f)$ denotes the bounded-error quantum query complexity and $C(f)$ denotes the certificate complexity.
  arXiv  Detail & Related papers  (2026-09-10T15:04:28Z)
• How Hard is it to Decide if a Fact is Relevant to a Query? [1.6058099298620423]
  Given a database D, a Boolean conjunctive query (CQ) q, and fact f in D, decide whether f is relevant to q wrt.<n>We identify self-joins (multiple atoms with the same relation) as the culprit.<n>Our results thus pinpoint what makes relevance harder than query evaluation and identify natural classes of queries which admit efficient relevance computation.
  arXiv  Detail & Related papers  (2026-04-24T10:29:27Z)
• Monte Carlo to Las Vegas for Recursively Composed Functions [0.26709266817192023]
  We study the composition limits of general measures in query complexity.<n>We show this limit converges under reasonable assumptions about the measure.<n>We then give a surprising result regarding the composition limit of randomized query complexity.
  arXiv  Detail & Related papers  (2026-01-12T23:34:37Z)
• Non-Asymptotic Length Generalization [26.982645261213847]
  We provide provable guarantees of length generalization for various classes of functions in an idealized setting.<n>We show the Minimum-Complexity Interpolator learning algorithm achieves optimal length complexity.
  arXiv  Detail & Related papers  (2025-06-03T17:09:34Z)
• Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering [50.1887329564127]
  We propose an efficient and scalable symbolic search framework for complex queries.<n>Our framework reduces the computational load of symbolic methods by 90% while maintaining nearly the same performance.
  arXiv  Detail & Related papers  (2025-05-13T01:24:09Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• The Role of Symmetry in Quantum Query-to-Communication Simulation [3.517404936232172]
  We show that the O(log n) overhead is required for some functions in the quantum setting, and thus the BCW simulation is tight. We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation.
  arXiv  Detail & Related papers  (2020-12-09T18:58:55Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  We design and analyze CascadeBAI, an algorithm for finding the best set of $K$ items. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes.
  arXiv  Detail & Related papers  (2020-01-23T16:47:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.