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.
-
['Ambainis, Andris', 'Iraids, Jānis', 'Kokainis, Martins']. Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity.2026. arXiv:2609.11664Read 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.yamlfunctions/07-recent-separations.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlmeasures/07-sabotage-and-certification.yamlopen_problems.yamlrelations/04-composition.yamlrelations/14-sabotage-and-2026-results.yamltables/total-exponents.yaml -
['Blanc, G.', 'Docter, J.', 'Strassle, C.', 'Tan, L.-Y.']. Proof of the Aaronson–Ambainis Conjecture: An Exposition.2026. arXiv:2611.11626Cleaner exposition of the PSI/Turturean proof, organized into four steps. Parameters are not optimized.used in
measures/05-fourier.yamlopen_problems.yaml -
['Belovs, A.']. Tight quantum lower bound for k-distinctness.2026. arXiv:2604.05133Preprint. 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 -
['Ben-David, Shalev', 'Kothari, Robin']. Randomized query complexity can beat certificate complexity.2026. arXiv:2609.15063Theorem 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.yamlmeasures/01-deterministic.yamlrelations/14-sabotage-and-2026-results.yamltables/total-exponents.yaml -
['Cornelissen, A.', 'Gilani, A.', 'Patro, S.']. Quantum algorithms for path and cycle containment problems.2026. arXiv:2605.09017Preprint. 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 -
['Gu', 'Y.', 'Li', 'X.', 'Xu', 'Y.']. A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions.COLT 2026, 2026. arXiv:2606.11448General 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.yamlfunctions/01-basic.yamlfunctions/06-classical-total.yamlmeasures/02-randomized.yamlrelations/04-composition.yaml -
['Huffstutler, T.', 'Miloschewsky, D.', 'Podder, S.']. A short proof of the Aaronson-Ambainis Conjecture via the completion framework.2026. arXiv:2611.12795Shorter 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.yamlopen_problems.yaml -
['Kothari', 'R.', 'Kovacs-Deak', 'M.', 'Wang', 'D.', 'Yang', 'R. Z.']. Rational degree is polynomially related to degree.2026. arXiv:2601.08727also cited here as
KKW+26,KovacsDeak26Answers 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 infunctions/02-composed.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/02-degree.yamltables/total-exponents.yaml -
['Kayal, Chandrima', 'Laplante, Sophie', 'Larroque, Émile', 'Prūsis, Krišjānis', 'Vihrovs, Jevgēnijs']. Certification complexity of Boolean functions.2026. arXiv:2609.26757Read 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.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/07-recent-separations.yamlmeasures/01-deterministic.yamlmeasures/03-quantum.yamlmeasures/07-sabotage-and-certification.yamlopen_problems.yamlrelations/14-sabotage-and-2026-results.yamltables/total-exponents.yaml -
['Meiburg', 'A.']. Block Sensitivity can exceed Spectral Sensitivity Squared.2026. arXiv:2608.00851Refutes 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.yamlfunctions/02-composed.yamlmeasures/03-quantum.yamlrelations/14-sabotage-and-2026-results.yaml -
['Meiburg, A.']. No Perfect Randomized Composition.2026. arXiv:2610.31638Read 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.yamlfunctions/02-composed.yamlfunctions/07-recent-separations.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/04-composition.yamlrelations/11-lp-and-lower-bound-methods.yamlrelations/14-sabotage-and-2026-results.yaml -
['OpenAI']. A Nearly Quartic Separation Between Randomized and Quantum Query Complexity.2026. linkOctober 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.yamlmeasures/02-randomized.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/03-quantum.yamltables/total-exponents.yaml -
['OpenAI']. A superquadratic separation between sensitivity and block sensitivity.2026. linkSeptember 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.yamlfunctions/07-recent-separations.yamlmeasures/01-deterministic.yamlopen_problems.yamltables/total-exponents.yaml -
['Pabbaraju, Chirag']. Optimal Unambiguous DNFs and Alon-Saks-Seymour.SODA 2027 (camera-ready preprint), 2026. arXiv:2608.02533Read 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.yamlmeasures/01-deterministic.yamlrelations/01-classical-core.yamlrelations/14-sabotage-and-2026-results.yamltables/total-exponents.yaml -
['Pednekar, S.', 'Podder, S.']. A General Composition Theorem for Approximate Degree.2026. arXiv:2609.30139Read 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.yamlmeasures/03-quantum.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/04-composition.yaml -
['Pednekar, S.', 'Podder, S.']. On the Composition Theorem for Approximate Degree, Randomized and Exact Quantum Query Complexity.STOC 2027 submission, 2026. linkExpanded 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.yamlmeasures/02-randomized.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/04-composition.yaml -
['Prove2Me campaign contributors (including yousofy; see source attribution)']. Block Sensitivity vs. Sensitivity: exact exponent log(14055^8)/log(3738277295413674).2026. linkPublic 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.yamlfunctions/07-recent-separations.yamlmeasures/01-deterministic.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/14-sabotage-and-2026-results.yamltables/total-exponents.yaml -
['Physical Superintelligence (PSI)']. The Aaronson–Ambainis conjecture.2026. linkPSI 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.yamlopen_problems.yamlrelations/05-fourier.yaml -
['Turturean, D.']. A Proof of the Aaronson–Ambainis Conjecture.2026. arXiv:2611.09773PSI’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.yamlopen_problems.yamlrelations/05-fourier.yaml -
['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.21090doiEvery 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 -
['Gu', 'Y.', 'Li', 'X.', 'Xu', 'Y.']. Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold.COLT 2025, 2025. arXiv:2502.04632N_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.yamlmeasures/02-randomized.yamlmeasures/05-fourier.yamlrelations/04-composition.yaml -
['Hamoudi', 'Y.']. A Brief Introduction to Quantum Query Complexity.2025. arXiv:2508.08852not currently cited by any entry
-
['Jeffery, S.', 'Zur, S.']. Multidimensional quantum walks, with application to k-distinctness.STOC 2023, pp. 1125-1130; journal version in TheoretiCS, 2025. arXiv:2208.13492doiExtends 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 -
['Belovs, A.']. Global phase helps in quantum search: yet another look at the welded tree problem.arXiv preprint, 2024. arXiv:2404.19476A two-page proof of the optimal linear hitting time, via transducers and a modified electric quantum walk.used in
functions/05-more.yaml -
['Ben-David', 'S.', 'Kundu', 'S.']. Separations in query complexity for total search problems.2024. arXiv:2410.16245Alias of [BenDavidKundu24search]; kept because earlier data files cite this key.not currently cited by any entry
-
['Ben-David', 'S.', 'Kundu', 'S.']. Separations in query complexity for total search problems.2024. arXiv:2410.16245Query-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.yamlfunctions/04-partial-and-relations.yamlmeasures/04-degree.yamlmeasures/06-lp.yamlrelations/06-settings.yaml -
['Branzei, S.', 'Choo, D.', 'Recker, N. J.']. The sharp power law of local search on expanders.SODA 2024, pp. 1792-1809, 2024. arXiv:2305.08269doiRandomized local search on constant-degree expanders is Omega(sqrt n / log n), matching Aldous up to a log.used in
functions/05-more.yaml -
['Branzei, S.', 'Recker, N. J.']. A note on quantum lower bounds for local search via congestion and expansion.arXiv preprint, 2024. arXiv:2412.13345Q(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 -
['Cornelissen, Arjan', 'Mande, Nikhil S.', 'Patro, Subhasree']. Quantum Sabotage Complexity.2024. arXiv:2408.12595Sections 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.yamlfunctions/01-basic.yamlmeasures/03-quantum.yamlmeasures/07-sabotage-and-certification.yamlopen_problems.yamlrelations/14-sabotage-and-2026-results.yaml -
['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.08395doiA 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 -
['Sanyal', 'S.']. Randomized Query Composition and Product Distributions.STACS 2024; ACM Transactions on Computation Theory (2025), 2024. arXiv:2401.15352ECCC TR24-016RS(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.yamlfunctions/05-more.yamlfunctions/06-classical-total.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/04-composition.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Ambainis', 'A.', 'Belovs', 'A.']. An exponential separation between quantum query complexity and the polynomial degree.CCC 2023, 2023. arXiv:2301.09218doiPartial 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.yamlfunctions/04-partial-and-relations.yamlrelations/06-settings.yaml -
['Bun, M.', 'Voronova, N.']. Approximate degree lower bounds for oracle identification problems.TQC 2023, 1:1-1:19, 2023. arXiv:2303.03921doiApproximate 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 -
['Chattopadhyay', 'A.', 'Dahiya', 'Y.', 'Mahajan', 'M.']. Query Complexity of Search Problems.MFCS 2023; computational complexity (2025), 2023. ECCC TR23-039doiMulti-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.yamlfunctions/01-basic.yamlfunctions/04-partial-and-relations.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlrelations/06-settings.yamlrelations/13-definitional.yaml -
['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.03396CG, 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.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/04-partial-and-relations.yamlfunctions/05-more.yamlfunctions/06-classical-total.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlmeasures/03-quantum.yamlrelations/10-new-measures.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Childs, A. M.', 'Coudron, M.', 'Gilani, A. S.']. Quantum algorithms and the power of forgetting.ITCS 2023, 37:1-37:22, 2023. arXiv:2211.12447doiThe 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 -
['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.03900Composition 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.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlfunctions/05-more.yamlfunctions/06-classical-total.yamlopen_problems.yamlrelations/04-composition.yaml -
['Chugh', 'R.', 'Podder', 'S.', 'Sanyal', 'S.']. Decision Tree Complexity versus Block Sensitivity and Degree.FSTTCS 2023, 2023. arXiv:2209.08042Asks 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 -
['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.08004also cited here as
IJK+23,Iyer23Introduces rdeg, and collects the best known separation and upper-bound exponents between the classical and quantum measures.used inconcepts.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/04-partial-and-relations.yamlmeasures/03-quantum.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/02-degree.yamlrelations/09-chain.yamltables/total-exponents.yaml -
['Sherstov, A. A.', 'Thaler, J.']. Vanishing-error approximate degree and QMA complexity.Chicago Journal of Theoretical Computer Science 2023, article 3, 2023. arXiv:1909.07498eps-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.yamlfunctions/05-more.yaml -
['Ben-David', 'S.', 'Blais', 'E.', 'Goos, M.', 'Maystre', 'G.']. Randomised Composition and Small-Bias Minimax.FOCS 2022, 2022. arXiv:2208.12896Linearised 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.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlfunctions/05-more.yamlfunctions/07-recent-separations.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/04-composition.yamlrelations/07-parameters.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Bun', 'M.', 'Thaler', 'J.']. Approximate Degree in Classical and Quantum Computing.Foundations and Trends in Theoretical Computer Science 15(3-4), 2022. doiBook-length survey of approximate degree; the reference for everything deg-tilde.used in
functions/01-basic.yamlfunctions/05-more.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/10-new-measures.yaml -
['Yamakawa', 'T.', 'Zhandry', 'M.']. Verifiable Quantum Advantage without Structure.FOCS 2022, 2022. arXiv:2204.02063Total NP search problem (a relation) with exponential quantum query advantage, even against the uniform distribution.used in
functions/04-partial-and-relations.yaml -
['Anshu', 'A.', 'Ben-David', 'S.', 'Kundu', 'S.']. On query-to-communication lifting for adversary bounds.CCC 2021, 2021. arXiv:2012.03415doiTwo 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.yamlfunctions/05-more.yamlrelations/03-quantum.yamlrelations/06-settings.yamlrelations/10-new-measures.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['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.12629also cited here as
ABK+21Introduces 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 inconcepts.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlfunctions/07-recent-separations.yamlmeasures/01-deterministic.yamlmeasures/03-quantum.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/02-degree.yamlrelations/03-quantum.yamlrelations/14-sabotage-and-2026-results.yamltables/total-exponents.yaml -
['Atia, Y.', 'Chakraborty, S.']. Improved upper bounds for the hitting times of quantum walks.Physical Review A 104:032215, 2021. arXiv:2005.04062doiused in
functions/05-more.yaml -
['Bansal', 'N.', 'Sinha', 'M.']. k-Forrelation Optimally Separates Quantum and Classical Query Complexity.STOC 2021, 2021. arXiv:2008.07003also cited here as
BS21Q(f) = k vs R(f) = Omega-tilde(n^{1-1/k}).used inconcepts.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/03-quantum.yamlrelations/06-settings.yaml -
['Balodis', 'K.', 'Ben-David', 'S.', 'Goos, M.', 'Jain', 'S.', 'Kothari', 'R.']. Unambiguous DNFs and Alon-Saks-Seymour.FOCS 2021, 2021. arXiv:2102.08348doialso cited here as
BBG+22Cited 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 infunctions/03-separating-total.yamltables/total-exponents.yaml -
['Bravyi', 'S.', 'Gosset', 'D.', 'Grier', 'D.', 'Schaeffer', 'L.']. Classical algorithms for Forrelation.2021. arXiv:2102.06963Matching classical upper bound showing the SSW separation is optimal.used in
functions/04-partial-and-relations.yaml -
['Bun, M.', 'Thaler, J.']. The large-error approximate degree of AC^0.Theory of Computing 17(7):1-46 (APPROX/RANDOM 2019), 2021. doiThreshold degree of surjectivity: Theta-tilde(min{R, sqrt N}).used in
functions/05-more.yaml -
['Goldwasser', 'S.', 'Impagliazzo', 'R.', 'Pitassi', 'T.', 'Santhanam', 'R.']. On the pseudo-deterministic query complexity of NP search problems.CCC 2021, 2021. ECCC TR21-003Exponential separation between randomized and pseudo-deterministic query complexity; Omega(sqrt n) psD lower bound for SearchCNF.used in
functions/04-partial-and-relations.yamlmeasures/02-randomized.yamlrelations/06-settings.yaml -
['Goos, M.', 'Maystre', 'G.']. A Majority Lemma for Randomised Query Complexity.CCC 2021, 2021. ECCC TR21-024used in
concepts.yamlmeasures/02-randomized.yamlrelations/04-composition.yaml -
['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.10223also cited here as
SSW23Q(f) <= k vs R(f) = Omega-tilde(n^{1 - 1/2k}); optimal by Aaronson-Ambainis / BGGS.used inconcepts.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/03-quantum.yamlrelations/06-settings.yaml -
['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.10654also cited here as
BDG+20Concurrent 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 inconcepts.yamlmeasures/02-randomized.yamlrelations/04-composition.yaml -
['Belovs', 'A.', 'Lee', 'T.']. The quantum query complexity of composition with a relation.2020. arXiv:2004.06439Adversary bound for relations; perfect composition of a relation with a Boolean function.used in
measures/03-quantum.yaml -
['Ben-David', 'S.', 'Blais', 'E.']. A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions.FOCS 2020, 2020. arXiv:2002.10809R(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.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/04-partial-and-relations.yamlfunctions/05-more.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/04-composition.yamlrelations/13-definitional.yaml -
['Ben-David', 'S.', 'Blais', 'E.']. A New Minimax Theorem for Randomized Algorithms.FOCS 2020; Journal of the ACM 70(6) (2023), 2020. arXiv:2002.10802A single hard distribution that works at every bias level simultaneously; introduces noisy randomized query complexity noisyR and the forecasting-algorithm view.used in
concepts.yamlfunctions/04-partial-and-relations.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlrelations/04-composition.yaml -
['Carette, T.', 'Lauriere, M.', 'Magniez, F.']. Extended learning graphs for triangle finding.Algorithmica 82:1989-2005, 2020. arXiv:1609.07786Current record: O(m^{5/4}) with no logarithmic factors.used in
functions/05-more.yaml -
['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.08389doiused in
functions/05-more.yaml -
['Sherstov', 'A. A.']. Algorithmic polynomials.SIAM Journal on Computing 49(6), 2020. arXiv:1801.04607Near-optimal approximate degree upper bounds for surjectivity, element distinctness, etc.used in
functions/05-more.yaml -
['Tal', 'A.']. Towards Optimal Separations between Quantum and Randomized Query Complexities.FOCS 2020, 2020. arXiv:1912.12561Q = O(1) vs R = Omega(n^{2/3-eps}) via Fourier growth of decision trees.used in
functions/04-partial-and-relations.yamlmeasures/05-fourier.yaml -
['Anshu, A.', 'Boddu, N. G.', 'Touchette, D.']. Quantum log-approximate-rank conjecture is also false.FOCS 2019, pp. 982-994, 2019. arXiv:1811.10525doiused in
functions/06-classical-total.yaml -
['Blais', 'E.', 'Brody', 'J.']. Optimal Separation and Strong Direct Sum for Randomized Query Complexity.CCC 2019, 2019. arXiv:1908.01020Bounded-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.yamlopen_problems.yamlrelations/04-composition.yamlrelations/07-parameters.yaml -
['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-176doiSINK 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 -
['Gavinsky', 'D.', 'Lee', 'T.', 'Santha', 'M.', 'Sanyal', 'S.']. A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity.ICALP 2019, 2019. arXiv:1811.10752Max-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.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlfunctions/05-more.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/04-composition.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Huang', 'H.']. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture.Annals of Mathematics 190(3):949-955, 2019. arXiv:1907.00847deg(f) <= s(f)^2. The proof in fact gives deg(f) <= lambda(f)^2.used in
concepts.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlmeasures/01-deterministic.yamlmeasures/03-quantum.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/02-degree.yamlrelations/08-fractional.yamltables/total-exponents.yaml -
['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.yamlmeasures/05-fourier.yamlopen_problems.yaml -
['Sinha, M.', 'de Wolf, R.']. Exponential separation between quantum communication and logarithm of approximate rank.FOCS 2019, pp. 966-981, 2019. arXiv:1811.10090doiused in
functions/06-classical-total.yaml -
['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.57291-query quantum vs Omega-tilde(sqrt(n)) randomized; conjectured k-Forrelation separation.used in
functions/04-partial-and-relations.yamlfunctions/05-more.yaml -
['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.08985For total functions, the classical adversary CA(f) = Theta(fbs(f)); they can be far apart for partial functions.used in
concepts.yamlfunctions/01-basic.yamlfunctions/03-separating-total.yamlfunctions/06-classical-total.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Ambainis', 'A.']. Understanding Quantum Algorithms via Query Complexity.Proc. ICM 2018, 2018. arXiv:1712.06349not currently cited by any entry
-
['Ambainis', 'A.', 'Prusis, K.', 'Vihrovs', 'J.']. On Block Sensitivity and Fractional Block Sensitivity.Lobachevskii Journal of Mathematics 39(7):967-969, 2018. arXiv:1710.05108Simpler construction for the fbs vs bs 3/2 separation, with a better constant.used in
open_problems.yamlrelations/08-fractional.yaml -
['Ben-David', 'S.', 'Kothari', 'R.']. Randomized query complexity of sabotaged and composed functions.Theory of Computing 14(5), ICALP 2016, 2018. arXiv:1605.09071Sabotage 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.yamlfunctions/01-basic.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlfunctions/05-more.yamlfunctions/06-classical-total.yamlmeasures/02-randomized.yamlmeasures/06-lp.yamlopen_problems.yamlrelations/04-composition.yaml -
['Bun', 'M.', 'Kothari', 'R.', 'Thaler', 'J.']. The polynomial method strikes back: tight quantum query bounds via dual polynomials.STOC 2018, 2018. arXiv:1710.09079used in
functions/05-more.yaml -
['Chistopolskaya, A.', 'Podolskii, V. V.']. Parity decision tree complexity is greater than granularity.arXiv preprint, 2018. arXiv:1810.08668ECCC TR18-174D_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.yamlfunctions/02-composed.yamlfunctions/06-classical-total.yaml -
['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-052used in
functions/01-basic.yamlfunctions/03-separating-total.yamlrelations/04-composition.yamltables/total-exponents.yaml -
['Goos, M.', 'Pitassi', 'T.', 'Watson', 'T.']. Deterministic Communication vs. Partition Number.SIAM Journal on Computing 47(6), FOCS 2015, 2018. ECCC TR15-050Total function with D = Omega-tilde(UC^2) / D vs subcube partition; used for the D vs deg entry.used in
concepts.yamlfunctions/01-basic.yamlfunctions/03-separating-total.yamlmeasures/01-deterministic.yamlopen_problems.yamlrelations/02-degree.yamltables/total-exponents.yaml -
['Li', 'Y.']. Conflict complexity is lower bounded by block sensitivity.2018. arXiv:1810.08873used in
functions/01-basic.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlfunctions/07-recent-separations.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/04-composition.yaml -
['Sanyal', 'S.']. A composition theorem via conflict complexity.2018. arXiv:1801.03285Introduces conflict complexity chi(g); R(f o g^n) = Omega(R(f) chi(g)).used in
concepts.yamlfunctions/03-separating-total.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/04-composition.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Sherstov, A. A.']. The power of asymmetry in constant-depth circuits.SIAM Journal on Computing 47(6):2362-2434 (FOCS 2015), 2018. ECCC TR15-147Remark 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 -
['Aaronson, S.', 'Chen, L.']. Complexity-theoretic foundations of quantum supremacy experiments.CCC 2017, 22:1-22:67, 2017. arXiv:1612.05903doiSection 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 -
['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.04719also cited here as
ABB+17Cubic-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 infunctions/03-separating-total.yamlmeasures/02-randomized.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/02-degree.yamlrelations/03-quantum.yamltables/total-exponents.yaml -
['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.00335used in
measures/02-randomized.yamlopen_problems.yamlrelations/04-composition.yaml -
['Ben-David', 'S.', 'Hatami', 'P.', 'Tal', 'A.']. Low-Sensitivity Functions from Unambiguous Certificates.ITCS 2017, 2017. arXiv:1605.07084Total function with D(f) = Omega-tilde(s(f)^3); also C(f) = Omega(UC_min(f)^{1.22}).used in
functions/01-basic.yamlfunctions/03-separating-total.yamlfunctions/05-more.yamlmeasures/01-deterministic.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/10-new-measures.yamltables/total-exponents.yaml -
['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.05784also cited here as
BT20,BT17Cited 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 inmeasures/04-degree.yamlrelations/02-degree.yamltables/total-exponents.yaml -
['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-123Uses 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
-
['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-123Introduces 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.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlrelations/01-classical-core.yamlrelations/09-chain.yamlrelations/10-new-measures.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Liu, R. P.']. Some upper and lower bounds regarding query complexity.MMath thesis, University of Waterloo (Combinatorics & Optimization), 2017. linkChapter 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 -
['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.06025Contains the clean special case of Samorodnitsky's inequality (noise beats erasure) used to prove Rna = O(noisyRna).used in
concepts.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/04-composition.yaml -
['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-049doiStructure 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
-
['Aaronson', 'S.', 'Ben-David', 'S.', 'Kothari', 'R.']. Separations in Query Complexity Using Cheat Sheets.STOC 2016, 2016. arXiv:1511.01937Cheat-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.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlopen_problems.yamlrelations/02-degree.yamlrelations/03-quantum.yamltables/total-exponents.yaml -
['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.01210A 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.yamlrelations/01-classical-core.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['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.5793Improves the bound to O(d^2) in general and O(d log d) for homogeneous functions.used in
measures/05-fourier.yamlopen_problems.yamlrelations/05-fourier.yaml -
['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 -
['Goos, M.', 'Jayram, T. S.']. A composition theorem for conical juntas.CCC 2016, LIPIcs 50, 5:1-5:16, 2016. ECCC TR15-167Degree 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.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['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.0630C vs RC quadratic; RC vs bs to the power 3/2.used in
functions/03-separating-total.yamlmeasures/01-deterministic.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/08-fractional.yamlrelations/10-new-measures.yamltables/total-exponents.yaml -
['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-199Under 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
-
['Kulkarni', 'R.', 'Tal', 'A.']. On Fractional Block Sensitivity.Chicago Journal of Theoretical Computer Science 2016(8), 2016. ECCC TR13-168fbs = 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.yamlfunctions/01-basic.yamlfunctions/03-separating-total.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlmeasures/03-quantum.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/02-degree.yamlrelations/08-fractional.yamlrelations/10-new-measures.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['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-192R_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 -
['Samorodnitsky', 'A.']. On the entropy of a noisy function.IEEE Transactions on Information Theory 62(10):5446-5464, 2016. arXiv:1508.01464also cited here as
Sam16,Sam15For 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 inconcepts.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/04-composition.yaml -
['Balodis, K.', 'Iraids, J.']. Quantum lower bound for graph collision implies lower bound for triangle detection.2015. arXiv:1507.03885used in
functions/05-more.yaml -
['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.1505Introduces 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.yamlfunctions/05-more.yamlfunctions/06-classical-total.yamlmeasures/06-lp.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Kothari', 'R.', 'Racicot-Desloges', 'D.', 'Santha', 'M.']. Separating Decision Tree Complexity from Subcube Partition Complexity.RANDOM 2015, 2015. arXiv:1504.01339used in
functions/03-separating-total.yamlmeasures/01-deterministic.yamlrelations/01-classical-core.yaml -
['Mahadev', 'U.', 'de Wolf', 'R.']. Rational approximations and quantum algorithms with postselection.Quantum Information and Computation 15(3-4), 2015. arXiv:1401.0912PostQ_eps(f) = Theta(rdeg_eps(f)).used in
functions/01-basic.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlfunctions/05-more.yamlfunctions/06-classical-total.yamlmeasures/03-quantum.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/03-quantum.yamlrelations/09-chain.yamlrelations/13-definitional.yaml -
['Aaronson', 'S.', 'Ambainis', 'A.']. The Need for Structure in Quantum Speedups.Theory of Computing 10:133-166, ITCS 2011, 2014. arXiv:0911.0996R(f) = O(Q(f)^{2 d}) style results for low-degree bounded functions; the Aaronson-Ambainis conjecture on influential variables.used in
concepts.yamlfunctions/04-partial-and-relations.yamlmeasures/05-fourier.yamlopen_problems.yamlrelations/06-settings.yaml -
['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.0717Total 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
-
['Backurs', 'A.', 'Bavarian', 'M.']. On the sum of L1 influences.CCC 2014, 2014. arXiv:1302.4625Total 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.yamlopen_problems.yaml -
['Beimel', 'A.', 'Ben Daniel', 'S.', 'Kushilevitz', 'E.', 'Weinreb', 'E.']. Choosing, agreeing, and eliminating in communication complexity.Computational Complexity 23:1-42, 2014. doiThe communication-complexity ancestor of the selection problem: solve any one of k given instances.used in
measures/02-randomized.yaml -
['Belovs, A.', 'Rosmanis, A.']. On the power of non-adaptive learning graphs.Computational Complexity 23(2):323-354 (CCC 2013), 2014. arXiv:1210.3279Prop. 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 -
['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. doialso cited here as
CK14The '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 inconcepts.yaml -
['Goos, M.', 'Pitassi, T.']. Communication lower bounds via critical block sensitivity.STOC 2014; SIAM Journal on Computing 47(5), 2014. arXiv:1311.2355Defines 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.yamlfunctions/02-composed.yamlfunctions/04-partial-and-relations.yamlfunctions/05-more.yamlmeasures/01-deterministic.yamlrelations/10-new-measures.yaml -
['Le Gall, F.']. Improved quantum algorithm for triangle finding via combinatorial arguments.FOCS 2014, 2014. arXiv:1407.0085Theorem 1.1: O-tilde(m^{5/4}), and it finds the triangle.used in
functions/05-more.yaml -
['Montanaro', 'A.']. A composition theorem for decision tree complexity.Chicago Journal of Theoretical Computer Science 2014, Article 6, 2014. arXiv:1302.4207also cited here as
Mon14D(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 inconcepts.yamlrelations/04-composition.yaml -
["O'Donnell", 'R.']. Analysis of Boolean Functions.Cambridge University Press, 2014. linkStandard reference for influence, noise sensitivity, Fourier weight, spectral norm.used in
concepts.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/06-classical-total.yamlmeasures/05-fourier.yamlrelations/05-fourier.yamlrelations/10-new-measures.yamlrelations/12-normalized.yaml -
['Sherstov, A. A.']. Breaking the Minsky-Papert barrier for constant-depth circuits.STOC 2014, 2014. doiSystematic use of one-sided approximate degree (deg_+) for AC^0 lower bounds.used in
measures/04-degree.yamlrelations/10-new-measures.yaml -
['Ambainis', 'A.']. Superlinear Advantage for Exact Quantum Algorithms.STOC 2013, 2013. arXiv:1211.0721also cited here as
Amb13First total function with QE(f) = O(D(f)^{1-eps}); gives the 1.15 exponents in the QE column.used infunctions/03-separating-total.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/03-quantum.yamltables/total-exponents.yaml -
['Ambainis', 'A.', 'Iraids', 'J.', 'Smotrovs', 'J.']. Exact quantum query complexity of EXACT and THRESHOLD.TQC 2013, 2013. arXiv:1302.1235used in
functions/01-basic.yamlfunctions/03-separating-total.yamlmeasures/03-quantum.yaml -
['Goldreich', 'O.', 'Goldwasser', 'S.', 'Ron', 'D.']. On the possibilities and limitations of pseudodeterministic algorithms.ITCS 2013, 2013. ECCC TR12-101Introduces pseudo-determinism; quartic relation between deterministic and pseudo-deterministic query complexity of search problems.used in
functions/04-partial-and-relations.yamlmeasures/02-randomized.yamlrelations/06-settings.yamlrelations/13-definitional.yaml -
['Jeffery, S.', 'Kothari, R.', 'Magniez, F.']. Nested quantum walks with quantum data structures.SODA 2013, pp. 1474-1485, 2013. arXiv:1210.1199used in
functions/05-more.yaml -
['Lee', 'T.', 'Roland', 'J.']. A strong direct product theorem for quantum query complexity.Computational Complexity 22(2):429-462, CCC 2012, 2013. arXiv:1104.4468also cited here as
LR11,LR12Quantum 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 inconcepts.yamlopen_problems.yamlrelations/04-composition.yaml -
['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 -
['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.1014Theorem 7: O(m^{9/7}). Not arXiv:1109.5135, which gives only m^{35/27} for the triangle.used in
functions/05-more.yaml -
['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.0110doiused in
functions/06-classical-total.yaml -
['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
-
['Tal', 'A.']. Properties and Applications of Boolean Function Composition.ITCS 2013, 2013. ECCC TR12-163Composition behaviour of s, bs, C, deg, deg-tilde, and the 'sensitivity composes' results.used in
concepts.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlmeasures/01-deterministic.yamlopen_problems.yamlrelations/04-composition.yamlrelations/08-fractional.yamlrelations/10-new-measures.yaml -
['Tsang', 'H. Y.', 'Wong', 'C. H.', 'Xie', 'N.', 'Zhang', 'S.']. Fourier sparsity, spectral norm, and the log-rank conjecture.FOCS 2013, 2013. arXiv:1304.1245deg(f) = O(log spar(f)) style bounds; the log-rank conjecture connection.used in
concepts.yamlfunctions/01-basic.yamlmeasures/01-deterministic.yamlmeasures/05-fourier.yamlopen_problems.yamlrelations/05-fourier.yaml -
['Beame, P.', 'Machmouchi, W.']. The quantum query complexity of AC^0.Quantum Information and Computation 12(7-8):670-676, 2012. arXiv:1008.2422Omega(n/log n) quantum queries for an AC^0 function; Omega(n) element queries for ONTO.used in
functions/05-more.yaml -
['Belovs, A.']. Learning-graph-based quantum algorithm for k-distinctness.FOCS 2012, 2012. arXiv:1205.1534used in
functions/05-more.yaml -
['Belovs, A.']. Span programs for functions with constant-sized 1-certificates.STOC 2012, 2012. arXiv:1105.4024Learning graphs; Theorem 8 gives O(m^{35/27}) for triangle finding.used in
functions/05-more.yaml -
['Drucker', 'A.']. Improved direct product theorems for randomized query complexity.Computational Complexity 21(2):197-244, CCC 2011, 2012. arXiv:1005.0644Direct product: solving k independent copies of f with fewer than ~k R(f) queries succeeds with exponentially small probability.used in
concepts.yamlopen_problems.yamlrelations/04-composition.yaml -
['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.yamlfunctions/05-more.yaml -
['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 -
['Sherstov', 'A. A.']. Making polynomials robust to noise.STOC 2012; Theory of Computing 9:593-615 (2013), 2012. doialso cited here as
Sherstov12Every 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 inconcepts.yamlfunctions/02-composed.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/04-composition.yaml -
['Ambainis', 'A.', 'Sun', 'X.']. New separation between s(f) and bs(f).2011. arXiv:1108.3494ECCC TR11-116bs(f) >= (2/3) s(f)^2 - (1/3) s(f); the best known constant in the bs-vs-s separation.used in
concepts.yamlfunctions/02-composed.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/08-fractional.yaml -
['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 -
['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.yamlopen_problems.yaml -
['Hatami', 'P.', 'Kulkarni', 'R.', 'Pankratov', 'D.']. Variations on the Sensitivity Conjecture.Theory of Computing Library, Graduate Surveys 4, 2011. doiSurvey of s vs bs vs C vs deg, pre-Huang.used in
concepts.yaml -
['Lee', 'T.', 'Mittal', 'R.', 'Reichardt', 'B. W.', 'Spalek, R.', 'Szegedy', 'M.']. Quantum query complexity of state conversion.FOCS 2011, 2011. arXiv:1011.3020Extends Adv^pm = Theta(Q) to non-Boolean output and state conversion.used in
concepts.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlmeasures/03-quantum.yamlrelations/03-quantum.yamlrelations/04-composition.yamlrelations/06-settings.yaml -
['Reichardt', 'B. W.']. Reflections for quantum query algorithms.SODA 2011, 2011. arXiv:1005.1601Q(f) = Theta(Adv^pm(f)) for all (partial) Boolean functions: the adversary bound is tight.used in
concepts.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/03-quantum.yamlrelations/04-composition.yamlrelations/06-settings.yaml -
['Aaronson', 'S.']. BQP and the polynomial hierarchy.STOC 2010, 2010. arXiv:0910.4698Fourier checking; introduces the forrelation-style separations.used in
functions/05-more.yaml -
['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.1291also cited here as
ACGT09Shows 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 inconcepts.yamlrelations/04-composition.yaml -
['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/0703015Discrete-query version of the NAND-tree algorithm; general AND-OR formulas.used in
functions/02-composed.yaml -
['Jain', 'R.', 'Klauck', 'H.']. The partition bound for classical communication complexity and query complexity.CCC 2010, 2010. arXiv:0910.4266Introduces 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.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlfunctions/05-more.yamlfunctions/06-classical-total.yamlmeasures/06-lp.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['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.0105Direct sum for D and R: computing k copies costs k times as much, up to constants.used in
concepts.yamlopen_problems.yamlrelations/04-composition.yaml -
['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 -
['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. doiused in
functions/05-more.yaml -
['Zhang, S.']. Tight bounds for randomized and quantum local search.SIAM Journal on Computing 39(3):948-977 (STACS 2006), 2009. arXiv:quant-ph/0504085doiSettles 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 -
['Aaronson', 'S.']. Quantum certificate complexity.Journal of Computer and System Sciences 74(3):313-322, CCC 2003, 2008. arXiv:quant-ph/0210020Introduces randomized certificate complexity RC and quantum certificate complexity QC; QC = Theta(sqrt(RC)).used in
concepts.yamlfunctions/01-basic.yamlfunctions/04-partial-and-relations.yamlfunctions/06-classical-total.yamlfunctions/07-recent-separations.yamlmeasures/01-deterministic.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/03-quantum.yamlrelations/08-fractional.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Childs, A. M.', 'Lee, T.']. Optimal quantum adversary lower bounds for ordered search.ICALP 2008, pp. 869-880, 2008. arXiv:0708.3396doiThe 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 -
['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.1816deg~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 -
['Farhi', 'E.', 'Goldstone', 'J.', 'Gutmann', 'S.']. A quantum algorithm for the Hamiltonian NAND tree.Theory of Computing 4:169-190, 2008. arXiv:quant-ph/0702144Continuous-time O(sqrt(n)) algorithm for the balanced NAND tree.used in
functions/02-composed.yaml -
['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/0311189A Kolmogorov-complexity form of the classical adversary.used in
measures/02-randomized.yamlrelations/13-definitional.yaml -
['Sherstov', 'A. A.']. Approximate inclusion-exclusion for arbitrary symmetric functions.CCC 2008; Computational Complexity 18(2), 2008. doiFirst characterisation of the eps-approximate degree of symmetric Boolean functions, up to logs.used in
relations/07-parameters.yaml -
['Spalek, R.']. The multiplicative quantum adversary.CCC 2008, pp. 237-248, 2008. arXiv:quant-ph/0703237doiAt 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.yamlfunctions/04-partial-and-relations.yamlmeasures/03-quantum.yamlrelations/03-quantum.yamlrelations/04-composition.yaml -
['Ambainis', 'A.']. Quantum walk algorithm for element distinctness.SIAM Journal on Computing 37(1):210-239, 2007. arXiv:quant-ph/0311001used in
functions/04-partial-and-relations.yamlfunctions/05-more.yaml -
['Ben-Or, M.', 'Hassidim, A.']. Quantum search in an ordered list via adaptive learning.arXiv preprint, 2007. arXiv:quant-ph/0703231Expected 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 -
['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/0309220Among 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 -
['Chakrabarti, A.', 'Khot, S.']. Improved lower bounds on the randomized complexity of graph properties.Random Structures & Algorithms 30(3):427-440 (ICALP 2001), 2007. doiEvery 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 -
['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/0608161doiExact 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 -
['Hoyer, P.', 'Lee, T.', 'Spalek, R.']. Negative weights make adversaries stronger.STOC 2007, 2007. arXiv:quant-ph/0611054The general (negative-weight) adversary bound Adv^pm.used in
concepts.yamlfunctions/02-composed.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/03-quantum.yamlrelations/04-composition.yaml -
['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/0402123also cited here as
KSdW07,KlauckSpalekdeWolf07First 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 inconcepts.yamlrelations/04-composition.yaml -
['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/0310134used in
functions/05-more.yaml -
['Aaronson', 'S.']. Lower bounds for local search by quantum arguments.SIAM Journal on Computing 35(4):804-824, 2006. arXiv:quant-ph/0307149The classical adversary method (relational adversary).used in
functions/04-partial-and-relations.yamlfunctions/05-more.yamlmeasures/02-randomized.yamlrelations/13-definitional.yaml -
['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/0401091doiAdjacency-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 -
['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 -
['Spalek, R.', 'Szegedy, M.']. All quantum adversary methods are equivalent.Theory of Computing 2:1-18, 2006. arXiv:quant-ph/0409116Shows the many published positive-weight adversary formulations coincide, and establishes the certificate-complexity barrier Adv(f) <= sqrt(C0(f) C1(f)).used in
concepts.yamlfunctions/04-partial-and-relations.yamlfunctions/05-more.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/03-quantum.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Verhoeven, Y. F.']. Enhanced algorithms for local search.Information Processing Letters 97(5):171-176, 2006. doiO(sqrt k log log k) quantum local search on the two-dimensional grid, via graph genus.used in
functions/05-more.yaml -
['Aaronson, S.']. Quantum computing, postselection, and probabilistic polynomial-time.Proceedings of the Royal Society A 461(2063):3473-3482, 2005. arXiv:quant-ph/0412187PostBQP = PP. Also the first postselected query algorithm for majority, later improved to optimal by Mahadev-de Wolf.used in
functions/01-basic.yaml -
['Aaronson', 'S.']. Quantum computing, postselection, and probabilistic polynomial-time.Proc. Royal Society A 461:3473-3482, 2005. arXiv:quant-ph/0412187used in
measures/03-quantum.yaml -
['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/0305179doiused in
functions/04-partial-and-relations.yaml -
['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/0309220Robust 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.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlfunctions/06-classical-total.yamlmeasures/02-randomized.yamlmeasures/03-quantum.yamlrelations/03-quantum.yamlrelations/13-definitional.yaml -
['Hoyer, P.', 'Spalek, R.']. Lower bounds on quantum query complexity.Bulletin of the EATCS 87:78-103, 2005. arXiv:quant-ph/0509153Survey. 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 -
['Kutin, S.']. Quantum lower bound for the collision problem with small range.Theory of Computing 1(2):29-36, 2005. arXiv:quant-ph/0304162doiused in
functions/04-partial-and-relations.yaml -
['Midrijanis, G.']. On randomized and quantum query complexities.2005. arXiv:quant-ph/0501142R0(f) = O(R(f)^2 log n); improved to O(R^2 log R) by [KulkarniTal16].not currently cited by any entry
-
["O'Donnell", 'R.', 'Saks', 'M.', 'Schramm', 'O.', 'Servedio', 'R.']. Every decision tree has an influential variable.FOCS 2005, 2005. arXiv:cs/0508071The 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.yamlmeasures/05-fourier.yamlopen_problems.yamlrelations/05-fourier.yaml -
['Zhang', 'S.']. On the power of Ambainis lower bounds.Theoretical Computer Science 339(2-3):241-256, 2005. arXiv:quant-ph/0311060Independently proves the certificate-complexity barrier for the positive-weight adversary method.used in
concepts.yamlfunctions/04-partial-and-relations.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/03-quantum.yaml -
['Aaronson, S.', 'Shi, Y.']. Quantum lower bounds for the collision and the element distinctness problems.Journal of the ACM 51(4):595-605, 2004. doiThe 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.yamlrelations/03-quantum.yaml -
['Kenyon', 'C.', 'Kutin', 'S.']. Sensitivity, block sensitivity, and l-block sensitivity of Boolean functions.Information and Computation 189(1):43-53, 2004. doibs_l(f) = O(s(f)^l); in particular bs_2 = O(s^2).used in
functions/02-composed.yamlmeasures/01-deterministic.yamlopen_problems.yamlrelations/01-classical-core.yaml -
['Midrijanis, G.']. Exact quantum query complexity for total Boolean functions.2004. arXiv:quant-ph/0403168D(f) = O(deg(f)^3), improving Nisan-Smolensky's deg^4.used in
functions/03-separating-total.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/02-degree.yamlrelations/03-quantum.yamltables/total-exponents.yaml -
['Shaltiel', 'R.']. Towards proving strong direct product theorems.Computational Complexity 12(1-2):1-22, CCC 2001, 2004. doialso cited here as
Sha01,Sha04The 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 inconcepts.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/04-composition.yaml -
['Aaronson, S.']. Quantum lower bound for recursive Fourier sampling.Quantum Information and Computation 3(2):165-174, 2003. arXiv:quant-ph/0209060used in
functions/05-more.yaml -
['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.yamlrelations/03-quantum.yaml -
['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/0209131doiIntroduces 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 -
['de Wolf', 'R.']. Nondeterministic quantum query and communication complexities.SIAM Journal on Computing 32(3):681-699, 2003. arXiv:cs/0001014Nondeterministic degree ndeg and nondeterministic quantum query complexity NQ = ceil(ndeg/2).used in
functions/01-basic.yamlfunctions/02-composed.yamlfunctions/04-partial-and-relations.yamlfunctions/05-more.yamlfunctions/06-classical-total.yamlmeasures/01-deterministic.yamlmeasures/03-quantum.yamlmeasures/04-degree.yamlrelations/03-quantum.yamlrelations/13-definitional.yaml -
['Fenner, S.', 'Zhang, Y.']. A note on the classical lower bound for a hybrid quantum-classical algorithm.arXiv preprint, 2003. arXiv:quant-ph/0312230Improves the welded-trees classical lower bound to 2^{n/3}.used in
functions/05-more.yaml -
['Fortnow', 'L.']. Rational functions and decision-tree complexity (blog post).2003. linkWhere 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
-
['Hoyer, P.', 'Mosca', 'M.', 'de Wolf', 'R.']. Quantum search on bounded-error inputs.ICALP 2003, 2003. arXiv:quant-ph/0304052Q(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.yamlfunctions/02-composed.yamlfunctions/06-classical-total.yaml -
['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 -
['Ambainis', 'A.']. Quantum lower bounds by quantum arguments.Journal of Computer and System Sciences 64(4):750-767, 2002. arXiv:quant-ph/0002066The (positive-weight) adversary method.used in
concepts.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/03-quantum.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Buhrman', 'H.', 'de Wolf', 'R.']. Complexity measures and decision tree complexity: a survey.Theoretical Computer Science 288(1):21-43, 2002. doilinkThe 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.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlmeasures/03-quantum.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/02-degree.yamlrelations/03-quantum.yamlrelations/05-fourier.yamlrelations/06-settings.yamlrelations/09-chain.yamlrelations/10-new-measures.yamlrelations/13-definitional.yaml -
['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
-
['Chakrabarti, A.', 'Khot, S.', 'Shi, Y.']. Evasiveness of subgraph containment and related properties.SIAM Journal on Computing 31(3):866-875, 2002. doiused in
functions/05-more.yaml -
['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/0102078doiQ(ordered search) >= (ln n - 1)/pi, by a weighted all-pairs inner-product argument.used in
functions/05-more.yaml -
['Lovasz, L.', 'Young, N. E.']. Lecture notes on evasiveness of graph properties.arXiv preprint (Princeton TR 317-91, 1994), 2002. arXiv:cs/0205031used in
functions/06-classical-total.yaml -
['Savicky, P.']. On determinism versus unambiguous nondeterminism for decision trees.ECCC report TR02-009, 2002. ECCC TR02-009also cited here as
Sav02The earliest of the three independent proofs that D composes exactly; the composition theorem is a lemma on the way to D vs UC.used inconcepts.yamlrelations/04-composition.yaml -
['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/9802049The polynomial method. deg <= 2 QE, deg-tilde <= 2 Q, D <= C1*bs, D = O(deg-tilde^6).used in
functions/01-basic.yamlfunctions/02-composed.yamlfunctions/04-partial-and-relations.yamlfunctions/07-recent-separations.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlmeasures/03-quantum.yamlmeasures/04-degree.yamlmeasures/07-sabotage-and-certification.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/02-degree.yamlrelations/03-quantum.yamlrelations/06-settings.yamlrelations/07-parameters.yamlrelations/08-fractional.yamlrelations/09-chain.yaml -
['Ben-Sasson, E.', 'Wigderson, A.']. Short proofs are narrow -- resolution made simple.Journal of the ACM 48(2):149-169, 2001. doiSize-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.yamlfunctions/05-more.yaml -
['de Wolf', 'R.']. Characterization of non-deterministic quantum query and quantum communication complexity.CCC 2000, 2000. arXiv:cs/0001014Journal version is [deWolf03]. Defines ndeg and shows NQ(f) = ceil(ndeg(f)/2).used in
functions/01-basic.yaml -
['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. doiTotal 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.yamlrelations/05-fourier.yaml -
['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/9811080also cited here as
Ambainis99Almost all f have deg-tilde(f) >= n/2 - O(sqrt(n log n)), hence Q(f) >= n/4 - o(n).used inrelations/02-degree.yaml -
['Ambainis, A.']. A better lower bound for quantum algorithms searching an ordered list.FOCS 1999, pp. 352-357, 1999. arXiv:quant-ph/9902053doiused in
functions/05-more.yaml -
['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/9904019doialso cited here as
BCdWZ99Q_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 inconcepts.yamlfunctions/01-basic.yamlfunctions/06-classical-total.yamlmeasures/03-quantum.yamlrelations/03-quantum.yamlrelations/07-parameters.yaml -
['Buhrman, H.', 'de Wolf, R.']. A lower bound for quantum search of an ordered list.Information Processing Letters 70(5):205-209, 1999. doiused in
functions/05-more.yaml -
['Farhi, E.', 'Goldstone, J.', 'Gutmann, S.', 'Sipser, M.']. Invariant quantum algorithms for insertion into an ordered list.arXiv preprint, 1999. arXiv:quant-ph/9901059Defines 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 -
['Nayak', 'A.', 'Wu', 'F.']. The quantum query complexity of approximating the median and related statistics.STOC 1999, 1999. arXiv:quant-ph/9804066Tight quantum bounds for approximate counting / median; the standard tool for Q of symmetric functions.used in
functions/01-basic.yamlfunctions/04-partial-and-relations.yaml -
['Nisan', 'N.', 'Rudich', 'S.', 'Saks', 'M.']. Products and help bits in decision trees.SIAM Journal on Computing 28(3):1035-1050, FOCS 1994, 1999. doialso cited here as
NRS99Direct 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 inconcepts.yaml -
['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/9605034doiGrover search when the number of marked items is unknown, in O(sqrt(N/m)) queries.used in
functions/04-partial-and-relations.yaml -
['Brassard, G.', 'Hoyer, P.', 'Tapp, A.']. Quantum cryptanalysis of hash and claw-free functions.LATIN 1998, 1998. arXiv:quant-ph/9705002The O(n^{1/3}) collision-finding algorithm.used in
functions/04-partial-and-relations.yaml -
['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.yamlfunctions/01-basic.yamlmeasures/02-randomized.yamlrelations/04-composition.yaml -
['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/9812057The log n / (2 log log n) lower bound.used in
functions/05-more.yaml -
['van Dam', 'W.']. Quantum oracle interrogation: getting all information for almost half the price.Proc. 39th FOCS, pages 362-367, 1998. arXiv:quant-ph/9805006Q(f) <= n/2 + O(sqrt n) for every f on n bits -- the universal quantum upper bound.used in
relations/02-degree.yaml -
['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.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlrelations/07-parameters.yaml -
['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/9701001Q(OR) = Omega(sqrt(n)).used in
functions/01-basic.yamlfunctions/02-composed.yamlfunctions/04-partial-and-relations.yaml -
['Bernstein', 'E.', 'Vazirani', 'U.']. Quantum complexity theory.SIAM Journal on Computing 26(5):1411-1473, 1997.used in
functions/04-partial-and-relations.yamlfunctions/05-more.yaml -
['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 -
['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.yamlmeasures/04-degree.yaml -
['Dürr, C.', 'Høyer, P.']. A quantum algorithm for finding the minimum.1996. arXiv:quant-ph/9607014O(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 -
['Grover', 'L. K.']. A fast quantum mechanical algorithm for database search.STOC 1996, 1996. arXiv:quant-ph/9605043used in
functions/01-basic.yamlfunctions/04-partial-and-relations.yaml -
['Impagliazzo', 'R.']. Hard-core distributions for somewhat hard problems.FOCS 1995, 1995.not currently cited by any entry
-
['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. doiFoundational 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.yamlfunctions/05-more.yamlrelations/10-new-measures.yaml -
['Nisan', 'N.', 'Wigderson', 'A.']. On rank vs. communication complexity.Combinatorica 15:557-565, 1995. doialso cited here as
NW95Iterating 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 infunctions/02-composed.yamlrelations/02-degree.yamltables/total-exponents.yaml -
['Rubinstein', 'D.']. Sensitivity vs. block sensitivity of Boolean functions.Combinatorica 15:297-299, 1995. doialso cited here as
Rub95First quadratic separation bs(f) = s(f)^2/2.used inconcepts.yamlfunctions/02-composed.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/08-fractional.yaml -
['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.yamlmeasures/02-randomized.yamlopen_problems.yaml -
['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 -
['Feige', 'U.', 'Raghavan', 'P.', 'Peleg', 'D.', 'Upfal', 'E.']. Computing with Noisy Information.SIAM Journal on Computing 23(5):1001-1018, 1994. doiIntroduces 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.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlfunctions/06-classical-total.yamlmeasures/02-randomized.yamlmeasures/03-quantum.yamlopen_problems.yamlrelations/04-composition.yamlrelations/07-parameters.yaml -
['Nisan', 'N.', 'Smolensky', 'R.']. Unpublished; proof reproduced in [BdW02].1994.also cited here as
NisanSmolensky94,NS94smolenskyD(f) <= deg(f)^2 bs(f) <= 2 deg(f)^4.used inopen_problems.yamlrelations/02-degree.yaml -
['Nisan', 'N.', 'Szegedy', 'M.']. On the degree of Boolean functions as real polynomials.Computational Complexity 4:301-313, 1994. doibs <= 2 deg^2 and bs <= 6 deg-tilde^2; D = O(deg^8); the sqrt(n) approximating polynomial for OR.used in
concepts.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/03-separating-total.yamlfunctions/04-partial-and-relations.yamlmeasures/01-deterministic.yamlmeasures/04-degree.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/02-degree.yamlrelations/09-chain.yamlrelations/10-new-measures.yamltables/total-exponents.yaml -
['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 -
['Llewellyn, D. C.', 'Tovey, C.']. Dividing and conquering the square.Discrete Applied Mathematics 43(2):131-153, 1993. doiused in
functions/05-more.yaml -
['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 -
['Paturi', 'R.']. On the degree of polynomials that approximate symmetric Boolean functions.STOC 1992, 1992. doiTight characterisation of deg-tilde for symmetric functions.used in
functions/01-basic.yamlfunctions/02-composed.yamlfunctions/04-partial-and-relations.yamlmeasures/04-degree.yamlrelations/10-new-measures.yaml -
['Nisan', 'N.']. CREW PRAMs and Decision Trees.SIAM Journal on Computing 20(6):999-1007, 1991. doiIntroduces block sensitivity; proves C <= s*bs, bs <= 3R, D <= 27 R^3, and C = s = bs for monotone f.used in
concepts.yamlfunctions/01-basic.yamlfunctions/03-separating-total.yamlfunctions/07-recent-separations.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/01-classical-core.yamlrelations/03-quantum.yamlrelations/04-composition.yamlrelations/08-fractional.yamlrelations/09-chain.yamlrelations/10-new-measures.yamlrelations/11-lp-and-lower-bound-methods.yamlrelations/14-sabotage-and-2026-results.yamltables/total-exponents.yaml -
['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.yamlmeasures/02-randomized.yamlrelations/04-composition.yaml -
['Ehrenfeucht', 'A.', 'Haussler', 'D.']. Learning decision trees from random examples.Information and Computation 82(3):231-246, 1989. doiIntroduces 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.yamlfunctions/05-more.yamlmeasures/01-deterministic.yamlrelations/10-new-measures.yaml -
['Llewellyn, D. C.', 'Tovey, C.', 'Trick, M.']. Local optimization on graphs.Discrete Applied Mathematics 23(2):157-178, 1989. doiCharacterises deterministic local-search complexity by vertex cuts; erratum in DAM 46:93-94 (1993).used in
functions/05-more.yaml -
['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. doiD(f) <= C0(f) * C1(f). Independently by Blum-Impagliazzo and Hartmanis-Hemachandra.used in
functions/02-composed.yamlmeasures/01-deterministic.yamlrelations/01-classical-core.yaml -
['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
-
['Kahn', 'J.', 'Kalai', 'G.', 'Linial', 'N.']. The influence of variables on Boolean functions.FOCS 1988, 1988.used in
concepts.yamlfunctions/01-basic.yamlmeasures/05-fourier.yamlrelations/12-normalized.yaml -
['Blum', 'M.', 'Impagliazzo', 'R.']. Generic oracles and oracle classes.FOCS 1987, 1987.Independent proof of D <= C0*C1.used in
functions/02-composed.yamlrelations/01-classical-core.yaml -
['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,HartmanisHemachandra91Independent proof of D <= C0*C1.used infunctions/02-composed.yamlrelations/01-classical-core.yaml -
['Urquhart, A.']. Hard examples for resolution.Journal of the ACM 34(1):209-219, 1987. doiThe 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 -
['Saks', 'M.', 'Wigderson', 'A.']. Probabilistic Boolean decision trees and the complexity of evaluating game trees.FOCS 1986, 1986. doiR0(NAND-tree) = Theta(n^{0.7537...}); the alpha = log_2((1+sqrt(33))/4) exponent.used in
functions/02-composed.yamlfunctions/06-classical-total.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/07-parameters.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Ben-Or', 'M.', 'Linial', 'N.']. Collective coin flipping, robust voting schemes and minima of Banzhaf values.FOCS 1985, 1985.used in
functions/01-basic.yamlmeasures/05-fourier.yaml -
['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.yamlfunctions/06-classical-total.yaml -
['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
-
['Kahn, J.', 'Saks, M.', 'Sturtevant, D.']. A topological approach to evasiveness.Combinatorica 4(4):297-306, 1984. doiNontrivial monotone graph properties are evasive when the number of vertices is a prime power.used in
functions/06-classical-total.yaml -
['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 -
['Aldous, D.']. Minimization algorithms and random walk on the d-cube.Annals of Probability 11(2):403-413, 1983. doiThe 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 -
['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 -
['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.yamlfunctions/01-basic.yamlfunctions/02-composed.yamlfunctions/06-classical-total.yamlmeasures/01-deterministic.yamlmeasures/02-randomized.yamlopen_problems.yamlrelations/07-parameters.yamlrelations/11-lp-and-lower-bound-methods.yaml -
['Bollobas, B.']. Complete subgraphs are elusive.Journal of Combinatorial Theory Series B 21:1-7, 1976. doiContaining a K_k is evasive for every m; hence D(triangle) = C(m,2) exactly.used in
functions/05-more.yamlfunctions/06-classical-total.yaml -
['Rivest, R. L.', 'Vuillemin, J.']. On recognizing graph properties from adjacency matrices.Theoretical Computer Science 3(3):371-384, 1976. doiEvery 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 -
['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 -
['Hellman', 'M. E.', 'Raviv', 'J.']. Probability of error, equivocation, and the Chernoff bound.IEEE Transactions on Information Theory 16(4):368-372, 1970. doiError 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.yamlmeasures/02-randomized.yaml -
['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.yamlfunctions/02-composed.yamlfunctions/04-partial-and-relations.yamlfunctions/06-classical-total.yamlmeasures/04-degree.yamlrelations/10-new-measures.yaml -
['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