Q The Query Complexity Zoo

References

256 entries, newest first. A citation key is the anchor, so refs.html#Nisan91 works. “Used in” lists the data files that cite it.

  1. ['Ambainis, Andris', 'Iraids, Jānis', 'Kokainis, Martins']. Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity.2026. arXiv:2609.11664
    Read v3, October 5, 2026. Theorems 2.1–2.3: quartic C/Q, log-free quadratic C/R₁, and quadratic C/Q₀ and C/Q_E separations. R₀/Q is also quartic. Builds on Pabbaraju; independent of Ben-David–Kothari.
    used in functions/01-basic.yaml functions/07-recent-separations.yaml measures/01-deterministic.yaml measures/02-randomized.yaml measures/07-sabotage-and-certification.yaml open_problems.yaml relations/04-composition.yaml relations/14-sabotage-and-2026-results.yaml tables/total-exponents.yaml
  2. ['Blanc, G.', 'Docter, J.', 'Strassle, C.', 'Tan, L.-Y.']. Proof of the Aaronson–Ambainis Conjecture: An Exposition.2026. arXiv:2611.11626
    Cleaner exposition of the PSI/Turturean proof, organized into four steps. Parameters are not optimized.
    used in measures/05-fourier.yaml open_problems.yaml
  3. ['Belovs, A.']. Tight quantum lower bound for k-distinctness.2026. arXiv:2604.05133
    Preprint. Closes k-distinctness for constant k and alphabet Omega(n^2) via a compressed-oracle framework that subsumes the polynomial method.
    used in functions/05-more.yaml
  4. ['Ben-David, Shalev', 'Kothari, Robin']. Randomized query complexity can beat certificate complexity.2026. arXiv:2609.15063
    Theorem 1 simultaneously gives C = Ω(n²), R = O(n log n), and Q = Õ(√n). Concurrent independent work of Ambainis, Iraids and Kokainis is credited in the paper.
    used in functions/07-recent-separations.yaml measures/01-deterministic.yaml relations/14-sabotage-and-2026-results.yaml tables/total-exponents.yaml
  5. ['Cornelissen, A.', 'Gilani, A.', 'Patro, S.']. Quantum algorithms for path and cycle containment problems.2026. arXiv:2605.09017
    Preprint. Lemma 3.3/3.4: R(Subgraph^H) = Theta(m^2), Q = Omega(m), and detection equals finding up to constants.
    used in functions/05-more.yaml
  6. ['Gu', 'Y.', 'Li', 'X.', 'Xu', 'Y.']. A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions.COLT 2026, 2026. arXiv:2606.11448
    General N_p lower bound from degree statistics of subgraphs of the hypercube -- the first beyond the trivial N_p >= R. Yields N_p(f) = Omega(I(f) log I(f)) for all total f, settling Open Problem 2 of [Gu25noisy], and recovers most earlier noisy lower bounds up to constants.
    used in concepts.yaml functions/01-basic.yaml functions/06-classical-total.yaml measures/02-randomized.yaml relations/04-composition.yaml
  7. ['Huffstutler, T.', 'Miloschewsky, D.', 'Podder, S.']. A short proof of the Aaronson-Ambainis Conjecture via the completion framework.2026. arXiv:2611.12795
    Shorter completion-based exposition. For partial Boolean f with domain density δ, obtains a deterministic O(Q(f)^6/(εδ)^2)-query algorithm correct on at least a 1−ε fraction of the domain. Also derives the bounded-polynomial influence formulation.
    used in measures/05-fourier.yaml open_problems.yaml
  8. ['Kothari', 'R.', 'Kovacs-Deak', 'M.', 'Wang', 'D.', 'Yang', 'R. Z.']. Rational degree is polynomially related to degree.2026. arXiv:2601.08727
    also cited here as KKW+26, KovacsDeak26
    Answers Fortnow's 1994 question affirmatively: D <= 16 rdeg^4, and deg = O~(rdeg^3). Fills in the whole rdeg column, which had read '?' since the question was posed.
    used in functions/02-composed.yaml measures/04-degree.yaml open_problems.yaml relations/02-degree.yaml tables/total-exponents.yaml
  9. ['Kayal, Chandrima', 'Laplante, Sophie', 'Larroque, Émile', 'Prūsis, Krišjānis', 'Vihrovs, Jevgēnijs']. Certification complexity of Boolean functions.2026. arXiv:2609.26757
    Read v1, September 22, 2026. The degree measures, including degree certification, require bounded polynomials on the whole Boolean cube, even outside a promise.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/07-recent-separations.yaml measures/01-deterministic.yaml measures/03-quantum.yaml measures/07-sabotage-and-certification.yaml open_problems.yaml relations/14-sabotage-and-2026-results.yaml tables/total-exponents.yaml
  10. ['Meiburg', 'A.']. Block Sensitivity can exceed Spectral Sensitivity Squared.2026. arXiv:2608.00851
    Refutes the ABKRT question 'is bs = O(lambda^2)?'. Total function on 2017584 variables with bs >= 14011, lambda <= 89.0162, so bs >= lambda^{2.127}. Formally verified in Lean.
    used in functions/01-basic.yaml functions/02-composed.yaml measures/03-quantum.yaml relations/14-sabotage-and-2026-results.yaml
  11. ['Meiburg, A.']. No Perfect Randomized Composition.2026. arXiv:2610.31638
    Read v1 (October 22, 2026). Total–total R composition loses Θ(log R(g)) = Θ(log log L), where L is the composed input length (Theorem 1.1). Separates every adjacent pair RS, max-conflict, LR, R on total functions; separates noisyR from R; makes conflict and sabotage incomparable. For AND-of-ORs use the proved Theorem 9.1 bracket Ω(m²/log²m) ≤ χ ≤ O(m²/√log m), rather than the stronger upper bound printed in the introduction table. Also proves χ is not O(C) and a maximal R* / R = Θ(log R) gap.
    used in concepts.yaml functions/02-composed.yaml functions/07-recent-separations.yaml measures/02-randomized.yaml open_problems.yaml relations/04-composition.yaml relations/11-lp-and-lower-bound-methods.yaml relations/14-sabotage-and-2026-results.yaml
  12. ['OpenAI']. A Nearly Quartic Separation Between Randomized and Quantum Query Complexity.2026. link
    October 5, 2026 preprint. Theorem 1.1 settles the optimal R-versus-Q power at 4 for total Boolean functions. For every fixed k≥2, Q(F_{k,m})≤C_k sqrt(m)(log m)^{b_k}, R(F_{k,m})≥c_k m^{2−1/k}/(log m)^2, giving exponents 4−2/k with polylogarithmic losses. Letting k range rules out every universal exponent below 4. The statement is an optimal-exponent theorem, not a fixed-k literal Ω̃(Q^4) bound. Will Cook provides a great exposition and a Lean proof, with instructions for reproducing the formal checks.
    used in functions/07-recent-separations.yaml measures/02-randomized.yaml measures/03-quantum.yaml open_problems.yaml relations/03-quantum.yaml tables/total-exponents.yaml
  13. ['OpenAI']. A superquadratic separation between sensitivity and block sensitivity.2026. link
    September 25, 2026. Theorem 1.1 refutes every universal quadratic bound; Corollary 4.3 obtains a fixed exponent α>2 by self-composition. Adapts Meiburg’s tournament architecture to ordinary sensitivity.
    used in concepts.yaml functions/07-recent-separations.yaml measures/01-deterministic.yaml open_problems.yaml tables/total-exponents.yaml
  14. ['Pabbaraju, Chirag']. Optimal Unambiguous DNFs and Alon-Saks-Seymour.SODA 2027 (camera-ready preprint), 2026. arXiv:2608.02533
    Read v2, October 15, 2026. Theorem 4 proves a quartic C/approximate-degree separation, not a quantum query upper bound. Theorem 1 and Corollaries 1.2–1.3 remove logarithms in other certificate separations.
    used in functions/07-recent-separations.yaml measures/01-deterministic.yaml relations/01-classical-core.yaml relations/14-sabotage-and-2026-results.yaml tables/total-exponents.yaml
  15. ['Pednekar, S.', 'Podder, S.']. A General Composition Theorem for Approximate Degree.2026. arXiv:2609.30139
    Read v2 (October 23, 2026). Proves constant-factor composition of approximate degree for all total Boolean functions and refutes multiplicative exact quantum query composition. The expanded STOC 2027 submission [PednekarPodder26STOC] also proves randomized composition with a log(n+1) loss for possibly partial Boolean functions.
    used in concepts.yaml measures/03-quantum.yaml measures/04-degree.yaml open_problems.yaml relations/04-composition.yaml
  16. ['Pednekar, S.', 'Podder, S.']. On the Composition Theorem for Approximate Degree, Randomized and Exact Quantum Query Complexity.STOC 2027 submission, 2026. link
    Expanded submission version of [PednekarPodder26composition], paper 1312. Theorem 31: R(f) ≤ C log(n+1) noisyR(f) for nonconstant partial Boolean f on n bits, hence R(f∘g) = Ω(R(f)R(g)/log(n+1)) for possibly partial Boolean f,g. The loss depends on the outer input size, not R(f). Theorem 33 refutes constant-factor exact quantum query composition on total functions.
    used in concepts.yaml measures/02-randomized.yaml measures/03-quantum.yaml open_problems.yaml relations/04-composition.yaml
  17. ['Prove2Me campaign contributors (including yousofy; see source attribution)']. Block Sensitivity vs. Sensitivity: exact exponent log(14055^8)/log(3738277295413674).2026. link
    Public theorem marked Proved, October 20, 2026; inspected October 22, 2026. Campaign: https://prove2.me/campaigns/block-sensitivity-vs-sensitivity. Exponent 2.1308255793978239476… . The displayed statement quantifies over every ε>0 and sensitivity threshold S≥2. Attribution to Robin Kothari and OpenAI’s earlier construction is retained in the proof source. Verification status is reported by Prove2Me; the zoo did not independently replay the Lean proof.
    used in concepts.yaml functions/07-recent-separations.yaml measures/01-deterministic.yaml open_problems.yaml relations/01-classical-core.yaml relations/14-sabotage-and-2026-results.yaml tables/total-exponents.yaml
  18. ['Physical Superintelligence (PSI)']. The Aaronson–Ambainis conjecture.2026. link
    PSI announcement and proof attribution. David Turturean discovered the proof using PSI’s research system. Original paper: [Turturean26]. Cleaner expositions: [BDST26AA] (arXiv:2611.11626) and [HMP26AA] (arXiv:2611.12795).
    used in measures/05-fourier.yaml open_problems.yaml relations/05-fourier.yaml
  19. ['Turturean, D.']. A Proof of the Aaronson–Ambainis Conjecture.2026. arXiv:2611.09773
    PSI’s original proof. For bounded degree-d functions, max influence ≥ c Var(f)^(5/2)/d^6 with an absolute c>0, using the paper’s influence normalization. In the [0,1]-valued formulation this yields an influence ≥ (Var(f)/d)^7. Cleaner expositions appear in [BDST26AA] (arXiv:2611.11626) and [HMP26AA] (arXiv:2611.12795); the latter gives a completion-based proof and an O(Q^6/(εδ)^2) simulation for a domain of density δ.
    used in measures/05-fourier.yaml open_problems.yaml relations/05-fourier.yaml
  20. ['Carolan, J.', 'Childs, A. M.', 'Kovacs-Deak, M.', 'Schaeffer, L.']. Translation-invariant quantum algorithms for ordered search are optimal.ACM Transactions on Quantum Computing, 2025. arXiv:2503.21090doi
    Every bounded-error k-query ordered-search algorithm can be made translation-invariant and workspace-free; an LP search then gives an exact 5-query algorithm for 7265 items, i.e. 0.390 log_2 n.
    used in functions/05-more.yaml
  21. ['Gu', 'Y.', 'Li', 'X.', 'Xu', 'Y.']. Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold.COLT 2025, 2025. arXiv:2502.04632
    N_p(f) = Theta(n log n) for every f with total influence Omega(n). Asks (Open Problem 2) whether the influence-based bound holds at all scales, i.e. N_p(f) = Omega(I(f) log I(f)); settled by [GLX26noisy].
    used in concepts.yaml measures/02-randomized.yaml measures/05-fourier.yaml relations/04-composition.yaml
  22. ['Hamoudi', 'Y.']. A Brief Introduction to Quantum Query Complexity.2025. arXiv:2508.08852
    not currently cited by any entry
  23. ['Jeffery, S.', 'Zur, S.']. Multidimensional quantum walks, with application to k-distinctness.STOC 2023, pp. 1125-1130; journal version in TheoretiCS, 2025. arXiv:2208.13492doi
    Extends the electric network framework; solves welded trees in O(n) queries and O(n^2) time, and gives an O~(n^{3/4 - 1/(4(2^k-1))})-time k-distinctness algorithm.
    used in functions/05-more.yaml
  24. ['Belovs, A.']. Global phase helps in quantum search: yet another look at the welded tree problem.arXiv preprint, 2024. arXiv:2404.19476
    A two-page proof of the optimal linear hitting time, via transducers and a modified electric quantum walk.
    used in functions/05-more.yaml
  25. ['Ben-David', 'S.', 'Kundu', 'S.']. Separations in query complexity for total search problems.2024. arXiv:2410.16245
    Alias of [BenDavidKundu24search]; kept because earlier data files cite this key.
    not currently cited by any entry
  26. ['Ben-David', 'S.', 'Kundu', 'S.']. Separations in query complexity for total search problems.2024. arXiv:2410.16245
    Query-complexity analogue of TFNP. Exponential Q vs deg-tilde and deg-tilde vs Adv separations for total search problems; translations relation <-> partial function; reproves [AmbainisBelovs23].
    used in concepts.yaml functions/04-partial-and-relations.yaml measures/04-degree.yaml measures/06-lp.yaml relations/06-settings.yaml
  27. ['Branzei, S.', 'Choo, D.', 'Recker, N. J.']. The sharp power law of local search on expanders.SODA 2024, pp. 1792-1809, 2024. arXiv:2305.08269doi
    Randomized local search on constant-degree expanders is Omega(sqrt n / log n), matching Aldous up to a log.
    used in functions/05-more.yaml
  28. ['Branzei, S.', 'Recker, N. J.']. A note on quantum lower bounds for local search via congestion and expansion.arXiv preprint, 2024. arXiv:2412.13345
    Q(LS_G) = Omega(n^{3/4}/sqrt g) with g the vertex congestion; Omega(n^{1/4}/sqrt(log n)) on constant-degree expanders, improving Santha-Szegedy's n^{1/8}/log n.
    used in functions/05-more.yaml
  29. ['Cornelissen, Arjan', 'Mande, Nikhil S.', 'Patro, Subhasree']. Quantum Sabotage Complexity.2024. arXiv:2408.12595
    Sections 1.1 and 3 define four variants, not just two: weak/strong oracle access and decision/index output. Appendix B supplies the strong-model Index lower bound.
    used in concepts.yaml functions/01-basic.yaml measures/03-quantum.yaml measures/07-sabotage-and-certification.yaml open_problems.yaml relations/14-sabotage-and-2026-results.yaml
  30. ['Li, G.', 'Li, L.', 'Luo, J.']. Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem.SODA 2024, pp. 2454-2480; Algorithmica 87 (2025), 2024. arXiv:2304.08395doi
    A plain coined quantum walk run for a classically precomputed number of steps, plus exact amplitude amplification: zero error in O(n^{1.5} log n) queries.
    used in functions/05-more.yaml
  31. ['Sanyal', 'S.']. Randomized Query Composition and Product Distributions.STACS 2024; ACM Transactions on Computation Theory (2025), 2024. arXiv:2401.15352ECCC TR24-016
    RS(g) = Omega-tilde(D^prod(g)) for total g, hence R(f o g^n) = Omega-tilde(R(f) D^prod(g)). Also the first polynomial separation of R from D^prod, on the balanced NAND tree, which shows that lower bound is not tight.
    used in functions/02-composed.yaml functions/05-more.yaml functions/06-classical-total.yaml measures/01-deterministic.yaml measures/02-randomized.yaml open_problems.yaml relations/04-composition.yaml relations/11-lp-and-lower-bound-methods.yaml
  32. ['Ambainis', 'A.', 'Belovs', 'A.']. An exponential separation between quantum query complexity and the polynomial degree.CCC 2023, 2023. arXiv:2301.09218doi
    Partial function with Q(f) exponentially larger than the EXACT degree deg(f): threshold satisfiability over Z_q has deg = 9 (a cubic count composed with a fixed cubic univariate) while Q = Omega(n^{1/3}). The deg-tilde statement is the immediate corollary, since deg-tilde <= deg. Killed the hope that either degree measure characterises Q for promise problems.
    used in concepts.yaml functions/04-partial-and-relations.yaml relations/06-settings.yaml
  33. ['Bun, M.', 'Voronova, N.']. Approximate degree lower bounds for oracle identification problems.TQC 2023, 1:1-1:19, 2023. arXiv:2303.03921doi
    Approximate degree Omega(m / log^2 m) for ordered search on 2^m inputs, and for the k-of-n oracle identification problems.
    used in functions/05-more.yaml
  34. ['Chattopadhyay', 'A.', 'Dahiya', 'Y.', 'Mahajan', 'M.']. Query Complexity of Search Problems.MFCS 2023; computational complexity (2025), 2023. ECCC TR23-039doi
    Multi-output/relational versions of s, bs, C. Cubic relation D(S) = O(psD(S)^3) for total search problems, improving the quartic bound of [GGR13].
    used in concepts.yaml functions/01-basic.yaml functions/04-partial-and-relations.yaml measures/01-deterministic.yaml measures/02-randomized.yaml relations/06-settings.yaml relations/13-definitional.yaml
  35. ['Chakraborty', 'S.', 'Gal, A.', 'Laplante', 'S.', 'Mittal', 'R.', 'Sunny', 'A.']. Certificate Games (and Consequences for the Classical Adversary Bound).ITCS 2023; extended version with M. Goos, 2025, 2023. arXiv:2211.03396
    CG, CG^pub, CG^*, CG^ns. CG^pub = Theta(classical adversary). Single-bit private-coin version = lambda^2; single-bit public-coin version = Theta(s).
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/04-partial-and-relations.yaml functions/05-more.yaml functions/06-classical-total.yaml measures/01-deterministic.yaml measures/02-randomized.yaml measures/03-quantum.yaml relations/10-new-measures.yaml relations/11-lp-and-lower-bound-methods.yaml
  36. ['Childs, A. M.', 'Coudron, M.', 'Gilani, A. S.']. Quantum algorithms and the power of forgetting.ITCS 2023, 37:1-37:22, 2023. arXiv:2211.12447doi
    The path-finding version of welded trees is hard for any quantum algorithm that only queries a connected subgraph containing the entrance.
    used in functions/05-more.yaml
  37. ['Chakraborty', 'S.', 'Kayal', 'C.', 'Mittal', 'R.', 'Paraashar', 'M.', 'Sanyal', 'S.', 'Saurabh', 'N.']. On the Composition of Randomized Query Complexity and Approximate Degree.APPROX/RANDOM 2023, 2023. arXiv:2307.03900
    Composition of R holds whenever R(f) = Theta(n) or f is (weakly) symmetric; first inner composition theorem for approximate degree, deg~(f o g) = Omega~(sqrt(bs(f)) deg~(g)).
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml functions/05-more.yaml functions/06-classical-total.yaml open_problems.yaml relations/04-composition.yaml
  38. ['Chugh', 'R.', 'Podder', 'S.', 'Sanyal', 'S.']. Decision Tree Complexity versus Block Sensitivity and Degree.FSTTCS 2023, 2023. arXiv:2209.08042
    Asks whether D = O(bs^3) and D = O(deg^3) are tight, and proves the quadratic bounds for graph properties, for functions of bounded alternation, and for 'zebra' functions. Records what a quadratic answer would buy: D = O(R^2), Q = O-tilde(fbs^2), R0 = O(fbs^2), D = O(s^4) and D = O(QE^2).
    used in open_problems.yaml
  39. ['Iyer', 'V.', 'Jain', 'S.', 'Kothari', 'R.', 'Kovacs-Deak', 'M.', 'Kumar', 'V. M.', 'Schaeffer', 'L.', 'Wang', 'D.', 'Whitmeyer', 'M.']. On the Rational Degree of Boolean Functions and Applications.2023. arXiv:2310.08004
    also cited here as IJK+23, Iyer23
    Introduces rdeg, and collects the best known separation and upper-bound exponents between the classical and quantum measures.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/04-partial-and-relations.yaml measures/03-quantum.yaml measures/04-degree.yaml open_problems.yaml relations/02-degree.yaml relations/09-chain.yaml tables/total-exponents.yaml
  40. ['Sherstov, A. A.', 'Thaler, J.']. Vanishing-error approximate degree and QMA complexity.Chicago Journal of Theoretical Computer Science 2023, article 3, 2023. arXiv:1909.07498
    eps-dependence: SURJ is Theta-tilde(n^{3/4} log^{1/4}(1/eps)), ED is Theta(n^{2/3} log^{1/3}(1/eps)).
    used in functions/04-partial-and-relations.yaml functions/05-more.yaml
  41. ['Ben-David', 'S.', 'Blais', 'E.', 'Goos, M.', 'Maystre', 'G.']. Randomised Composition and Small-Bias Minimax.FOCS 2022, 2022. arXiv:2208.12896
    Linearised complexity LR: R(f o g) = Omega(R(f) LR(g)), and LR is the largest such inner measure. Also defines R* = lim_k R(f^{o k})^{1/k} in the open problems, and shows Yao's small-bias minimax fails at eps = 1/2 - o(1).
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml functions/05-more.yaml functions/07-recent-separations.yaml measures/01-deterministic.yaml measures/02-randomized.yaml open_problems.yaml relations/04-composition.yaml relations/07-parameters.yaml relations/11-lp-and-lower-bound-methods.yaml
  42. ['Bun', 'M.', 'Thaler', 'J.']. Approximate Degree in Classical and Quantum Computing.Foundations and Trends in Theoretical Computer Science 15(3-4), 2022. doi
    Book-length survey of approximate degree; the reference for everything deg-tilde.
    used in functions/01-basic.yaml functions/05-more.yaml measures/04-degree.yaml open_problems.yaml relations/10-new-measures.yaml
  43. ['Yamakawa', 'T.', 'Zhandry', 'M.']. Verifiable Quantum Advantage without Structure.FOCS 2022, 2022. arXiv:2204.02063
    Total NP search problem (a relation) with exponential quantum query advantage, even against the uniform distribution.
    used in functions/04-partial-and-relations.yaml
  44. ['Anshu', 'A.', 'Ben-David', 'S.', 'Kundu', 'S.']. On query-to-communication lifting for adversary bounds.CCC 2021, 2021. arXiv:2012.03415doi
    Two query-side corollaries the zoo uses directly: Adv(f) = O(deg-tilde(f)^2), so the positive-weight adversary can never beat the polynomial method by more than a square; and CAdv(f) = Omega(cbs(f)), so the classical adversary dominates critical block sensitivity. Both hold for partial f. The lifting theorem itself takes CAdv to randomized communication complexity with a constant-size gadget.
    used in functions/04-partial-and-relations.yaml functions/05-more.yaml relations/03-quantum.yaml relations/06-settings.yaml relations/10-new-measures.yaml relations/11-lp-and-lower-bound-methods.yaml
  45. ['Aaronson', 'S.', 'Ben-David', 'S.', 'Kothari', 'R.', 'Rao', 'S.', 'Tal', 'A.']. Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem.STOC 2021, 2021. arXiv:2010.12629
    also cited here as ABK+21
    Introduces spectral sensitivity lambda. deg <= lambda^2, lambda <= deg, lambda = O(deg-tilde), lambda <= sqrt(s0 s1), s <= lambda^2, deg = O(deg-tilde^2), D = O(Q^4), D = O(deg-tilde^4).
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/03-separating-total.yaml functions/07-recent-separations.yaml measures/01-deterministic.yaml measures/03-quantum.yaml measures/04-degree.yaml open_problems.yaml relations/02-degree.yaml relations/03-quantum.yaml relations/14-sabotage-and-2026-results.yaml tables/total-exponents.yaml
  46. ['Atia, Y.', 'Chakraborty, S.']. Improved upper bounds for the hitting times of quantum walks.Physical Review A 104:032215, 2021. arXiv:2005.04062doi
    used in functions/05-more.yaml
  47. ['Bansal', 'N.', 'Sinha', 'M.']. k-Forrelation Optimally Separates Quantum and Classical Query Complexity.STOC 2021, 2021. arXiv:2008.07003
    also cited here as BS21
    Q(f) = k vs R(f) = Omega-tilde(n^{1-1/k}).
    used in concepts.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml measures/03-quantum.yaml open_problems.yaml relations/03-quantum.yaml relations/06-settings.yaml
  48. ['Balodis', 'K.', 'Ben-David', 'S.', 'Goos, M.', 'Jain', 'S.', 'Kothari', 'R.']. Unambiguous DNFs and Alon-Saks-Seymour.FOCS 2021, 2021. arXiv:2102.08348doi
    also cited here as BBG+22
    Cited as [BBG+22] in the Iyer et al. table. Source of the current best C-vs-s (cubic), C-vs-lambda (quartic), C-vs-deg (quadratic) and C-vs-deg-tilde (cubic) separations.
    used in functions/03-separating-total.yaml tables/total-exponents.yaml
  49. ['Bravyi', 'S.', 'Gosset', 'D.', 'Grier', 'D.', 'Schaeffer', 'L.']. Classical algorithms for Forrelation.2021. arXiv:2102.06963
    Matching classical upper bound showing the SSW separation is optimal.
    used in functions/04-partial-and-relations.yaml
  50. ['Bun, M.', 'Thaler, J.']. The large-error approximate degree of AC^0.Theory of Computing 17(7):1-46 (APPROX/RANDOM 2019), 2021. doi
    Threshold degree of surjectivity: Theta-tilde(min{R, sqrt N}).
    used in functions/05-more.yaml
  51. ['Goldwasser', 'S.', 'Impagliazzo', 'R.', 'Pitassi', 'T.', 'Santhanam', 'R.']. On the pseudo-deterministic query complexity of NP search problems.CCC 2021, 2021. ECCC TR21-003
    Exponential separation between randomized and pseudo-deterministic query complexity; Omega(sqrt n) psD lower bound for SearchCNF.
    used in functions/04-partial-and-relations.yaml measures/02-randomized.yaml relations/06-settings.yaml
  52. ['Goos, M.', 'Maystre', 'G.']. A Majority Lemma for Randomised Query Complexity.CCC 2021, 2021. ECCC TR21-024
    used in concepts.yaml measures/02-randomized.yaml relations/04-composition.yaml
  53. ['Sherstov', 'A. A.', 'Storozhenko', 'A. A.', 'Wu', 'P.']. An Optimal Separation of Randomized and Quantum Query Complexity.STOC 2021; SIAM Journal on Computing, 2021. arXiv:2008.10223
    also cited here as SSW23
    Q(f) <= k vs R(f) = Omega-tilde(n^{1 - 1/2k}); optimal by Aaronson-Ambainis / BGGS.
    used in concepts.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml measures/03-quantum.yaml open_problems.yaml relations/03-quantum.yaml relations/06-settings.yaml
  54. ['Bassilakis', 'A.', 'Drucker', 'A.', 'Goos, M.', 'Hu', 'L.', 'Ma', 'W.', 'Tan', 'L.-Y.']. The Power of Many Samples in Query Complexity.ICALP 2020, LIPIcs 168, 9:1-9:18, 2020. arXiv:2002.10654
    also cited here as BDG+20
    Concurrent with and independent of BenDavidBlais20composition. R(f o g) = Omega(fbs(f) R(g)), strengthening the Goos-Jayram-Pitassi-Watson bound Omega(s(f) R(g)); also direct-sum-style results on solving many copies of g.
    used in concepts.yaml measures/02-randomized.yaml relations/04-composition.yaml
  55. ['Belovs', 'A.', 'Lee', 'T.']. The quantum query complexity of composition with a relation.2020. arXiv:2004.06439
    Adversary bound for relations; perfect composition of a relation with a Boolean function.
    used in measures/03-quantum.yaml
  56. ['Ben-David', 'S.', 'Blais', 'E.']. A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions.FOCS 2020, 2020. arXiv:2002.10809
    R(f o g) = Omega(noisyR(f) R(g)); noisyR is the largest outer measure with this property; also disproves the randomized composition conjecture for partial functions.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/04-partial-and-relations.yaml functions/05-more.yaml measures/02-randomized.yaml open_problems.yaml relations/04-composition.yaml relations/13-definitional.yaml
  57. ['Ben-David', 'S.', 'Blais', 'E.']. A New Minimax Theorem for Randomized Algorithms.FOCS 2020; Journal of the ACM 70(6) (2023), 2020. arXiv:2002.10802
    A single hard distribution that works at every bias level simultaneously; introduces noisy randomized query complexity noisyR and the forecasting-algorithm view.
    used in concepts.yaml functions/04-partial-and-relations.yaml measures/01-deterministic.yaml measures/02-randomized.yaml relations/04-composition.yaml
  58. ['Carette, T.', 'Lauriere, M.', 'Magniez, F.']. Extended learning graphs for triangle finding.Algorithmica 82:1989-2005, 2020. arXiv:1609.07786
    Current record: O(m^{5/4}) with no logarithmic factors.
    used in functions/05-more.yaml
  59. ['Mande, N. S.', 'Thaler, J.', 'Zhu, S.']. Improved approximate degree bounds for k-distinctness.TQC 2020, LIPIcs 158, 2:1-2:22, 2020. arXiv:2002.08389doi
    used in functions/05-more.yaml
  60. ['Sherstov', 'A. A.']. Algorithmic polynomials.SIAM Journal on Computing 49(6), 2020. arXiv:1801.04607
    Near-optimal approximate degree upper bounds for surjectivity, element distinctness, etc.
    used in functions/05-more.yaml
  61. ['Tal', 'A.']. Towards Optimal Separations between Quantum and Randomized Query Complexities.FOCS 2020, 2020. arXiv:1912.12561
    Q = O(1) vs R = Omega(n^{2/3-eps}) via Fourier growth of decision trees.
    used in functions/04-partial-and-relations.yaml measures/05-fourier.yaml
  62. ['Anshu, A.', 'Boddu, N. G.', 'Touchette, D.']. Quantum log-approximate-rank conjecture is also false.FOCS 2019, pp. 982-994, 2019. arXiv:1811.10525doi
    used in functions/06-classical-total.yaml
  63. ['Blais', 'E.', 'Brody', 'J.']. Optimal Separation and Strong Direct Sum for Randomized Query Complexity.CCC 2019, 2019. arXiv:1908.01020
    Bounded-error separation theorem: a total f with Rbar_eps(f) = Omega(R(f) log(1/eps)), so the amplification log factor is necessary. Strong direct sum: Rbar_eps(f^k) = Theta(k Rbar_{eps/k}(f)). Together: R(f^k) = Theta(k log k R(f)).
    used in concepts.yaml open_problems.yaml relations/04-composition.yaml relations/07-parameters.yaml
  64. ['Chattopadhyay, A.', 'Mande, N. S.', 'Sherif, S.']. The log-approximate-rank conjecture is false.Journal of the ACM 67(4):23 (STOC 2019), 2019. ECCC TR18-176doi
    SINK o XOR: spectral norm O(sqrt m) but randomized communication complexity Omega(sqrt m). Also refutes Grolmusz's conjecture and the parity-measure conjecture of Tsang-Wong-Xie-Zhang.
    used in functions/06-classical-total.yaml
  65. ['Gavinsky', 'D.', 'Lee', 'T.', 'Santha', 'M.', 'Sanyal', 'S.']. A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity.ICALP 2019, 2019. arXiv:1811.10752
    Max-conflict complexity chi-bar. R(f o g^n) = Omega(R(f) chi-bar(g)); chi(g) = Omega(sqrt(R(g))) even for partial g (Thm 6), hence the same for chi-bar; chi-bar = Omega(RS) (Thm 7). The two combine with the collision problem to separate chi-bar from RS on partial functions, though the paper states neither as a separation.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml functions/05-more.yaml measures/02-randomized.yaml open_problems.yaml relations/04-composition.yaml relations/11-lp-and-lower-bound-methods.yaml
  66. ['Huang', 'H.']. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture.Annals of Mathematics 190(3):949-955, 2019. arXiv:1907.00847
    deg(f) <= s(f)^2. The proof in fact gives deg(f) <= lambda(f)^2.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml measures/01-deterministic.yaml measures/03-quantum.yaml measures/04-degree.yaml open_problems.yaml relations/01-classical-core.yaml relations/02-degree.yaml relations/08-fractional.yaml tables/total-exponents.yaml
  67. ['Sanyal', 'S.']. Fourier sparsity and dimension.Theory of Computing 15(11), 2019.
    D(f) = O(sqrt(spar(f)) log spar(f)) for the parity decision tree / Fourier sparsity line of work.
    used in measures/01-deterministic.yaml measures/05-fourier.yaml open_problems.yaml
  68. ['Sinha, M.', 'de Wolf, R.']. Exponential separation between quantum communication and logarithm of approximate rank.FOCS 2019, pp. 966-981, 2019. arXiv:1811.10090doi
    used in functions/06-classical-total.yaml
  69. ['Aaronson', 'S.', 'Ambainis', 'A.']. Forrelation: A Problem That Optimally Separates Quantum from Classical Computing.SIAM Journal on Computing 47(3), STOC 2015, 2018. arXiv:1411.5729
    1-query quantum vs Omega-tilde(sqrt(n)) randomized; conjectured k-Forrelation separation.
    used in functions/04-partial-and-relations.yaml functions/05-more.yaml
  70. ['Ambainis', 'A.', 'Balodis', 'K.', 'Iraids', 'J.', 'Kokainis', 'M.', 'Prusis, K.', 'Smotrovs', 'J.']. All Classical Adversary Methods are Equivalent for Total Functions.STACS 2018, 2018. arXiv:1709.08985
    For total functions, the classical adversary CA(f) = Theta(fbs(f)); they can be far apart for partial functions.
    used in concepts.yaml functions/01-basic.yaml functions/03-separating-total.yaml functions/06-classical-total.yaml measures/01-deterministic.yaml measures/02-randomized.yaml open_problems.yaml relations/11-lp-and-lower-bound-methods.yaml
  71. ['Ambainis', 'A.']. Understanding Quantum Algorithms via Query Complexity.Proc. ICM 2018, 2018. arXiv:1712.06349
    not currently cited by any entry
  72. ['Ambainis', 'A.', 'Prusis, K.', 'Vihrovs', 'J.']. On Block Sensitivity and Fractional Block Sensitivity.Lobachevskii Journal of Mathematics 39(7):967-969, 2018. arXiv:1710.05108
    Simpler construction for the fbs vs bs 3/2 separation, with a better constant.
    used in open_problems.yaml relations/08-fractional.yaml
  73. ['Ben-David', 'S.', 'Kothari', 'R.']. Randomized query complexity of sabotaged and composed functions.Theory of Computing 14(5), ICALP 2016, 2018. arXiv:1605.09071
    Sabotage complexity RS. R(f o g) = Omega(R(f) RS(g)); RS composes perfectly; RS = O(R) and R = O(RS log RS) for total f.
    used in concepts.yaml functions/01-basic.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml functions/05-more.yaml functions/06-classical-total.yaml measures/02-randomized.yaml measures/06-lp.yaml open_problems.yaml relations/04-composition.yaml
  74. ['Bun', 'M.', 'Kothari', 'R.', 'Thaler', 'J.']. The polynomial method strikes back: tight quantum query bounds via dual polynomials.STOC 2018, 2018. arXiv:1710.09079
    used in functions/05-more.yaml
  75. ['Chistopolskaya, A.', 'Podolskii, V. V.']. Parity decision tree complexity is greater than granularity.arXiv preprint, 2018. arXiv:1810.08668ECCC TR18-174
    D_xor(f) >= k+1, where 2^{-k} is the granularity of the Fourier spectrum. Pins D_xor(MAJ_n) = n - B(n) + 1 and D_xor(RMAJ_3^d) = (n+1)/2.
    used in functions/01-basic.yaml functions/02-composed.yaml functions/06-classical-total.yaml
  76. ['Goos, M.', 'Jayram', 'T. S.', 'Pitassi', 'T.', 'Watson', 'T.']. Randomized Communication vs. Partition Number.ACM Transactions on Computation Theory 10(1), ICALP 2017, 2018. ECCC TR17-052
    used in functions/01-basic.yaml functions/03-separating-total.yaml relations/04-composition.yaml tables/total-exponents.yaml
  77. ['Goos, M.', 'Pitassi', 'T.', 'Watson', 'T.']. Deterministic Communication vs. Partition Number.SIAM Journal on Computing 47(6), FOCS 2015, 2018. ECCC TR15-050
    Total function with D = Omega-tilde(UC^2) / D vs subcube partition; used for the D vs deg entry.
    used in concepts.yaml functions/01-basic.yaml functions/03-separating-total.yaml measures/01-deterministic.yaml open_problems.yaml relations/02-degree.yaml tables/total-exponents.yaml
  78. ['Li', 'Y.']. Conflict complexity is lower bounded by block sensitivity.2018. arXiv:1810.08873
    used in functions/01-basic.yaml functions/02-composed.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml functions/07-recent-separations.yaml measures/02-randomized.yaml open_problems.yaml relations/04-composition.yaml
  79. ['Sanyal', 'S.']. A composition theorem via conflict complexity.2018. arXiv:1801.03285
    Introduces conflict complexity chi(g); R(f o g^n) = Omega(R(f) chi(g)).
    used in concepts.yaml functions/03-separating-total.yaml measures/02-randomized.yaml open_problems.yaml relations/04-composition.yaml relations/11-lp-and-lower-bound-methods.yaml
  80. ['Sherstov, A. A.']. The power of asymmetry in constant-depth circuits.SIAM Journal on Computing 47(6):2362-2434 (FOCS 2015), 2018. ECCC TR15-147
    Remark 3.4 states a confidence, not a theorem, that the log factor in the AC^0 quantum bound can be removed.
    used in functions/05-more.yaml
  81. ['Aaronson, S.', 'Chen, L.']. Complexity-theoretic foundations of quantum supremacy experiments.CCC 2017, 22:1-22:67, 2017. arXiv:1612.05903doi
    Section 6 settles Fourier fishing and Fourier sampling: R = Omega(N/log N) for the relation, Theta(N) for sampling, against one quantum query.
    used in functions/05-more.yaml
  82. ['Ambainis', 'A.', 'Balodis', 'K.', 'Belovs', 'A.', 'Lee', 'T.', 'Santha', 'M.', 'Smotrovs', 'J.']. Separations in Query Complexity Based on Pointer Functions.Journal of the ACM 64(5), STOC 2016, 2017. arXiv:1506.04719
    also cited here as ABB+17
    Cubic-free pointer functions: D vs R0 quadratic, D vs R quadratic, R0 vs R quadratic, D vs QE, D vs Q quartic, D vs deg-tilde quartic.
    used in functions/03-separating-total.yaml measures/02-randomized.yaml measures/03-quantum.yaml open_problems.yaml relations/01-classical-core.yaml relations/02-degree.yaml relations/03-quantum.yaml tables/total-exponents.yaml
  83. ['Anshu', 'A.', 'Gavinsky', 'D.', 'Jain', 'R.', 'Kundu', 'S.', 'Lee', 'T.', 'Mukhopadhyay', 'P.', 'Santha', 'M.', 'Sanyal', 'S.']. A Composition Theorem for Randomized Query Complexity.FSTTCS 2017, 2017. arXiv:1706.00335
    used in measures/02-randomized.yaml open_problems.yaml relations/04-composition.yaml
  84. ['Ben-David', 'S.', 'Hatami', 'P.', 'Tal', 'A.']. Low-Sensitivity Functions from Unambiguous Certificates.ITCS 2017, 2017. arXiv:1605.07084
    Total function with D(f) = Omega-tilde(s(f)^3); also C(f) = Omega(UC_min(f)^{1.22}).
    used in functions/01-basic.yaml functions/03-separating-total.yaml functions/05-more.yaml measures/01-deterministic.yaml open_problems.yaml relations/01-classical-core.yaml relations/10-new-measures.yaml tables/total-exponents.yaml
  85. ['Bun', 'M.', 'Thaler', 'J.']. A Nearly Optimal Lower Bound on the Approximate Degree of AC^0.FOCS 2017; SIAM Journal on Computing 49(4) (2020), 2017. arXiv:1703.05784
    also cited here as BT20, BT17
    Cited as [BT20] (the SICOMP version) in the Iyer et al. table for the whole deg-tilde row: deg-tilde(f) can be quadratically larger than C, RC, bs, s and lambda.
    used in measures/04-degree.yaml relations/02-degree.yaml tables/total-exponents.yaml
  86. ['Gavinsky, D.', 'Lee, T.', 'Santha, M.', 'Sanyal, S.']. Quadratically tight relations for randomized query complexity.Theory of Computing Systems 64:101-119 (CSR 2019), 2017. ECCC TR17-123
    Uses prt for the logarithm of the Jain-Klauck LP optimum, the convention this zoo follows. Also: EC <= R_0 = O(EC^2), FC <= EC <= FC^{3/2}, so EC^{2/3} <= R.
    not currently cited by any entry
  87. ['Gavinsky', 'D.', 'Jain', 'R.', 'Klauck', 'H.', 'Kundu', 'S.', 'Lee', 'T.', 'Santha', 'M.', 'Sanyal', 'S.', 'Vihrovs', 'J.']. Quadratically tight relations for randomized query complexity.Theory of Computing Systems 64:101-119 (2020); CSR 2018, 2017. arXiv:1708.00822ECCC TR17-123
    Introduces expectational certificate complexity EC: EC(f) <= R0(f) = O(EC(f)^2), and fbs <= EC <= C. The reference for the EC row of this zoo.
    used in functions/01-basic.yaml measures/01-deterministic.yaml measures/02-randomized.yaml relations/01-classical-core.yaml relations/09-chain.yaml relations/10-new-measures.yaml relations/11-lp-and-lower-bound-methods.yaml
  88. ['Liu, R. P.']. Some upper and lower bounds regarding query complexity.MMath thesis, University of Waterloo (Combinatorics & Optimization), 2017. link
    Chapter 4 gives a matching classical algorithm and lower bound for the glued-trees label-detection problem, tight up to a log factor in the input size.
    used in functions/05-more.yaml
  89. ['Polyanskiy', 'Y.', 'Wu', 'Y.']. Strong data-processing inequalities for channels and Bayesian networks.Convexity and Concentration, IMA Volumes in Mathematics and its Applications 161, Springer, pp. 211-249, 2017. arXiv:1508.06025
    Contains the clean special case of Samorodnitsky's inequality (noise beats erasure) used to prove Rna = O(noisyRna).
    used in concepts.yaml measures/02-randomized.yaml open_problems.yaml relations/04-composition.yaml
  90. ['Shpilka, A.', 'Tal, A.', 'Volk, B. L.']. On the structure of Boolean functions with small spectral norm.Computational Complexity 26(1):229-273 (ITCS 2014), 2017. ECCC TR13-049doi
    Structure theorems for small spectral norm; parity decision tree size at most 2^A n^{2A} with A = L1(f), shown tight by [CMS19].
    not currently cited by any entry
  91. ['Aaronson', 'S.', 'Ben-David', 'S.', 'Kothari', 'R.']. Separations in Query Complexity Using Cheat Sheets.STOC 2016, 2016. arXiv:1511.01937
    Cheat-sheet technique. Q vs deg-tilde quartic, R vs Q, D vs Q quartic, and the general 'lifting a partial-function separation to a total function' machinery.
    used in concepts.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml open_problems.yaml relations/02-degree.yaml relations/03-quantum.yaml tables/total-exponents.yaml
  92. ['Ambainis, A.', 'Kokainis, M.', 'Kothari, R.']. Nearly optimal separations between communication (or query) complexity and partitions.CCC 2016, 4:1-4:14, 2016. arXiv:1512.01210
    A total f with D(f) = Omega~(SP(f)^2), hence also D(f) = Omega~(prt(f)^2). Nearly matches D = O(SP^2) / D = O(prt_0 * prt_{1/3}).
    used in measures/01-deterministic.yaml relations/01-classical-core.yaml relations/11-lp-and-lower-bound-methods.yaml
  93. ['Filmus', 'Y.', 'Hatami', 'H.', 'Keller', 'N.', 'Lifshitz', 'N.']. On the sum of the L1 influences of bounded functions.Israel Journal of Mathematics 214(1):167-192, 2016. arXiv:1409.5793
    Improves the bound to O(d^2) in general and O(d log d) for homogeneous functions.
    used in measures/05-fourier.yaml open_problems.yaml relations/05-fourier.yaml
  94. ['Goos, M.', 'Lovett, S.', 'Meka, R.', 'Watson, T.', 'Zuckerman, D.']. Rectangles are nonnegative juntas.SIAM Journal on Computing 45(5):1835-1869 (STOC 2015), 2016.
    The junta theorem: a rectangle in the domain of g^n is approximated by a conical d-junta. This is what makes conical junta degree the right query-side measure for randomized lifting.
    used in relations/11-lp-and-lower-bound-methods.yaml
  95. ['Goos, M.', 'Jayram, T. S.']. A composition theorem for conical juntas.CCC 2016, LIPIcs 50, 5:1-5:16, 2016. ECCC TR15-167
    Degree lower bounds for conical juntas computing recursively defined functions: Omega~(n^0.753) for the binary AND-OR tree (answering Beame-Lawry) and Omega(2.59^h) for the height-h 3-majority tree -- the latter is still the best known randomized lower bound for recursive majority.
    used in functions/02-composed.yaml relations/11-lp-and-lower-bound-methods.yaml
  96. ['Gilmer', 'J.', 'Saks', 'M.', 'Srinivasan', 'S.']. Composition limits and separating examples for some Boolean function complexity measures.Combinatorica 36(3):265-311, CCC 2013, 2016. arXiv:1306.0630
    C vs RC quadratic; RC vs bs to the power 3/2.
    used in functions/03-separating-total.yaml measures/01-deterministic.yaml open_problems.yaml relations/01-classical-core.yaml relations/08-fractional.yaml relations/10-new-measures.yaml tables/total-exponents.yaml
  97. ['Harsha, P.', 'Jain, R.', 'Radhakrishnan, J.']. Partition bound is quadratically tight for product distributions.ICALP 2016, 135:1-135:13, 2016. arXiv:1512.01968ECCC TR15-199
    Under any product distribution mu, D^mu_{0.49}(f) = O((prt_{1/8}(f) * log prt_{1/8}(f))^2) -- so the partition bound is quadratically tight for product distributions, in both the communication and the query setting. The 2015 version stated this for the relaxed partition bound; the published version corrects it to prt.
    not currently cited by any entry
  98. ['Kulkarni', 'R.', 'Tal', 'A.']. On Fractional Block Sensitivity.Chicago Journal of Theoretical Computer Science 2016(8), 2016. ECCC TR13-168
    fbs = Theta(RC); RC(f) = O(deg-tilde(f)^2); R0(f) = O(R(f) s(f) log RC(f)) -- one of the few genuinely log-factor relations known. Also the randomized strengthening of the certificate complexity barrier: the positive adversary is at most sqrt(FC^0 FC^1), hence at most fbs, for total f.
    used in concepts.yaml functions/01-basic.yaml functions/03-separating-total.yaml measures/01-deterministic.yaml measures/02-randomized.yaml measures/03-quantum.yaml measures/04-degree.yaml open_problems.yaml relations/01-classical-core.yaml relations/02-degree.yaml relations/08-fractional.yaml relations/10-new-measures.yaml relations/11-lp-and-lower-bound-methods.yaml
  99. ['Magniez, F.', 'Nayak, A.', 'Santha, M.', 'Sherman, J.', 'Tardos, G.', 'Xiao, D.']. Improved bounds for the randomized decision tree complexity of recursive majority.Random Structures & Algorithms 48(3):612-638 (ICALP 2011), 2016. arXiv:1309.7565ECCC TR10-192
    R_0(3-MAJ_h) <= 1.007 * 2.64944^h by an interleaving of two recursive algorithms (Thm 4.2), and R_delta(3-MAJ_h) >= (1/2 - delta) * 2.57143^h. The lower bound has since been superseded by Goos-Jayram's Omega(2.59^h); the upper bound stands.
    used in functions/02-composed.yaml
  100. ['Samorodnitsky', 'A.']. On the entropy of a noisy function.IEEE Transactions on Information Theory 62(10):5446-5464, 2016. arXiv:1508.01464
    also cited here as Sam16, Sam15
    For a Boolean f and X ~ mu, the noisy copy N_rho(X) preserves at least as much information about f(X) as the erasure copy E_{rho^2}(X). The special case used in BenDavidBlais20composition is the one isolated by PolyanskiyWu17. The paper's own target is the Courtade-Kumar conjecture, which it settles for high noise (Theorem 1.15).
    used in concepts.yaml measures/02-randomized.yaml open_problems.yaml relations/04-composition.yaml
  101. ['Balodis, K.', 'Iraids, J.']. Quantum lower bound for graph collision implies lower bound for triangle detection.2015. arXiv:1507.03885
    used in functions/05-more.yaml
  102. ['Kerenidis', 'I.', 'Laplante', 'S.', 'Lerays', 'V.', 'Roland', 'J.', 'Xiao', 'D.']. Lower bounds on information complexity via zero-communication protocols and applications.SIAM Journal on Computing 44(5), 2015. arXiv:1204.1505
    Introduces the relaxed partition bound and relates zero-communication protocols to LP relaxations; the query-complexity shadow of this is the certificate-game family.
    used in functions/04-partial-and-relations.yaml functions/05-more.yaml functions/06-classical-total.yaml measures/06-lp.yaml relations/11-lp-and-lower-bound-methods.yaml
  103. ['Kothari', 'R.', 'Racicot-Desloges', 'D.', 'Santha', 'M.']. Separating Decision Tree Complexity from Subcube Partition Complexity.RANDOM 2015, 2015. arXiv:1504.01339
    used in functions/03-separating-total.yaml measures/01-deterministic.yaml relations/01-classical-core.yaml
  104. ['Mahadev', 'U.', 'de Wolf', 'R.']. Rational approximations and quantum algorithms with postselection.Quantum Information and Computation 15(3-4), 2015. arXiv:1401.0912
    PostQ_eps(f) = Theta(rdeg_eps(f)).
    used in functions/01-basic.yaml functions/02-composed.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml functions/05-more.yaml functions/06-classical-total.yaml measures/03-quantum.yaml measures/04-degree.yaml open_problems.yaml relations/03-quantum.yaml relations/09-chain.yaml relations/13-definitional.yaml
  105. ['Aaronson', 'S.', 'Ambainis', 'A.']. The Need for Structure in Quantum Speedups.Theory of Computing 10:133-166, ITCS 2011, 2014. arXiv:0911.0996
    R(f) = O(Q(f)^{2 d}) style results for low-degree bounded functions; the Aaronson-Ambainis conjecture on influential variables.
    used in concepts.yaml functions/04-partial-and-relations.yaml measures/05-fourier.yaml open_problems.yaml relations/06-settings.yaml
  106. ['Ambainis', 'A.', 'de Wolf', 'R.']. How low can approximate degree and quantum query complexity be for total Boolean functions?.Computational Complexity 23(2):305-322, 2014. arXiv:1206.0717
    Total f with deg-tilde(f) = O(log n) type extremal questions; the minimum possible approximate degree of a total function depending on n variables.
    not currently cited by any entry
  107. ['Backurs', 'A.', 'Bavarian', 'M.']. On the sum of L1 influences.CCC 2014, 2014. arXiv:1302.4625
    Total L1 influence of a bounded degree-d function is at most poly(d), independent of n: O(d^3) in general, O(d^2) homogeneous.
    used in measures/05-fourier.yaml open_problems.yaml
  108. ['Beimel', 'A.', 'Ben Daniel', 'S.', 'Kushilevitz', 'E.', 'Weinreb', 'E.']. Choosing, agreeing, and eliminating in communication complexity.Computational Complexity 23:1-42, 2014. doi
    The communication-complexity ancestor of the selection problem: solve any one of k given instances.
    used in measures/02-randomized.yaml
  109. ['Belovs, A.', 'Rosmanis, A.']. On the power of non-adaptive learning graphs.Computational Complexity 23(2):323-354 (CCC 2013), 2014. arXiv:1210.3279
    Prop. 13: Omega(m^{9/7}/sqrt(log m)) for the triangle certificate structure -- a barrier for non-adaptive learning graphs, unconditional only for triangle sum.
    used in functions/05-more.yaml
  110. ['Courtade', 'T. A.', 'Kumar', 'G. R.']. Which Boolean functions maximize mutual information on noisy inputs?.IEEE Transactions on Information Theory 60(8):4515-4525, 2014. doi
    also cited here as CK14
    The 'most informative Boolean function' conjecture: I(f(X); Y) <= 1 - H(eps) for every Boolean f, where Y is X passed through a binary symmetric channel of crossover probability eps. Dictators attain it.
    used in concepts.yaml
  111. ['Goos, M.', 'Pitassi, T.']. Communication lower bounds via critical block sensitivity.STOC 2014; SIAM Journal on Computing 47(5), 2014. arXiv:1311.2355
    Defines critical block sensitivity cbs(S) for search problems and lifts it to randomized communication lower bounds; recovers and strengthens the Beame-Pitassi-Segerlind monotone/proof-complexity bounds.
    used in functions/01-basic.yaml functions/02-composed.yaml functions/04-partial-and-relations.yaml functions/05-more.yaml measures/01-deterministic.yaml relations/10-new-measures.yaml
  112. ['Le Gall, F.']. Improved quantum algorithm for triangle finding via combinatorial arguments.FOCS 2014, 2014. arXiv:1407.0085
    Theorem 1.1: O-tilde(m^{5/4}), and it finds the triangle.
    used in functions/05-more.yaml
  113. ['Montanaro', 'A.']. A composition theorem for decision tree complexity.Chicago Journal of Theoretical Computer Science 2014, Article 6, 2014. arXiv:1302.4207
    also cited here as Mon14
    D(f o g) = D(f) D(g), independently of Tal13, and for an outer relation with boolean-valued inner relations. Also gives the direct sum for D as a corollary, and a 3-query counterexample showing the theorem fails when the inner alphabet is not boolean.
    used in concepts.yaml relations/04-composition.yaml
  114. ["O'Donnell", 'R.']. Analysis of Boolean Functions.Cambridge University Press, 2014. link
    Standard reference for influence, noise sensitivity, Fourier weight, spectral norm.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/06-classical-total.yaml measures/05-fourier.yaml relations/05-fourier.yaml relations/10-new-measures.yaml relations/12-normalized.yaml
  115. ['Sherstov, A. A.']. Breaking the Minsky-Papert barrier for constant-depth circuits.STOC 2014, 2014. doi
    Systematic use of one-sided approximate degree (deg_+) for AC^0 lower bounds.
    used in measures/04-degree.yaml relations/10-new-measures.yaml
  116. ['Ambainis', 'A.']. Superlinear Advantage for Exact Quantum Algorithms.STOC 2013, 2013. arXiv:1211.0721
    also cited here as Amb13
    First total function with QE(f) = O(D(f)^{1-eps}); gives the 1.15 exponents in the QE column.
    used in functions/03-separating-total.yaml measures/03-quantum.yaml open_problems.yaml relations/03-quantum.yaml tables/total-exponents.yaml
  117. ['Ambainis', 'A.', 'Iraids', 'J.', 'Smotrovs', 'J.']. Exact quantum query complexity of EXACT and THRESHOLD.TQC 2013, 2013. arXiv:1302.1235
    used in functions/01-basic.yaml functions/03-separating-total.yaml measures/03-quantum.yaml
  118. ['Goldreich', 'O.', 'Goldwasser', 'S.', 'Ron', 'D.']. On the possibilities and limitations of pseudodeterministic algorithms.ITCS 2013, 2013. ECCC TR12-101
    Introduces pseudo-determinism; quartic relation between deterministic and pseudo-deterministic query complexity of search problems.
    used in functions/04-partial-and-relations.yaml measures/02-randomized.yaml relations/06-settings.yaml relations/13-definitional.yaml
  119. ['Jeffery, S.', 'Kothari, R.', 'Magniez, F.']. Nested quantum walks with quantum data structures.SODA 2013, pp. 1474-1485, 2013. arXiv:1210.1199
    used in functions/05-more.yaml
  120. ['Lee', 'T.', 'Roland', 'J.']. A strong direct product theorem for quantum query complexity.Computational Complexity 22(2):429-462, CCC 2012, 2013. arXiv:1104.4468
    also cited here as LR11, LR12
    Quantum DPT at the right scale: Omega(Q(f)k) queries still leave success probability exponentially small in k. The classical analogue at Omega(R(f)k) is open.
    used in concepts.yaml open_problems.yaml relations/04-composition.yaml
  121. ['Leonardos, N.']. An improved lower bound for the randomized decision tree complexity of recursive majority.ICALP 2013, LNCS 7965, 696-708, 2013.
    (1-2delta) * 2.55^h, between Jayram-Kumar-Sivakumar and Magniez et al.
    used in functions/02-composed.yaml
  122. ['Lee, T.', 'Magniez, F.', 'Santha, M.']. Improved quantum query algorithms for triangle finding and associativity testing.SODA 2013, pp. 1486-1502; Algorithmica 77:459-486 (2017), 2013. arXiv:1210.1014
    Theorem 7: O(m^{9/7}). Not arXiv:1109.5135, which gives only m^{35/27} for the triangle.
    used in functions/05-more.yaml
  123. ['Miller, C. A.']. Evasiveness of graph properties and topological fixed-point theorems.Foundations and Trends in Theoretical Computer Science 7(4):337-415, 2013. arXiv:1306.0110doi
    used in functions/06-classical-total.yaml
  124. ['Sherstov, A. A.']. Making polynomials robust to noise.Theory of Computing 9:593-615 (STOC 2012), 2013.
    An explicit construction of the degree-O(n) robust polynomial that Buhrman-Newman-Rohrig-de Wolf had obtained only via a quantum algorithm.
    not currently cited by any entry
  125. ['Tal', 'A.']. Properties and Applications of Boolean Function Composition.ITCS 2013, 2013. ECCC TR12-163
    Composition behaviour of s, bs, C, deg, deg-tilde, and the 'sensitivity composes' results.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml measures/01-deterministic.yaml open_problems.yaml relations/04-composition.yaml relations/08-fractional.yaml relations/10-new-measures.yaml
  126. ['Tsang', 'H. Y.', 'Wong', 'C. H.', 'Xie', 'N.', 'Zhang', 'S.']. Fourier sparsity, spectral norm, and the log-rank conjecture.FOCS 2013, 2013. arXiv:1304.1245
    deg(f) = O(log spar(f)) style bounds; the log-rank conjecture connection.
    used in concepts.yaml functions/01-basic.yaml measures/01-deterministic.yaml measures/05-fourier.yaml open_problems.yaml relations/05-fourier.yaml
  127. ['Beame, P.', 'Machmouchi, W.']. The quantum query complexity of AC^0.Quantum Information and Computation 12(7-8):670-676, 2012. arXiv:1008.2422
    Omega(n/log n) quantum queries for an AC^0 function; Omega(n) element queries for ONTO.
    used in functions/05-more.yaml
  128. ['Belovs, A.']. Learning-graph-based quantum algorithm for k-distinctness.FOCS 2012, 2012. arXiv:1205.1534
    used in functions/05-more.yaml
  129. ['Belovs, A.']. Span programs for functions with constant-sized 1-certificates.STOC 2012, 2012. arXiv:1105.4024
    Learning graphs; Theorem 8 gives O(m^{35/27}) for triangle finding.
    used in functions/05-more.yaml
  130. ['Drucker', 'A.']. Improved direct product theorems for randomized query complexity.Computational Complexity 21(2):197-244, CCC 2011, 2012. arXiv:1005.0644
    Direct product: solving k independent copies of f with fewer than ~k R(f) queries succeeds with exponentially small probability.
    used in concepts.yaml open_problems.yaml relations/04-composition.yaml
  131. ['Huynh, T.', 'Nordstrom, J.']. On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity.STOC 2012, 233-248, 2012.
    Where critical block sensitivity was introduced, as the query-side measure that survives lifting for search problems with many valid answers.
    used in functions/04-partial-and-relations.yaml functions/05-more.yaml
  132. ['McKague, M.']. Interactive proofs for BQP via self-tested graph states.Chicago Journal of Theoretical Computer Science 2012, article 6, 2012.
    Section 1.1 gives the implementable per-node-secret restatement of recursive Fourier sampling.
    used in functions/05-more.yaml
  133. ['Sherstov', 'A. A.']. Making polynomials robust to noise.STOC 2012; Theory of Computing 9:593-615 (2013), 2012. doi
    also cited here as Sherstov12
    Every bounded degree-d polynomial has a degree-O(d) robust version, giving the approximate-degree composition UPPER bound deg~(f o g) = O(deg~(f) deg~(g)). The matching lower bound is now proved for total Boolean functions [PednekarPodder26composition].
    used in concepts.yaml functions/02-composed.yaml measures/04-degree.yaml open_problems.yaml relations/04-composition.yaml
  134. ['Ambainis', 'A.', 'Sun', 'X.']. New separation between s(f) and bs(f).2011. arXiv:1108.3494ECCC TR11-116
    bs(f) >= (2/3) s(f)^2 - (1/3) s(f); the best known constant in the bs-vs-s separation.
    used in concepts.yaml functions/02-composed.yaml open_problems.yaml relations/01-classical-core.yaml relations/08-fractional.yaml
  135. ['Chakraborty', 'S.']. On the sensitivity of cyclically-invariant Boolean functions.Discrete Mathematics and Theoretical Computer Science 13(4), 2011.
    Cyclically invariant function with s = Theta(bs^{1/3})... see also the 'minterm' constructions.
    used in functions/02-composed.yaml
  136. ['Gopalan', 'P.', "O'Donnell", 'R.', 'Servedio', 'R.', 'Shpilka', 'A.', 'Wimmer', 'K.']. Testing Fourier dimensionality and sparsity.SIAM Journal on Computing 40(4), 2011.
    used in measures/05-fourier.yaml open_problems.yaml
  137. ['Hatami', 'P.', 'Kulkarni', 'R.', 'Pankratov', 'D.']. Variations on the Sensitivity Conjecture.Theory of Computing Library, Graduate Surveys 4, 2011. doi
    Survey of s vs bs vs C vs deg, pre-Huang.
    used in concepts.yaml
  138. ['Lee', 'T.', 'Mittal', 'R.', 'Reichardt', 'B. W.', 'Spalek, R.', 'Szegedy', 'M.']. Quantum query complexity of state conversion.FOCS 2011, 2011. arXiv:1011.3020
    Extends Adv^pm = Theta(Q) to non-Boolean output and state conversion.
    used in concepts.yaml functions/02-composed.yaml functions/03-separating-total.yaml measures/03-quantum.yaml relations/03-quantum.yaml relations/04-composition.yaml relations/06-settings.yaml
  139. ['Reichardt', 'B. W.']. Reflections for quantum query algorithms.SODA 2011, 2011. arXiv:1005.1601
    Q(f) = Theta(Adv^pm(f)) for all (partial) Boolean functions: the adversary bound is tight.
    used in concepts.yaml functions/02-composed.yaml functions/03-separating-total.yaml measures/03-quantum.yaml open_problems.yaml relations/03-quantum.yaml relations/04-composition.yaml relations/06-settings.yaml
  140. ['Aaronson', 'S.']. BQP and the polynomial hierarchy.STOC 2010, 2010. arXiv:0910.4698
    Fourier checking; introduces the forrelation-style separations.
    used in functions/05-more.yaml
  141. ['Ambainis', 'A.', 'Childs', 'A. M.', 'Le Gall', 'F.', 'Tani', 'S.']. The quantum query complexity of certification.Quantum Information and Computation 10(3-4):181-189, 2010. arXiv:0903.1291
    also cited here as ACGT09
    Shows the general adversary bound has direct sum behaviour, which with Reichardt's tightness theorem gives a quantum direct sum for boolean functions up to a log factor.
    used in concepts.yaml relations/04-composition.yaml
  142. ['Ambainis', 'A.', 'Childs', 'A. M.', 'Reichardt', 'B. W.', 'Spalek, R.', 'Zhu', 'S.']. Any AND-OR formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer.SIAM Journal on Computing 39(6):2513-2530, 2010. arXiv:quant-ph/0703015
    Discrete-query version of the NAND-tree algorithm; general AND-OR formulas.
    used in functions/02-composed.yaml
  143. ['Jain', 'R.', 'Klauck', 'H.']. The partition bound for classical communication complexity and query complexity.CCC 2010, 2010. arXiv:0910.4266
    Introduces the partition bound; it subsumes the rectangle/corruption bound, the smooth rectangle bound, and in the query world randomized certificate complexity, block sensitivity and the approximate-degree bound.
    used in functions/02-composed.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml functions/05-more.yaml functions/06-classical-total.yaml measures/06-lp.yaml relations/11-lp-and-lower-bound-methods.yaml
  144. ['Jain', 'R.', 'Klauck', 'H.', 'Santha', 'M.']. Optimal direct sum results for deterministic and randomized decision tree complexity.Information Processing Letters 110(20):893-897, 2010. arXiv:1004.0105
    Direct sum for D and R: computing k copies costs k times as much, up to constants.
    used in concepts.yaml open_problems.yaml relations/04-composition.yaml
  145. ['Santha, M.', 'Szegedy, M.']. Quantum and classical query complexities of local search are polynomially related.Algorithmica 55(3):557-575 (STOC 2004), 2009.
    D(LS_G) = O(Q(LS_G)^19) for every graph G, via the separation number; the exponent is not claimed to be optimal.
    used in functions/05-more.yaml
  146. ['Sun, X.', 'Yao, A. C.-C.']. On the quantum query complexity of local search in two and three dimensions.Algorithmica 55(3):576-600 (FOCS 2006), 2009. doi
    used in functions/05-more.yaml
  147. ['Zhang, S.']. Tight bounds for randomized and quantum local search.SIAM Journal on Computing 39(3):948-977 (STACS 2006), 2009. arXiv:quant-ph/0504085doi
    Settles the cube (R = Theta(2^{n/2} sqrt n), Q = Theta(2^{n/3} n^{1/6})) and the grid for d >= 4 (randomized) and d >= 5 (quantum).
    used in functions/05-more.yaml
  148. ['Aaronson', 'S.']. Quantum certificate complexity.Journal of Computer and System Sciences 74(3):313-322, CCC 2003, 2008. arXiv:quant-ph/0210020
    Introduces randomized certificate complexity RC and quantum certificate complexity QC; QC = Theta(sqrt(RC)).
    used in concepts.yaml functions/01-basic.yaml functions/04-partial-and-relations.yaml functions/06-classical-total.yaml functions/07-recent-separations.yaml measures/01-deterministic.yaml measures/03-quantum.yaml open_problems.yaml relations/01-classical-core.yaml relations/03-quantum.yaml relations/08-fractional.yaml relations/11-lp-and-lower-bound-methods.yaml
  149. ['Childs, A. M.', 'Lee, T.']. Optimal quantum adversary lower bounds for ordered search.ICALP 2008, pp. 869-880, 2008. arXiv:0708.3396doi
    The exact optimum of both the non-negative and the negative-weight adversary bound for (a symmetrised) ordered search is (ln n)/pi + O(1): the Hoyer-Neerbek-Shi bound is the ceiling of the method.
    used in functions/05-more.yaml
  150. ['de Wolf', 'R.']. A note on quantum algorithms and the minimal degree of eps-error polynomials for symmetric functions.Quantum Information and Computation 8(10):943-950, 2008. arXiv:0802.1816
    deg~eps(f) = Theta(deg~{1/3}(f) + sqrt(n log(1/eps))) for symmetric f, without the log factors of Sherstov's version.
    used in relations/07-parameters.yaml
  151. ['Farhi', 'E.', 'Goldstone', 'J.', 'Gutmann', 'S.']. A quantum algorithm for the Hamiltonian NAND tree.Theory of Computing 4:169-190, 2008. arXiv:quant-ph/0702144
    Continuous-time O(sqrt(n)) algorithm for the balanced NAND tree.
    used in functions/02-composed.yaml
  152. ['Laplante', 'S.', 'Magniez', 'F.']. Lower bounds for randomized and quantum query complexity using Kolmogorov arguments.SIAM Journal on Computing 38(1):46-62, 2008. arXiv:quant-ph/0311189
    A Kolmogorov-complexity form of the classical adversary.
    used in measures/02-randomized.yaml relations/13-definitional.yaml
  153. ['Sherstov', 'A. A.']. Approximate inclusion-exclusion for arbitrary symmetric functions.CCC 2008; Computational Complexity 18(2), 2008. doi
    First characterisation of the eps-approximate degree of symmetric Boolean functions, up to logs.
    used in relations/07-parameters.yaml
  154. ['Spalek, R.']. The multiplicative quantum adversary.CCC 2008, pp. 237-248, 2008. arXiv:quant-ph/0703237doi
    At least as strong as the additive negative-weights adversary, and unlike it survives exponentially small success probability, giving strong direct product theorems.
    used in functions/01-basic.yaml functions/04-partial-and-relations.yaml measures/03-quantum.yaml relations/03-quantum.yaml relations/04-composition.yaml
  155. ['Ambainis', 'A.']. Quantum walk algorithm for element distinctness.SIAM Journal on Computing 37(1):210-239, 2007. arXiv:quant-ph/0311001
    used in functions/04-partial-and-relations.yaml functions/05-more.yaml
  156. ['Ben-Or, M.', 'Hassidim, A.']. Quantum search in an ordered list via adaptive learning.arXiv preprint, 2007. arXiv:quant-ph/0703231
    Expected cost below 0.32 log_2 n. The abstract says error free; section 3 allows o(1) failure probability.
    used in functions/05-more.yaml
  157. ['Buhrman', 'H.', 'Newman', 'I.', 'Rohrig, H.', 'de Wolf', 'R.']. Robust polynomials and quantum algorithms.Theory of Computing Systems 40(4):379-395, STACS 2005, 2007. arXiv:quant-ph/0309220
    Among other things, settles how well k copies can be computed quantumly with a query budget a large constant times Q(f)k -- the question Drucker12 leaves open classically.
    used in open_problems.yaml
  158. ['Chakrabarti, A.', 'Khot, S.']. Improved lower bounds on the randomized complexity of graph properties.Random Structures & Algorithms 30(3):427-440 (ICALP 2001), 2007. doi
    Every nontrivial monotone graph property has R = Omega(n^{4/3} log^{1/3} n); the conjecture is Omega(n^2).
    used in functions/06-classical-total.yaml
  159. ['Childs, A. M.', 'Landahl, A. J.', 'Parrilo, P. A.']. Quantum algorithms for the ordered search problem via semidefinite programming.Physical Review A 75:032335, 2007. arXiv:quant-ph/0608161doi
    Exact 4-query algorithm for 605 items, 0.433 log_2 n. Brookes, Jacokes and Landahl had reached 4 log_550 n by gradient descent.
    used in functions/05-more.yaml
  160. ['Hoyer, P.', 'Lee, T.', 'Spalek, R.']. Negative weights make adversaries stronger.STOC 2007, 2007. arXiv:quant-ph/0611054
    The general (negative-weight) adversary bound Adv^pm.
    used in concepts.yaml functions/02-composed.yaml measures/03-quantum.yaml open_problems.yaml relations/03-quantum.yaml relations/04-composition.yaml
  161. ['Klauck', 'H.', 'Spalek, R.', 'de Wolf', 'R.']. Quantum and classical strong direct product theorems and optimal time-space tradeoffs.SIAM Journal on Computing 36(5):1472-1493, FOCS 2004, 2007. arXiv:quant-ph/0402123
    also cited here as KSdW07, KlauckSpalekdeWolf07
    First general DPT for randomized query complexity, with the query budget scaling as bs(f)k rather than R(f)k; also the quantum version at sqrt(bs(f))k. Superseded classically by Drucker12.
    used in concepts.yaml relations/04-composition.yaml
  162. ['Magniez, F.', 'Santha, M.', 'Szegedy, M.']. Quantum algorithms for the triangle problem.SIAM Journal on Computing 37(2):413-424 (SODA 2005), 2007. arXiv:quant-ph/0310134
    used in functions/05-more.yaml
  163. ['Aaronson', 'S.']. Lower bounds for local search by quantum arguments.SIAM Journal on Computing 35(4):804-824, 2006. arXiv:quant-ph/0307149
    The classical adversary method (relational adversary).
    used in functions/04-partial-and-relations.yaml functions/05-more.yaml measures/02-randomized.yaml relations/13-definitional.yaml
  164. ['Durr, C.', 'Heiligman, M.', 'Hoyer, P.', 'Mhalla, M.']. Quantum query complexity of some graph problems.SIAM Journal on Computing 35(6):1310-1328 (ICALP 2004), 2006. arXiv:quant-ph/0401091doi
    Adjacency-matrix model: connectivity Theta(n^{3/2}), strong connectivity Theta(n^{3/2}), minimum spanning tree Theta(n^{3/2}), single-source shortest paths Theta(n^{3/2}).
    used in functions/06-classical-total.yaml
  165. ['Laplante', 'S.', 'Lee', 'T.', 'Szegedy', 'M.']. The quantum adversary method and classical formula size lower bounds.Computational Complexity 15(2):163-196, 2006.
    Comparisons among adversary variants; K(f) <= SA(f).
    used in measures/03-quantum.yaml
  166. ['Spalek, R.', 'Szegedy, M.']. All quantum adversary methods are equivalent.Theory of Computing 2:1-18, 2006. arXiv:quant-ph/0409116
    Shows the many published positive-weight adversary formulations coincide, and establishes the certificate-complexity barrier Adv(f) <= sqrt(C0(f) C1(f)).
    used in concepts.yaml functions/04-partial-and-relations.yaml functions/05-more.yaml measures/03-quantum.yaml open_problems.yaml relations/03-quantum.yaml relations/11-lp-and-lower-bound-methods.yaml
  167. ['Verhoeven, Y. F.']. Enhanced algorithms for local search.Information Processing Letters 97(5):171-176, 2006. doi
    O(sqrt k log log k) quantum local search on the two-dimensional grid, via graph genus.
    used in functions/05-more.yaml
  168. ['Aaronson, S.']. Quantum computing, postselection, and probabilistic polynomial-time.Proceedings of the Royal Society A 461(2063):3473-3482, 2005. arXiv:quant-ph/0412187
    PostBQP = PP. Also the first postselected query algorithm for majority, later improved to optimal by Mahadev-de Wolf.
    used in functions/01-basic.yaml
  169. ['Aaronson', 'S.']. Quantum computing, postselection, and probabilistic polynomial-time.Proc. Royal Society A 461:3473-3482, 2005. arXiv:quant-ph/0412187
    used in measures/03-quantum.yaml
  170. ['Ambainis, A.']. Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range.Theory of Computing 1(3):37-46, 2005. arXiv:quant-ph/0305179doi
    used in functions/04-partial-and-relations.yaml
  171. ['Buhrman', 'H.', 'Newman', 'I.', 'Rohrig, H.', 'de Wolf', 'R.']. Robust Polynomials and Quantum Algorithms.STACS 2005; Theory of Computing Systems 40(4), 2005. arXiv:quant-ph/0309220
    Robust quantum query complexity: n noisy quantum queries suffice to recover all n bits, so quantum has no log n overhead for parity.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/03-separating-total.yaml functions/06-classical-total.yaml measures/02-randomized.yaml measures/03-quantum.yaml relations/03-quantum.yaml relations/13-definitional.yaml
  172. ['Hoyer, P.', 'Spalek, R.']. Lower bounds on quantum query complexity.Bulletin of the EATCS 87:78-103, 2005. arXiv:quant-ph/0509153
    Survey. Section 5 states the certificate complexity barrier in the form Adv(f) <= sqrt(C0 C1) and points out that it is the property-testing promise problems -- both certificate complexities O(1) -- on which the positive adversary collapses.
    used in functions/04-partial-and-relations.yaml
  173. ['Kutin, S.']. Quantum lower bound for the collision problem with small range.Theory of Computing 1(2):29-36, 2005. arXiv:quant-ph/0304162doi
    used in functions/04-partial-and-relations.yaml
  174. ['Midrijanis, G.']. On randomized and quantum query complexities.2005. arXiv:quant-ph/0501142
    R0(f) = O(R(f)^2 log n); improved to O(R^2 log R) by [KulkarniTal16].
    not currently cited by any entry
  175. ["O'Donnell", 'R.', 'Saks', 'M.', 'Schramm', 'O.', 'Servedio', 'R.']. Every decision tree has an influential variable.FOCS 2005, 2005. arXiv:cs/0508071
    The OSSS inequality: Var(f) <= sum_i delta_i(T) Inf_i(f); implies I(f) >= Var(f)^2 ... and D(f) >= Var(f)/max_i Inf_i.
    used in concepts.yaml measures/05-fourier.yaml open_problems.yaml relations/05-fourier.yaml
  176. ['Zhang', 'S.']. On the power of Ambainis lower bounds.Theoretical Computer Science 339(2-3):241-256, 2005. arXiv:quant-ph/0311060
    Independently proves the certificate-complexity barrier for the positive-weight adversary method.
    used in concepts.yaml functions/04-partial-and-relations.yaml measures/03-quantum.yaml open_problems.yaml relations/03-quantum.yaml
  177. ['Aaronson, S.', 'Shi, Y.']. Quantum lower bounds for the collision and the element distinctness problems.Journal of the ACM 51(4):595-605, 2004. doi
    The polynomial-method lower bounds Omega(n^{1/3}) and Omega(n^{2/3}), for range Omega(n^2).
    used in functions/04-partial-and-relations.yaml relations/03-quantum.yaml
  178. ['Kenyon', 'C.', 'Kutin', 'S.']. Sensitivity, block sensitivity, and l-block sensitivity of Boolean functions.Information and Computation 189(1):43-53, 2004. doi
    bs_l(f) = O(s(f)^l); in particular bs_2 = O(s^2).
    used in functions/02-composed.yaml measures/01-deterministic.yaml open_problems.yaml relations/01-classical-core.yaml
  179. ['Midrijanis, G.']. Exact quantum query complexity for total Boolean functions.2004. arXiv:quant-ph/0403168
    D(f) = O(deg(f)^3), improving Nisan-Smolensky's deg^4.
    used in functions/03-separating-total.yaml measures/04-degree.yaml open_problems.yaml relations/01-classical-core.yaml relations/02-degree.yaml relations/03-quantum.yaml tables/total-exponents.yaml
  180. ['Shaltiel', 'R.']. Towards proving strong direct product theorems.Computational Complexity 12(1-2):1-22, CCC 2001, 2004. doi
    also cited here as Sha01, Sha04
    The counterexamples every direct product theorem has to dodge: distributions with a small easy part, where solving k copies is much cheaper than k times solving one. Also proves an optimal XOR lemma for 'fair' algorithms that query every copy equally often.
    used in concepts.yaml measures/02-randomized.yaml open_problems.yaml relations/04-composition.yaml
  181. ['Aaronson, S.']. Quantum lower bound for recursive Fourier sampling.Quantum Information and Computation 3(2):165-174, 2003. arXiv:quant-ph/0209060
    used in functions/05-more.yaml
  182. ['Barnum', 'H.', 'Saks', 'M.', 'Szegedy', 'M.']. Quantum query complexity and semi-definite programming.CCC 2003, 2003.
    The spectral adversary SA(f); lambda <= SA = O(Q).
    used in measures/03-quantum.yaml relations/03-quantum.yaml
  183. ['Childs, A. M.', 'Cleve, R.', 'Deotto, E.', 'Farhi, E.', 'Gutmann, S.', 'Spielman, D. A.']. Exponential algorithmic speedup by a quantum walk.STOC 2003, pp. 59-68, 2003. arXiv:quant-ph/0209131doi
    Introduces the welded (glued) trees problem and the continuous-time quantum walk that traverses it; Thm. 9 is the classical 2^{n/6} lower bound.
    used in functions/05-more.yaml
  184. ['de Wolf', 'R.']. Nondeterministic quantum query and communication complexities.SIAM Journal on Computing 32(3):681-699, 2003. arXiv:cs/0001014
    Nondeterministic degree ndeg and nondeterministic quantum query complexity NQ = ceil(ndeg/2).
    used in functions/01-basic.yaml functions/02-composed.yaml functions/04-partial-and-relations.yaml functions/05-more.yaml functions/06-classical-total.yaml measures/01-deterministic.yaml measures/03-quantum.yaml measures/04-degree.yaml relations/03-quantum.yaml relations/13-definitional.yaml
  185. ['Fenner, S.', 'Zhang, Y.']. A note on the classical lower bound for a hybrid quantum-classical algorithm.arXiv preprint, 2003. arXiv:quant-ph/0312230
    Improves the welded-trees classical lower bound to 2^{n/3}.
    used in functions/05-more.yaml
  186. ['Fortnow', 'L.']. Rational functions and decision-tree complexity (blog post).2003. link
    Where the motivation for the rdeg question (C=P cap coC=P vs PP relative to an oracle) is spelled out.
    not currently cited by any entry
  187. ['Hoyer, P.', 'Mosca', 'M.', 'de Wolf', 'R.']. Quantum search on bounded-error inputs.ICALP 2003, 2003. arXiv:quant-ph/0304052
    Q(AND_n o OR_n) = O(n) on n^2 bits, i.e. Theta(sqrt(N)) with no log factor. Robust quantum search.
    used in functions/01-basic.yaml functions/02-composed.yaml functions/06-classical-total.yaml
  188. ['Jayram, T. S.', 'Kumar, R.', 'Sivakumar, D.']. Two applications of information complexity.STOC 2003, 673-682, 2003.
    The (1-2delta)(7/3)^h lower bound for recursive majority, and the information-complexity method that every later improvement refines.
    used in functions/02-composed.yaml
  189. ['Ambainis', 'A.']. Quantum lower bounds by quantum arguments.Journal of Computer and System Sciences 64(4):750-767, 2002. arXiv:quant-ph/0002066
    The (positive-weight) adversary method.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml measures/03-quantum.yaml open_problems.yaml relations/03-quantum.yaml relations/11-lp-and-lower-bound-methods.yaml
  190. ['Buhrman', 'H.', 'de Wolf', 'R.']. Complexity measures and decision tree complexity: a survey.Theoretical Computer Science 288(1):21-43, 2002. doilink
    The classical starting point. Source of most of the exact constants recorded in this zoo for the deterministic/randomized/quantum-vs-degree relations.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml measures/01-deterministic.yaml measures/02-randomized.yaml measures/03-quantum.yaml measures/04-degree.yaml open_problems.yaml relations/01-classical-core.yaml relations/02-degree.yaml relations/03-quantum.yaml relations/05-fourier.yaml relations/06-settings.yaml relations/09-chain.yaml relations/10-new-measures.yaml relations/13-definitional.yaml
  191. ['Buhrman', 'H.', 'de Wolf', 'R.']. Complexity measures and decision tree complexity: a survey -- constants used here.2002.
    Bookkeeping entry: the exact constants (D <= 27 R^3, bs <= 2 deg^2, bs <= 6 deg-tilde^2, deg <= 2 QE, deg-tilde <= 2 Q, D <= C^1 bs) are quoted from Theorems 3.x-5.x of [BdW02].
    not currently cited by any entry
  192. ['Chakrabarti, A.', 'Khot, S.', 'Shi, Y.']. Evasiveness of subgraph containment and related properties.SIAM Journal on Computing 31(3):866-875, 2002. doi
    used in functions/05-more.yaml
  193. ['Hoyer, P.', 'Neerbek, J.', 'Shi, Y.']. Quantum complexities of ordered searching, sorting, and element distinctness.Algorithmica 34(4):429-448 (ICALP 2001), 2002. arXiv:quant-ph/0102078doi
    Q(ordered search) >= (ln n - 1)/pi, by a weighted all-pairs inner-product argument.
    used in functions/05-more.yaml
  194. ['Lovasz, L.', 'Young, N. E.']. Lecture notes on evasiveness of graph properties.arXiv preprint (Princeton TR 317-91, 1994), 2002. arXiv:cs/0205031
    used in functions/06-classical-total.yaml
  195. ['Savicky, P.']. On determinism versus unambiguous nondeterminism for decision trees.ECCC report TR02-009, 2002. ECCC TR02-009
    also cited here as Sav02
    The earliest of the three independent proofs that D composes exactly; the composition theorem is a lemma on the way to D vs UC.
    used in concepts.yaml relations/04-composition.yaml
  196. ['Beals', 'R.', 'Buhrman', 'H.', 'Cleve', 'R.', 'Mosca', 'M.', 'de Wolf', 'R.']. Quantum Lower Bounds by Polynomials.Journal of the ACM 48(4):778-797, 2001. arXiv:quant-ph/9802049
    The polynomial method. deg <= 2 QE, deg-tilde <= 2 Q, D <= C1*bs, D = O(deg-tilde^6).
    used in functions/01-basic.yaml functions/02-composed.yaml functions/04-partial-and-relations.yaml functions/07-recent-separations.yaml measures/01-deterministic.yaml measures/02-randomized.yaml measures/03-quantum.yaml measures/04-degree.yaml measures/07-sabotage-and-certification.yaml open_problems.yaml relations/01-classical-core.yaml relations/02-degree.yaml relations/03-quantum.yaml relations/06-settings.yaml relations/07-parameters.yaml relations/08-fractional.yaml relations/09-chain.yaml
  197. ['Ben-Sasson, E.', 'Wigderson, A.']. Short proofs are narrow -- resolution made simple.Journal of the ACM 48(2):149-169, 2001. doi
    Size-width tradeoff for resolution; yields 2^{Omega(n)} tree-like resolution size lower bounds for random k-CNFs, hence decision-tree size lower bounds for their false-clause search problems.
    used in functions/04-partial-and-relations.yaml functions/05-more.yaml
  198. ['de Wolf', 'R.']. Characterization of non-deterministic quantum query and quantum communication complexity.CCC 2000, 2000. arXiv:cs/0001014
    Journal version is [deWolf03]. Defines ndeg and shows NQ(f) = ceil(ndeg(f)/2).
    used in functions/01-basic.yaml
  199. ['Shi', 'Y.']. Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables.Information Processing Letters 75(1-2):79-83, 2000. doi
    Total average sensitivity is a lower bound on approximate degree: I(f) <= deg-tilde(f). Quoted from [BdW02, Sec. 4.2].
    used in functions/03-separating-total.yaml relations/05-fourier.yaml
  200. ['Ambainis', 'A.']. A note on quantum black-box complexity of almost all Boolean functions.Information Processing Letters 71(1):5-7, 1999. arXiv:quant-ph/9811080
    also cited here as Ambainis99
    Almost all f have deg-tilde(f) >= n/2 - O(sqrt(n log n)), hence Q(f) >= n/4 - o(n).
    used in relations/02-degree.yaml
  201. ['Ambainis, A.']. A better lower bound for quantum algorithms searching an ordered list.FOCS 1999, pp. 352-357, 1999. arXiv:quant-ph/9902053doi
    used in functions/05-more.yaml
  202. ['Buhrman', 'H.', 'Cleve', 'R.', 'de Wolf', 'R.', 'Zalka', 'C.']. Bounds for small-error and zero-error quantum algorithms.FOCS 1999, 358-368, 1999. arXiv:cs/9904019doi
    also cited here as BCdWZ99
    Q_eps(OR_N) = Theta(sqrt(N log(1/eps))) -- quantum saves a sqrt on the amplification factor. Also zero-error quantum separations for monotone functions and graph properties.
    used in concepts.yaml functions/01-basic.yaml functions/06-classical-total.yaml measures/03-quantum.yaml relations/03-quantum.yaml relations/07-parameters.yaml
  203. ['Buhrman, H.', 'de Wolf, R.']. A lower bound for quantum search of an ordered list.Information Processing Letters 70(5):205-209, 1999. doi
    used in functions/05-more.yaml
  204. ['Farhi, E.', 'Goldstone, J.', 'Gutmann, S.', 'Sipser, M.']. Invariant quantum algorithms for insertion into an ordered list.arXiv preprint, 1999. arXiv:quant-ph/9901059
    Defines the translation-invariant class and gives the exact 3-query algorithm for 52 items, 0.526 log_2 n.
    used in functions/05-more.yaml
  205. ['Nayak', 'A.', 'Wu', 'F.']. The quantum query complexity of approximating the median and related statistics.STOC 1999, 1999. arXiv:quant-ph/9804066
    Tight quantum bounds for approximate counting / median; the standard tool for Q of symmetric functions.
    used in functions/01-basic.yaml functions/04-partial-and-relations.yaml
  206. ['Nisan', 'N.', 'Rudich', 'S.', 'Saks', 'M.']. Products and help bits in decision trees.SIAM Journal on Computing 28(3):1035-1050, FOCS 1994, 1999. doi
    also cited here as NRS99
    Direct product in the weaker 'decision forest' model: k separate algorithms, each producing one output. Does not give a direct sum theorem for a single k-output algorithm, which is why JainKlauckSantha10 was needed.
    used in concepts.yaml
  207. ['Boyer, M.', 'Brassard, G.', 'Hoyer, P.', 'Tapp, A.']. Tight bounds on quantum searching.Fortschritte der Physik 46(4-5):493-505, 1998. arXiv:quant-ph/9605034doi
    Grover search when the number of marked items is unknown, in O(sqrt(N/m)) queries.
    used in functions/04-partial-and-relations.yaml
  208. ['Brassard, G.', 'Hoyer, P.', 'Tapp, A.']. Quantum cryptanalysis of hash and claw-free functions.LATIN 1998, 1998. arXiv:quant-ph/9705002
    The O(n^{1/3}) collision-finding algorithm.
    used in functions/04-partial-and-relations.yaml
  209. ['Evans', 'W.', 'Pippenger', 'N.']. Average-case lower bounds for noisy Boolean decision trees.SIAM Journal on Computing 28(2):433-446, 1998.
    Fourier-spectral lower bounds for the noisy model; recovers and strengthens the n log n parity bound to the average case.
    used in concepts.yaml functions/01-basic.yaml measures/02-randomized.yaml relations/04-composition.yaml
  210. ['Farhi, E.', 'Goldstone, J.', 'Gutmann, S.', 'Sipser, M.']. A limit on the speed of quantum computation for insertion into an ordered list.arXiv preprint, 1998. arXiv:quant-ph/9812057
    The log n / (2 log log n) lower bound.
    used in functions/05-more.yaml
  211. ['van Dam', 'W.']. Quantum oracle interrogation: getting all information for almost half the price.Proc. 39th FOCS, pages 362-367, 1998. arXiv:quant-ph/9805006
    Q(f) <= n/2 + O(sqrt n) for every f on n bits -- the universal quantum upper bound.
    used in relations/02-degree.yaml
  212. ['Vereshchagin', 'N. K.']. Randomized Boolean decision trees: several remarks.Theoretical Computer Science 207(2):329-342, 1998.
    Distributional characterisation of bounded-error expected query complexity; the bounded-error case of Yao's question.
    used in concepts.yaml measures/01-deterministic.yaml measures/02-randomized.yaml relations/07-parameters.yaml
  213. ['Bennett', 'C. H.', 'Bernstein', 'E.', 'Brassard', 'G.', 'Vazirani', 'U.']. Strengths and weaknesses of quantum computing.SIAM Journal on Computing 26(5):1510-1523, 1997. arXiv:quant-ph/9701001
    Q(OR) = Omega(sqrt(n)).
    used in functions/01-basic.yaml functions/02-composed.yaml functions/04-partial-and-relations.yaml
  214. ['Bernstein', 'E.', 'Vazirani', 'U.']. Quantum complexity theory.SIAM Journal on Computing 26(5):1411-1473, 1997.
    used in functions/04-partial-and-relations.yaml functions/05-more.yaml
  215. ['Simon', 'D. R.']. On the power of quantum computation.SIAM Journal on Computing 26(5):1474-1483, 1997.
    Exponential quantum speedup for a promise (partial) problem.
    used in functions/04-partial-and-relations.yaml
  216. ['von zur Gathen', 'J.', 'Roche', 'J. R.']. Polynomials with two values.Combinatorica 17(3):345-362, 1997.
    deg(f) = n - O(n^{0.548}) for all non-constant symmetric f.
    used in functions/01-basic.yaml measures/04-degree.yaml
  217. ['Dürr, C.', 'Høyer, P.']. A quantum algorithm for finding the minimum.1996. arXiv:quant-ph/9607014
    O(sqrt n) quantum queries to find the index of the minimum (equivalently maximum) of an n-element list, by repeated Grover search with a shrinking threshold.
    used in functions/01-basic.yaml
  218. ['Grover', 'L. K.']. A fast quantum mechanical algorithm for database search.STOC 1996, 1996. arXiv:quant-ph/9605043
    used in functions/01-basic.yaml functions/04-partial-and-relations.yaml
  219. ['Impagliazzo', 'R.']. Hard-core distributions for somewhat hard problems.FOCS 1995, 1995.
    not currently cited by any entry
  220. ['Lovász, L.', 'Naor, M.', 'Newman, I.', 'Wigderson, A.']. Search problems in the decision tree model.SIAM Journal on Discrete Mathematics 8(1):119-132, 1995. doi
    Foundational treatment of relations in the decision tree model; includes the identification of deterministic decision-tree depth for the false-clause search problem with tree-like resolution depth.
    used in functions/04-partial-and-relations.yaml functions/05-more.yaml relations/10-new-measures.yaml
  221. ['Nisan', 'N.', 'Wigderson', 'A.']. On rank vs. communication complexity.Combinatorica 15:557-565, 1995. doi
    also cited here as NW95
    Iterating Kushilevitz's 6-variable function: deg(f) = bs(f)^{1.63...}, i.e. exponent log_6 ... . Best known deg-vs-bs and deg-vs-s separation.
    used in functions/02-composed.yaml relations/02-degree.yaml tables/total-exponents.yaml
  222. ['Rubinstein', 'D.']. Sensitivity vs. block sensitivity of Boolean functions.Combinatorica 15:297-299, 1995. doi
    also cited here as Rub95
    First quadratic separation bs(f) = s(f)^2/2.
    used in concepts.yaml functions/02-composed.yaml open_problems.yaml relations/01-classical-core.yaml relations/08-fractional.yaml
  223. ['Santha', 'M.']. On the Monte Carlo Boolean decision tree complexity of read-once formulae.Random Structures & Algorithms 6(1):75-87, 1995.
    Bounded-error version of Saks-Wigderson: R(NAND-tree) = Theta(n^{0.7537...}).
    used in functions/02-composed.yaml measures/02-randomized.yaml open_problems.yaml
  224. ['Beigel', 'R.']. Perceptrons, PP, and the polynomial hierarchy.Computational Complexity 4:339-349, 1994.
    ODD-MAX-BIT: sign degree 1 but any low-weight PTF needs large degree; separates sdeg from deg-tilde and from D.
    used in functions/01-basic.yaml
  225. ['Feige', 'U.', 'Raghavan', 'P.', 'Peleg', 'D.', 'Upfal', 'E.']. Computing with Noisy Information.SIAM Journal on Computing 23(5):1001-1018, 1994. doi
    Introduces the noisy decision tree model N_p. Parity needs Theta(n log n) noisy queries; tight bounds for thresholds and symmetric functions.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/03-separating-total.yaml functions/06-classical-total.yaml measures/02-randomized.yaml measures/03-quantum.yaml open_problems.yaml relations/04-composition.yaml relations/07-parameters.yaml
  226. ['Nisan', 'N.', 'Smolensky', 'R.']. Unpublished; proof reproduced in [BdW02].1994.
    also cited here as NisanSmolensky94, NS94smolensky
    D(f) <= deg(f)^2 bs(f) <= 2 deg(f)^4.
    used in open_problems.yaml relations/02-degree.yaml
  227. ['Nisan', 'N.', 'Szegedy', 'M.']. On the degree of Boolean functions as real polynomials.Computational Complexity 4:301-313, 1994. doi
    bs <= 2 deg^2 and bs <= 6 deg-tilde^2; D = O(deg^8); the sqrt(n) approximating polynomial for OR.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/03-separating-total.yaml functions/04-partial-and-relations.yaml measures/01-deterministic.yaml measures/04-degree.yaml open_problems.yaml relations/01-classical-core.yaml relations/02-degree.yaml relations/09-chain.yaml relations/10-new-measures.yaml tables/total-exponents.yaml
  228. ['Koutsoupias', 'E.']. Improvements on Khrapchenko's theorem.Theoretical Computer Science 116(2):399-403, 1993.
    The measure K(f) later shown to equal spectral sensitivity lambda(f).
    used in measures/03-quantum.yaml
  229. ['Llewellyn, D. C.', 'Tovey, C.']. Dividing and conquering the square.Discrete Applied Mathematics 43(2):131-153, 1993. doi
    used in functions/05-more.yaml
  230. ['Deutsch', 'D.', 'Jozsa', 'R.']. Rapid solution of problems by quantum computation.Proc. Royal Society A 439:553-558, 1992.
    used in functions/04-partial-and-relations.yaml
  231. ['Paturi', 'R.']. On the degree of polynomials that approximate symmetric Boolean functions.STOC 1992, 1992. doi
    Tight characterisation of deg-tilde for symmetric functions.
    used in functions/01-basic.yaml functions/02-composed.yaml functions/04-partial-and-relations.yaml measures/04-degree.yaml relations/10-new-measures.yaml
  232. ['Nisan', 'N.']. CREW PRAMs and Decision Trees.SIAM Journal on Computing 20(6):999-1007, 1991. doi
    Introduces block sensitivity; proves C <= s*bs, bs <= 3R, D <= 27 R^3, and C = s = bs for monotone f.
    used in concepts.yaml functions/01-basic.yaml functions/03-separating-total.yaml functions/07-recent-separations.yaml measures/01-deterministic.yaml measures/02-randomized.yaml open_problems.yaml relations/01-classical-core.yaml relations/03-quantum.yaml relations/04-composition.yaml relations/08-fractional.yaml relations/09-chain.yaml relations/10-new-measures.yaml relations/11-lp-and-lower-bound-methods.yaml relations/14-sabotage-and-2026-results.yaml tables/total-exponents.yaml
  233. ['Reischuk', 'R.', 'Schmeltz', 'B.']. Reliable computation with noisy circuits and decision trees -- a general n log n lower bound.FOCS 1991, 1991.
    used in concepts.yaml measures/02-randomized.yaml relations/04-composition.yaml
  234. ['Ehrenfeucht', 'A.', 'Haussler', 'D.']. Learning decision trees from random examples.Information and Computation 82(3):231-246, 1989. doi
    Introduces the rank of a decision tree and shows rank-r trees are learnable in n^O(r) time; source of the leaf-count bound sum_{i<=r} C(d,i).
    used in functions/03-separating-total.yaml functions/05-more.yaml measures/01-deterministic.yaml relations/10-new-measures.yaml
  235. ['Llewellyn, D. C.', 'Tovey, C.', 'Trick, M.']. Local optimization on graphs.Discrete Applied Mathematics 23(2):157-178, 1989. doi
    Characterises deterministic local-search complexity by vertex cuts; erratum in DAM 46:93-94 (1993).
    used in functions/05-more.yaml
  236. ['Tardos', 'G.']. Query complexity, or why is it difficult to separate NP^A cap coNP^A from P^A by random oracles A?.Combinatorica 9:385-392, 1989. doi
    D(f) <= C0(f) * C1(f). Independently by Blum-Impagliazzo and Hartmanis-Hemachandra.
    used in functions/02-composed.yaml measures/01-deterministic.yaml relations/01-classical-core.yaml
  237. ['Wegener', 'I.', 'Zadori', 'L.']. A note on the relations between critical and sensitive complexity.Journal of Information Processing and Cybernetics 25:417-421, 1989.
    Sub-quadratic s-vs-C gaps predating Rubinstein.
    not currently cited by any entry
  238. ['Kahn', 'J.', 'Kalai', 'G.', 'Linial', 'N.']. The influence of variables on Boolean functions.FOCS 1988, 1988.
    used in concepts.yaml functions/01-basic.yaml measures/05-fourier.yaml relations/12-normalized.yaml
  239. ['Blum', 'M.', 'Impagliazzo', 'R.']. Generic oracles and oracle classes.FOCS 1987, 1987.
    Independent proof of D <= C0*C1.
    used in functions/02-composed.yaml relations/01-classical-core.yaml
  240. ['Hartmanis', 'J.', 'Hemachandra', 'L.']. One-way functions, robustness, and non-isomorphism of NP-complete sets.Structure in Complexity Theory, 1987.
    also cited here as HH91, HartmanisHemachandra91
    Independent proof of D <= C0*C1.
    used in functions/02-composed.yaml relations/01-classical-core.yaml
  241. ['Urquhart, A.']. Hard examples for resolution.Journal of the ACM 34(1):209-219, 1987. doi
    The Tseitin contradictions on bounded-degree expanders: the first exponential resolution size lower bound for a natural family, hence 2^{Omega(n)} decision-tree size for the corresponding false-vertex search problem.
    used in functions/05-more.yaml
  242. ['Saks', 'M.', 'Wigderson', 'A.']. Probabilistic Boolean decision trees and the complexity of evaluating game trees.FOCS 1986, 1986. doi
    R0(NAND-tree) = Theta(n^{0.7537...}); the alpha = log_2((1+sqrt(33))/4) exponent.
    used in functions/02-composed.yaml functions/06-classical-total.yaml measures/02-randomized.yaml open_problems.yaml relations/07-parameters.yaml relations/11-lp-and-lower-bound-methods.yaml
  243. ['Ben-Or', 'M.', 'Linial', 'N.']. Collective coin flipping, robust voting schemes and minima of Banzhaf values.FOCS 1985, 1985.
    used in functions/01-basic.yaml measures/05-fourier.yaml
  244. ['Snir', 'M.']. Lower bounds on probabilistic linear decision trees.Theoretical Computer Science 38:69-82, 1985.
    The randomized algorithm for the AND-OR / NAND tree.
    used in functions/02-composed.yaml functions/06-classical-total.yaml
  245. ['Wegener', 'I.']. The critical complexity of all (monotone) Boolean functions and monotone graph properties.Information and Control 67(1-3):212-222, 1985.
    The monotone address function shows Simon's s(f) >= (log n)/2 - O(log log n) bound is tight up to the lower-order term.
    not currently cited by any entry
  246. ['Kahn, J.', 'Saks, M.', 'Sturtevant, D.']. A topological approach to evasiveness.Combinatorica 4(4):297-306, 1984. doi
    Nontrivial monotone graph properties are evasive when the number of vertices is a prime power.
    used in functions/06-classical-total.yaml
  247. ['Turan, G.']. The critical complexity of graph properties.Information Processing Letters 18:151-153, 1984.
    Every non-trivial graph property on n vertices has critical complexity (sensitivity) s = Omega(n).
    used in open_problems.yaml
  248. ['Aldous, D.']. Minimization algorithms and random walk on the d-cube.Annals of Probability 11(2):403-413, 1983. doi
    The generic O(sqrt(N*Delta)) randomized local-search algorithm, and a 2^{n/2-o(n)} lower bound on the cube.
    used in functions/05-more.yaml
  249. ['Simon', 'H.-U.']. A tight Omega(log log n) bound on the time for parallel RAM's to compute nondegenerate Boolean functions.FCT, 1983.
    s(f) >= (log n - log log n)/2 for f depending on all n variables.
    used in measures/01-deterministic.yaml
  250. ['Yao', 'A. C.-C.']. Probabilistic computations: Toward a unified measure of complexity.FOCS 1977, 1977.
    Yao's minimax principle; raises the question of a distributional characterisation of R-bar_eps.
    used in concepts.yaml functions/01-basic.yaml functions/02-composed.yaml functions/06-classical-total.yaml measures/01-deterministic.yaml measures/02-randomized.yaml open_problems.yaml relations/07-parameters.yaml relations/11-lp-and-lower-bound-methods.yaml
  251. ['Bollobas, B.']. Complete subgraphs are elusive.Journal of Combinatorial Theory Series B 21:1-7, 1976. doi
    Containing a K_k is evasive for every m; hence D(triangle) = C(m,2) exactly.
    used in functions/05-more.yaml functions/06-classical-total.yaml
  252. ['Rivest, R. L.', 'Vuillemin, J.']. On recognizing graph properties from adjacency matrices.Theoretical Computer Science 3(3):371-384, 1976. doi
    Every nontrivial monotone graph property needs Omega(n^2) queries; the Aanderaa-Karp-Rosenberg conjecture asks for exactly binom(n,2).
    used in functions/06-classical-total.yaml
  253. ['Best, M. R.', 'van Emde Boas, P.', 'Lenstra, H. W.']. A sharpened version of the Aanderaa-Rosenberg conjecture.Mathematisch Centrum report ZW 30/74, Amsterdam, 1974.
    Source of the scorpion graphs: a nontrivial graph property decidable in O(n) queries out of binom(n,2).
    used in functions/06-classical-total.yaml
  254. ['Hellman', 'M. E.', 'Raviv', 'J.']. Probability of error, equivocation, and the Chernoff bound.IEEE Transactions on Information Theory 16(4):368-372, 1970. doi
    Error probability is at most half the conditional entropy: the direction of Fano's inequality that turns an entropy gap into a guessing advantage.
    used in concepts.yaml measures/02-randomized.yaml
  255. ['Minsky', 'M.', 'Papert', 'S.']. Perceptrons.MIT Press, Cambridge MA, 1969.
    Origin of sign/threshold degree. The theorem is deg_pm(AND_m o OR_b) = Omega(min{m, sqrt b}); maximised at b = m^2, giving sdeg = Theta(N^{1/3}) for the one-in-a-box function on N = m^3 bits.
    used in functions/01-basic.yaml functions/02-composed.yaml functions/04-partial-and-relations.yaml functions/06-classical-total.yaml measures/04-degree.yaml relations/10-new-measures.yaml
  256. ['Newman, D. J.']. Rational approximation to |x|.Michigan Mathematical Journal 11(1):11-14, 1964.
    The origin of the log-degree rational approximation to the absolute value, hence of rdeg(MAJ) = O(log n). Mahadev-de Wolf reprove it from a postselected quantum algorithm.
    used in functions/01-basic.yaml