On the public citation graph
On the degree of boolean functions as real polynomials
0 signed · 370 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/3-540-18170-9_185openalex-snapshot
The complexity of symmetric boolean functions
inferredcites →https://doi.org/10.1007/bf01111276openalex-snapshot
Schwankung von Polynomen zwischen Gitterpunkten
inferredcites →https://doi.org/10.1007/bf01137685openalex-snapshot
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
inferredcites →https://doi.org/10.1109/sfcs.1988.21923openalex-snapshot
The influence of variables on Boolean functions
inferredcites →https://doi.org/10.1109/sfcs.1989.63537openalex-snapshot
Constant depth circuits, Fourier transform, and learnability
inferredcites →https://doi.org/10.1137/0221003openalex-snapshot
Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
inferredcites →https://doi.org/10.1137/0703024openalex-snapshot
A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
inferredcites →https://doi.org/10.1145/103418.103461openalex-snapshot
The expressive power of voting polynomials
inferredcites →https://doi.org/10.1145/103418.103466openalex-snapshot
Learning decision trees using the Fourier spectrum
inferredcites →https://doi.org/10.1145/28395.28404openalex-snapshot
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
inferredcites →https://doi.org/10.1145/322217.322225openalex-snapshot
Fast Probabilistic Algorithms for Verification of Polynomial Identities
inferredcites →https://doi.org/10.1145/97444.97678openalex-snapshot
Exact time bounds for computing boolean functions on PRAMs without simultaneous writes
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/jgt.22640openalex-snapshot
On induced subgraphs of the Hamming graph
inferred← citeshttps://doi.org/10.1002/rsa.20515openalex-snapshot
A stability result for balanced dictatorships in Sn
inferred← citeshttps://doi.org/10.1006/jcss.1999.1651openalex-snapshot
Complexity Limitations on Quantum Computation
inferred← citeshttps://doi.org/10.1007/1-4020-8141-3_10openalex-snapshot
Degree Bounds on Polynomials and Relativization Theory
inferred← citeshttps://doi.org/10.1007/11523468_104openalex-snapshot
A Quantum Lower Bound for the Query Complexity of Simon’s Problem
inferred← citeshttps://doi.org/10.1007/11750321_32openalex-snapshot
Block Sensitivity of Weakly Symmetric Functions
inferred← citeshttps://doi.org/10.1007/3-540-45294-x_26openalex-snapshot
On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems
inferred← citeshttps://doi.org/10.1007/3-540-46541-3_11openalex-snapshot
Average-Case Quantum Query Complexity
inferred← citeshttps://doi.org/10.1007/3-540-48523-6_26openalex-snapshot
Space-Time Tradeoffs for Graph Properties
inferred← citeshttps://doi.org/10.1007/3-540-48686-0_29openalex-snapshot
On the Average Sensitivity of Testing Square-Free Numbers
inferred← citeshttps://doi.org/10.1007/3-540-49116-3_4openalex-snapshot
Circuit Complexity of Testing Square-Free Numbers
inferred← citeshttps://doi.org/10.1007/3-540-62034-6_33openalex-snapshot
Circuit complexity before the dawn of the new millennium
inferred← citeshttps://doi.org/10.1007/978-1-4471-0313-4_20openalex-snapshot
Quantum Computation Relative to Oracles
inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_11openalex-snapshot
Polynomials and Combinatorial Definitions of Languages
inferred← citeshttps://doi.org/10.1007/978-3-030-26176-4_12openalex-snapshot
Sensitivity, Affine Transforms and Quantum Communication Complexity
inferred← citeshttps://doi.org/10.1007/978-3-030-60622-0_9openalex-snapshot
On the Multiplicity of the Zeros of Polynomials with Constrained Coefficients
inferred← citeshttps://doi.org/10.1007/978-3-030-61792-9_26openalex-snapshot
Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions
inferred← citeshttps://doi.org/10.1007/978-3-030-79416-3_25openalex-snapshot
On Separation Between the Degree of a Boolean Function and the Block Sensitivity
inferred← citeshttps://doi.org/10.1007/978-3-031-52213-0_5openalex-snapshot
On Query Complexity Measures and Their Relations for Symmetric Functions
inferred← citeshttps://doi.org/10.1007/978-3-319-17142-5_10openalex-snapshot
On the Power of Parity Queries in Boolean Decision Trees
inferred← citeshttps://doi.org/10.1007/978-3-319-17142-5_12openalex-snapshot
Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma
inferred← citeshttps://doi.org/10.1007/978-3-319-62389-4_22openalex-snapshot
A Tighter Relation Between Sensitivity Complexity and Certificate Complexity
inferred← citeshttps://doi.org/10.1007/978-3-319-62389-4_32openalex-snapshot
On the Modulo Degree Complexity of Boolean Functions
inferred← citeshttps://doi.org/10.1007/978-3-540-31856-9_49openalex-snapshot
Robust Polynomials and Quantum Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_30openalex-snapshot
Improved Separations between Nondeterministic and Randomized Multiparty Communication
inferred← citeshttps://doi.org/10.1007/978-3-642-02777-2_12openalex-snapshot
Variable Influences in Conjunctive Normal Forms
inferred← citeshttps://doi.org/10.1007/978-3-642-14165-2_41openalex-snapshot
Composition Theorems in Communication Complexity
inferred← citeshttps://doi.org/10.1007/978-3-642-21111-9_32openalex-snapshot
Representing Boolean Functions Using Polynomials: More Can Offer Less
inferred← citeshttps://doi.org/10.1007/978-3-642-22935-0_54openalex-snapshot
Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
inferred← citeshttps://doi.org/10.1007/978-3-642-32241-9_39openalex-snapshot
The Complexity of Unary Subset Sum
inferred← citeshttps://doi.org/10.1007/978-3-642-38233-8_25openalex-snapshot
Query Complexity of Matroids
inferred← citeshttps://doi.org/10.1007/978-3-642-38236-9_21openalex-snapshot
Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive
inferred← citeshttps://doi.org/10.1007/978-3-642-39206-1_26openalex-snapshot
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities
inferred← citeshttps://doi.org/10.1007/978-3-662-43948-7_57openalex-snapshot
The Complexity of Somewhat Approximation Resistant Predicates
inferred← citeshttps://doi.org/10.1007/978-3-662-43948-7_9openalex-snapshot
Tighter Relations between Sensitivity and Other Complexity Measures
inferred← citeshttps://doi.org/10.1007/978-3-662-44465-8_4openalex-snapshot
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
inferred← citeshttps://doi.org/10.1007/978-3-662-44522-8_3openalex-snapshot
Communication Complexity Theory: Thirty-Five Years of Set Disjointness
inferred← citeshttps://doi.org/10.1007/978-3-662-44777-2_49openalex-snapshot
Optimal Parallel Quantum Query Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_22openalex-snapshot
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_78openalex-snapshot
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
inferred← citeshttps://doi.org/10.1007/978-3-662-49890-3_2openalex-snapshot
Indistinguishability Obfuscation from Constant-Degree Graded Encoding Schemes
inferred← citeshttps://doi.org/10.1007/978-3-662-53015-3_21openalex-snapshot
Bounded Indistinguishability and the Complexity of Recovering Secrets
inferred← citeshttps://doi.org/10.1007/978-981-95-8110-8_4openalex-snapshot
Scaling Laws of Deep-Learning Neural Networks: Taxonomy and Survey
inferred← citeshttps://doi.org/10.1007/978-981-96-1090-7_11openalex-snapshot
Relations Between Monotone Complexity Measures Based on Decision Tree Complexity
inferred← citeshttps://doi.org/10.1007/pl00001600openalex-snapshot
The average sensitivity of square-freeness
inferred← citeshttps://doi.org/10.1007/pl00009809openalex-snapshot
Boolean Functions With Low Average Sensitivity Depend On Few Coordinates
inferred← citeshttps://doi.org/10.1007/s00037-003-0176-9openalex-snapshot
Complexity of some arithmetic problems for binary polynomials
inferred← citeshttps://doi.org/10.1007/s00037-006-0212-7openalex-snapshot
THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS
inferred← citeshttps://doi.org/10.1007/s00037-010-0296-yopenalex-snapshot
Lower Bounds for Agnostic Learning via Approximate Rank
inferred← citeshttps://doi.org/10.1007/s00037-012-0045-5openalex-snapshot
Improved Approximation of Linear Threshold Functions
inferred← citeshttps://doi.org/10.1007/s00037-014-0083-2openalex-snapshot
How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?
inferred← citeshttps://doi.org/10.1007/s00037-025-00277-4openalex-snapshot
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
inferred← citeshttps://doi.org/10.1007/s00220-024-04981-0openalex-snapshot
Quantum Talagrand, KKL and Friedgut’s Theorems and the Learnability of Quantum Boolean Functions
inferred← citeshttps://doi.org/10.1007/s00224-002-1068-0openalex-snapshot
Graph Complexity and Slice Functions
inferred← citeshttps://doi.org/10.1007/s00224-006-1313-zopenalex-snapshot
Robust Polynomials and Quantum Algorithms
inferred← citeshttps://doi.org/10.1007/s00453-002-0981-6openalex-snapshot
The Quantum Black-Box Complexity of Majority
inferred← citeshttps://doi.org/10.1007/s00453-007-9022-9openalex-snapshot
A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
inferred← citeshttps://doi.org/10.1007/s00453-013-9826-8openalex-snapshot
On Exact Quantum Query Complexity
inferred← citeshttps://doi.org/10.1007/s00453-016-0206-zopenalex-snapshot
Optimal Parallel Quantum Query Algorithms
inferred← citeshttps://doi.org/10.1007/s00493-011-2580-0openalex-snapshot
The Unbounded-Error Communication Complexity of Symmetric Functions
inferred← citeshttps://doi.org/10.1007/s00493-014-2875-zopenalex-snapshot
On the minimal fourier degree of symmetric Boolean functions
inferred← citeshttps://doi.org/10.1007/s00493-014-3027-1openalex-snapshot
A quasi-stability result for dictatorships in S n
inferred← citeshttps://doi.org/10.1007/s00493-019-4136-7openalex-snapshot
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function
inferred← citeshttps://doi.org/10.1007/s10115-021-01605-0openalex-snapshot
Model complexity of deep learning: a survey
inferred← citeshttps://doi.org/10.1007/s10878-020-00689-8openalex-snapshot
On the relationship between energy complexity and other boolean function measures
inferred← citeshttps://doi.org/10.1007/s11128-020-02975-0openalex-snapshot
From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
inferred← citeshttps://doi.org/10.1007/s11128-025-04714-9openalex-snapshot
Sensitivity of symmetric Boolean functions
inferred← citeshttps://doi.org/10.1007/s11786-018-0350-8openalex-snapshot
Boolean Functions: Degree and Support
inferred← citeshttps://doi.org/10.1007/s11854-015-0025-1openalex-snapshot
Pseudo-boolean functions and the multiplicity of the zeros of polynomials
inferred← citeshttps://doi.org/10.1007/s11856-020-2062-4openalex-snapshot
A structure theorem for almost low-degree functions on the slice
inferred← citeshttps://doi.org/10.1007/s12095-025-00797-4openalex-snapshot
On the number of relevant variables for discrete functions
inferred← citeshttps://doi.org/10.1016/j.dam.2018.05.014openalex-snapshot
A characterization of nested canalyzing functions with maximum average sensitivity
inferred← citeshttps://doi.org/10.1016/j.dam.2025.01.003openalex-snapshot
Interplay between resiliency and polynomial degree — Recursive amplification, higher order sensitivity and beyond
inferred← citeshttps://doi.org/10.1016/j.disc.2019.111614openalex-snapshot
Boolean constant degree functions on the slice are juntas
inferred← citeshttps://doi.org/10.1016/j.disc.2024.114138openalex-snapshot
On degree-3 and (n − 4)-correlation-immune perfect colorings of n-cubes
inferred← citeshttps://doi.org/10.1016/j.disc.2025.114745openalex-snapshot
An upper bound on the number of relevant variables for Boolean functions on the Hamming graph
inferred← citeshttps://doi.org/10.1016/j.ic.2002.12.001openalex-snapshot
Sensitivity, block sensitivity, and ℓ-block sensitivity of boolean functions
inferred← citeshttps://doi.org/10.1016/j.ic.2014.12.003openalex-snapshot
Dual lower bounds for approximate degree and Markov–Bernstein inequalities
inferred← citeshttps://doi.org/10.1016/j.ipl.2007.02.011openalex-snapshot
Bounds on the Fourier coefficients of the weighted sum function
inferred← citeshttps://doi.org/10.1016/j.jairtraman.2017.09.005openalex-snapshot
Multi-criteria weighted decision making for operational maintenance processes
inferred← citeshttps://doi.org/10.1016/j.jcss.2004.02.002openalex-snapshot
A lower bound on the quantum query complexity of read-once functions
inferred← citeshttps://doi.org/10.1016/j.jcss.2005.06.006openalex-snapshot
Polynomial degree vs. quantum query complexity
inferred← citeshttps://doi.org/10.1016/j.jcss.2006.01.002openalex-snapshot
LWPP and WPP are not uniformly gap-definable
inferred← citeshttps://doi.org/10.1016/j.jcss.2007.06.020openalex-snapshot
Quantum certificate complexity
inferred← citeshttps://doi.org/10.1016/j.jcss.2007.06.021openalex-snapshot
Extremal properties of polynomial threshold functions
inferred← citeshttps://doi.org/10.1016/j.jcss.2010.08.011openalex-snapshot
Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
inferred← citeshttps://doi.org/10.1016/j.jcss.2018.04.006openalex-snapshot
AC0∘MOD2 lower bounds for the Boolean Inner Product
inferred← citeshttps://doi.org/10.1016/j.jctb.2022.01.002openalex-snapshot
On sensitivity in bipartite Cayley graphs
inferred← citeshttps://doi.org/10.1016/j.jctb.2022.12.008openalex-snapshot
On the central levels problem
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.02.057openalex-snapshot
The quantum query complexity of the abelian hidden subgroup problem
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.05.020openalex-snapshot
Block sensitivity of weakly symmetric functions
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.02.042openalex-snapshot
An improved lower bound on the sensitivity complexity of graph properties
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.04.043openalex-snapshot
Unbounded-error quantum query complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2014.11.012openalex-snapshot
Any monotone property of 3-uniform hypergraphs is weakly evasive
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.04.049openalex-snapshot
On the modulo degree complexity of Boolean functions
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.08.025openalex-snapshot
A tighter relation between sensitivity complexity and certificate complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.05.048openalex-snapshot
Sensitivity, affine transforms and quantum communication complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2022.12.037openalex-snapshot
Tight bounds on sensitivity and block sensitivity of some classes of transitive functions
inferred← citeshttps://doi.org/10.1016/s0020-0190(00)00069-7openalex-snapshot
Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00144-xopenalex-snapshot
Complexity measures and decision tree complexity: a survey
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00377-2openalex-snapshot
One complexity theorist's view of quantum computing
inferred← citeshttps://doi.org/10.1016/s0304-3975(96)00290-3openalex-snapshot
On the power of circuits with gates of low L1 norms
inferred← citeshttps://doi.org/10.1016/s0890-5401(03)00018-xopenalex-snapshot
An oracle builder’s toolkit
inferred← citeshttps://doi.org/10.1016/s1571-0661(05)80330-5openalex-snapshot
One Complexity Theorist's View of Quantum Computing
inferred← citeshttps://doi.org/10.1017/cbo9780511780448.011openalex-snapshot
Boolean Functions for Cryptography and Error-Correcting Codes
inferred← citeshttps://doi.org/10.1017/cbo9781139814782openalex-snapshot
Analysis of Boolean Functions
inferred← citeshttps://doi.org/10.1070/im2003v067n01abeh000422openalex-snapshot
Quantum communication complexity of symmetric predicates
inferred← citeshttps://doi.org/10.1088/0305-4470/34/35/302openalex-snapshot
Average-case quantum query complexity
inferred← citeshttps://doi.org/10.1103/physreva.77.022326openalex-snapshot
Quantum query complexity for qutrits
inferred← citeshttps://doi.org/10.1103/physreve.107.014126openalex-snapshot
Robustness and stability of spin-glass ground states to perturbed interactions
inferred← citeshttps://doi.org/10.1103/physrevlett.133.220601openalex-snapshot
Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
inferred← citeshttps://doi.org/10.1109/ccc.2000.856758openalex-snapshot
Characterization of non-deterministic quantum query and quantum communication complexity
inferred← citeshttps://doi.org/10.1109/ccc.2001.933879openalex-snapshot
Communication complexity lower bounds by polynomials
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313854openalex-snapshot
Limitations of quantum advice and one-way communication
inferred← citeshttps://doi.org/10.1109/ccc.2004.16openalex-snapshot
Limitations of quantum advice and one-way communication
inferred← citeshttps://doi.org/10.1109/ccc.2005.29openalex-snapshot
The Quantum Adversary Method and Classical Formula Size Lower Bounds
inferred← citeshttps://doi.org/10.1109/ccc.2006.32openalex-snapshot
Oracles Are Subtle But Not Malicious
inferred← citeshttps://doi.org/10.1109/ccc.2009.8openalex-snapshot
Improved Approximation of Linear Threshold Functions
inferred← citeshttps://doi.org/10.1109/ccc.2010.31openalex-snapshot
The Partition Bound for Classical Communication Complexity and Query Complexity
inferred← citeshttps://doi.org/10.1109/ccc.2011.16openalex-snapshot
On the Minimal Fourier Degree of Symmetric Boolean Functions
inferred← citeshttps://doi.org/10.1109/ccc.2013.26openalex-snapshot
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
inferred← citeshttps://doi.org/10.1109/focs.2004.52openalex-snapshot
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
inferred← citeshttps://doi.org/10.1109/focs.2007.28openalex-snapshot
Polylogarithmic Independence Can Fool DNF Formulas
inferred← citeshttps://doi.org/10.1109/focs.2007.55openalex-snapshot
Smooth Histograms for Sliding Windows
inferred← citeshttps://doi.org/10.1109/focs.2008.76openalex-snapshot
Sketching and Streaming Entropy via Approximation Theory
inferred← citeshttps://doi.org/10.1109/focs.2008.91openalex-snapshot
The Polynomial Method in Quantum and Classical Computing
inferred← citeshttps://doi.org/10.1109/focs.2009.12openalex-snapshot
Multiparty Communication Complexity and Threshold Circuit Size of AC^0
inferred← citeshttps://doi.org/10.1109/focs.2009.18openalex-snapshot
The Intersection of Two Halfspaces Has High Threshold Degree
inferred← citeshttps://doi.org/10.1109/focs.2013.32openalex-snapshot
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
inferred← citeshttps://doi.org/10.1109/focs.2015.34openalex-snapshot
The Power of Asymmetry in Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1109/focs.2015.69openalex-snapshot
Lower Bounds for Clique vs. Independent Set
inferred← citeshttps://doi.org/10.1109/focs.2016.38openalex-snapshot
Structure of Protocols for XOR Functions
inferred← citeshttps://doi.org/10.1109/focs.2016.57openalex-snapshot
Polynomial Representations of Threshold Functions and Algorithmic Applications
inferred← citeshttps://doi.org/10.1109/focs.2017.10openalex-snapshot
A Nearly Optimal Lower Bound on the Approximate Degree of AC^0
inferred← citeshttps://doi.org/10.1109/focs.2018.00040openalex-snapshot
Classical Lower Bounds from Quantum Upper Bounds
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00030openalex-snapshot
Towards Optimal Separations between Quantum and Randomized Query Complexities
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00111openalex-snapshot
Separations in Proof Complexity and TFNP
inferred← citeshttps://doi.org/10.1109/isit.2015.7282505openalex-snapshot
Restrictions of nondegenerate Boolean functions and degree lower bounds over different rings
inferred← citeshttps://doi.org/10.1109/isit.2017.8006528openalex-snapshot
Enumeration of Boolean functions of sensitivity three and inheritance of nondegeneracy
inferred← citeshttps://doi.org/10.1109/ismvl.2007.11openalex-snapshot
Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory
inferred← citeshttps://doi.org/10.1109/jsait.2021.3055341openalex-snapshot
Coded Computing for Secure Boolean Computations
inferred← citeshttps://doi.org/10.1109/pst.2017.00040openalex-snapshot
Evidence-Based Trust Mechanism Using Clustering Algorithms for Distributed Storage Systems (Short Paper)
inferred← citeshttps://doi.org/10.1109/sfcs.1995.492670openalex-snapshot
On computing Boolean functions by sparse real polynomials
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743485openalex-snapshot
Quantum lower bounds by polynomials
inferred← citeshttps://doi.org/10.1109/sfcs.2000.892118openalex-snapshot
Randomizing polynomials: A new representation with applications to round-efficient secure computation
inferred← citeshttps://doi.org/10.1109/sfcs.2003.1238197openalex-snapshot
Polynomial degree vs. quantum query complexity
inferred← citeshttps://doi.org/10.1109/sffcs.1999.814607openalex-snapshot
Bounds for small-error and zero-error quantum algorithms
inferred← citeshttps://doi.org/10.1109/tifs.2020.3009609openalex-snapshot
Optimizing Inner Product Masking Scheme by a Coding Theory Approach
inferred← citeshttps://doi.org/10.1134/s1990793125701386openalex-snapshot
The Existence Regions for Transcomplex Recombination of Heavy Ions. Two-Dimensional Recombination Regions and Surroundings Indices
inferred← citeshttps://doi.org/10.1137/05063235xopenalex-snapshot
Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
inferred← citeshttps://doi.org/10.1137/070691954openalex-snapshot
Polylogarithmic Independence Can Fool DNF Formulas
inferred← citeshttps://doi.org/10.1137/1.9781611974331.ch87openalex-snapshot
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
inferred← citeshttps://doi.org/10.1137/100785260openalex-snapshot
The Intersection of Two Halfspaces Has High Threshold Degree
inferred← citeshttps://doi.org/10.1137/100792779openalex-snapshot
Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
inferred← citeshttps://doi.org/10.1137/120891587openalex-snapshot
The Multiparty Communication Complexity of Set Disjointness
inferred← citeshttps://doi.org/10.1137/130939043openalex-snapshot
Superlinear Advantage for Exact Quantum Algorithms
inferred← citeshttps://doi.org/10.1137/15m1015704openalex-snapshot
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1137/16m1064477openalex-snapshot
The Power of Asymmetry in Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1137/17m1136869openalex-snapshot
Structure of Protocols for XOR Functions
inferred← citeshttps://doi.org/10.1137/17m1161737openalex-snapshot
A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
inferred← citeshttps://doi.org/10.1137/18m117563xopenalex-snapshot
Quantum Query Algorithms Are Completely Bounded Forms
inferred← citeshttps://doi.org/10.1137/20m1312459openalex-snapshot
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
inferred← citeshttps://doi.org/10.1137/23m1557593openalex-snapshot
The Approximate Degree of DNF and CNF Formulas
inferred← citeshttps://doi.org/10.1137/s0097539700379644openalex-snapshot
Algorithms for Boolean Function Query Properties
inferred← citeshttps://doi.org/10.1137/s0097539701385296openalex-snapshot
A Theorem on Sensitivity and Applications in Private Computation
inferred← citeshttps://doi.org/10.1137/s0097539702407345openalex-snapshot
Nondeterministic Quantum Query and Communication Complexities
inferred← citeshttps://doi.org/10.1137/s0097539791224285openalex-snapshot
Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines
inferred← citeshttps://doi.org/10.1142/9789813272880_0181openalex-snapshot
UNDERSTANDING QUANTUM ALGORITHMS VIA QUERY COMPLEXITY
inferred← citeshttps://doi.org/10.1142/s0129054118500120openalex-snapshot
The Iota-Delta Function as an Alternative to Boolean Formalism
inferred← citeshttps://doi.org/10.1142/s0219749913500597openalex-snapshot
Explicit relation between all lower bound techniques for quantum query complexity
inferred← citeshttps://doi.org/10.1142/s2010324721400014openalex-snapshot
Exact Quantum 1-Query Algorithms and Complexity
inferred← citeshttps://doi.org/10.1145/1007352.1007378openalex-snapshot
Multilinear formulas and skepticism of quantum computing
inferred← citeshttps://doi.org/10.1145/1132516.1132604openalex-snapshot
A new quantum lower bound method,
inferred← citeshttps://doi.org/10.1145/1595391.1595392openalex-snapshot
Improved Separations between Nondeterministic and Randomized Multiparty Communication
inferred← citeshttps://doi.org/10.1145/1806689.1806702openalex-snapshot
A strong direct product theorem for disjointness
inferred← citeshttps://doi.org/10.1145/1806689.1806703openalex-snapshot
Hardness amplification in proof complexity
inferred← citeshttps://doi.org/10.1145/1855118.1855133openalex-snapshot
The story of set disjointness
inferred← citeshttps://doi.org/10.1145/1855118.1886592openalex-snapshot
SIGACT News Complexity Theory Column 67
inferred← citeshttps://doi.org/10.1145/2213977.2214026openalex-snapshot
The multiparty communication complexity of set disjointness
inferred← citeshttps://doi.org/10.1145/2213977.2214044openalex-snapshot
Making polynomials robust to noise
inferred← citeshttps://doi.org/10.1145/2422436.2422454openalex-snapshot
Evasiveness through a circuit lens
inferred← citeshttps://doi.org/10.1145/2422436.2422485openalex-snapshot
Properties and applications of boolean function composition
inferred← citeshttps://doi.org/10.1145/2488608.2488721openalex-snapshot
Superlinear advantage for exact quantum algorithms
inferred← citeshttps://doi.org/10.1145/2488608.2488725openalex-snapshot
Communication lower bounds using directional derivatives
inferred← citeshttps://doi.org/10.1145/2527748.2527763openalex-snapshot
Gems in decision tree complexity revisited
inferred← citeshttps://doi.org/10.1145/2591796.2591871openalex-snapshot
Breaking the minsky-papert barrier for constant-depth circuits
inferred← citeshttps://doi.org/10.1145/2629334openalex-snapshot
Communication Lower Bounds Using Directional Derivatives
inferred← citeshttps://doi.org/10.1145/2688073.2688096openalex-snapshot
A New Approach to the Sensitivity Conjecture
showing the first 200 of 357 · page through all 357
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.