On the degree of Boolean functions as real polynomials

DOI10.1007/BF01263419zbMath0829.68047MaRDI QIDQ1346612

Mario Szegedy, Noam Nisan

Publication date: 6 April 1995

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

Boolean functionblock sensitivityFourier degree

Mathematics Subject Classification ID

Related Items (89)

Log-Sobolev inequality for the multislice, with applications ⋮ Boolean functions: degree and support ⋮ A lower bound on the quantum query complexity of read-once functions ⋮ A characterization of nested canalyzing functions with maximum average sensitivity ⋮ A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables ⋮ Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions ⋮ Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ Amplification of One-Way Information Complexity via Codes and Noise Sensitivity ⋮ The quantum query complexity of the abelian hidden subgroup problem ⋮ Low-Sensitivity Functions from Unambiguous Certificates. ⋮ An orthogonal basis for functions over a slice of the Boolean hypercube ⋮ Bounds on the Fourier coefficients of the weighted sum function ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Block sensitivity of weakly symmetric functions ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Improved approximation of linear threshold functions ⋮ \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product ⋮ Optimal parallel quantum query algorithms ⋮ On sensitivity in bipartite Cayley graphs ⋮ All Classical Adversary Methods are Equivalent for Total Functions ⋮ On the power of circuits with gates of low \(L_{1}\) norms. ⋮ Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma ⋮ On the minimal Fourier degree of symmetric Boolean functions ⋮ Pseudo-Boolean functions and the multiplicity of the zeros of polynomials ⋮ On induced subgraphs of the Hamming graph ⋮ Induced subgraphs of product graphs and a generalization of Huang's theorem ⋮ Unnamed Item ⋮ An oracle builder's toolkit ⋮ Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions ⋮ From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm ⋮ Degree 2 Boolean functions on Grassmann graphs ⋮ Unnamed Item ⋮ Triangle-intersecting families of graphs ⋮ Boolean functions on $S_n$ which are nearly linear ⋮ On the central levels problem ⋮ Structure of Protocols for XOR Functions ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Unbounded-error quantum query complexity ⋮ Topology of real multi-affine hypersurfaces and a homological stability property ⋮ Junta threshold for low degree Boolean functions on the slice ⋮ On the resolution of the sensitivity conjecture ⋮ Unnamed Item ⋮ Complexity limitations on quantum computation ⋮ Unnamed Item ⋮ A structure theorem for almost low-degree functions on the slice ⋮ Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions ⋮ Algorithmic Polynomials ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Approximate Degree, Secret Sharing, and Concentration Phenomena ⋮ How low can approximate degree and quantum query complexity be for total Boolean functions? ⋮ The Iota-Delta Function as an Alternative to Boolean Formalism ⋮ On the Multiplicity of the Zeros of Polynomials with Constrained Coefficients ⋮ The equivalence of two problems on the cube ⋮ A quasi-stability result for dictatorships in \(S_n\) ⋮ Extremal properties of polynomial threshold functions ⋮ An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function ⋮ An improved lower bound on the sensitivity complexity of graph properties ⋮ Polynomial degree vs. quantum query complexity ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A tighter relation between sensitivity complexity and certificate complexity ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ On the modulo degree complexity of Boolean functions ⋮ Superlinear Advantage for Exact Quantum Algorithms ⋮ On the relationship between energy complexity and other Boolean function measures ⋮ Sensitivity, affine transforms and quantum communication complexity ⋮ Tight bounds on sensitivity and block sensitivity of some classes of transitive functions ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Variable Influences in Conjunctive Normal Forms ⋮ Unnamed Item ⋮ New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Unnamed Item ⋮ Counterexamples to “A conjecture on induced subgraphs of Cayley graphs” ⋮ Boolean constant degree functions on the slice are juntas ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Induced subgraphs of hypercubes and a proof of the sensitivity conjecture ⋮ A stability result for balanced dictatorships in S_n ⋮ Complexity measures and decision tree complexity: a survey. ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities ⋮ A Lifting Theorem with Applications to Symmetric Functions ⋮ On exact quantum query complexity ⋮ Agnostically Learning Boolean Functions with Finite Polynomial Representation ⋮ On separation between the degree of a Boolean function and the block sensitivity ⋮ One complexity theorist's view of quantum computing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Polynomials with two values
• Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
• Constant depth circuits, Fourier transform, and learnability
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof

This page was built for publication: On the degree of Boolean functions as real polynomials