On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)

No abstract is available for this paper.

• Publication year

  1992

• Venue

  Symposium on the Theory of Computing

• Publication date

  1992-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/129712.129758
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the degree of boolean functions as real polynomials

  1992cited by this paper
• Algebraic methods in the theory of lower bounds for Boolean circuit complexity

  1987cited by this paper
• The Rational Approximation of Real Functions

  1978cited by this paper
• The Chebyshev polynomials

  1974cited by this paper

• Sufficient conditions for hardness of lossy Gaussian boson sampling

  2025cites this paper
• Faster Algorithms for Agnostically Learning Disjunctions and their Implications

  2025cites this paper
• Quantum Computational Advantage of Noisy Boson Sampling with Partially Distinguishable Photons

  2025cites this paper
• Methods for Reducing Ancilla-Overhead in Block Encodings

  2025cites this paper
• Model-agnostic super-resolution in high dimensions

  2025cites this paper
• Approximate Degrees of Multisymmetric Properties with Application to Quantum Claw Detection

  2024cites this paper
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations

  2024cites this paper
• Towards ACC Lower Bounds using Torus Polynomials

  2024cites this paper
• Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching

  2023cites this paper
• Quantum and Classical Communication Complexity of Permutation-Invariant Functions

  2023cites this paper
• On the Composition of Randomized Query Complexity and Approximate Degree

  2023influential citation
• SYMMETRIC FUNCTIONS

  2023cites this paper
• The hardness of quantum spin dynamics

  2023cites this paper
• A Study of Sparse Representation of Boolean Functions

  2023cites this paper
• Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization

  2023cites this paper
• Compressibility-Aware Quantum Algorithms on Strings

  2023influential citation
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more

  2023cites this paper
• OPTIMAL METHOD FOR SOLVING SPECIAL CLASSES OF SYSTEMS OF NONLINEAR EQUATIONS OF THE SECOND DEGREE

  2023cites this paper
• Succinct Quantum Testers for Closeness and k-Wise Uniformity of Probability Distributions

  2023cites this paper
• Complexity-theoretic foundations of BosonSampling with a linear number of modes

  2023cites this paper
• Matching upper bounds on symmetric predicates in quantum communication complexity

  2023cites this paper
• How Balanced Can Permutations Be?

  2023cites this paper
• Discrete Analysis

  2022cites this paper
• Bounds on Oblivious Multiparty Quantum Communication Complexity

  2022cites this paper
• Unitary property testing lower bounds by polynomials

  2022cites this paper
• Approximate Degree, Weight, and Indistinguishability

  2022cites this paper
• Quantum Speed-Ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching

  2022influential citation
• Computational advantage of quantum random sampling

  2022cites this paper
• Bounded Indistinguishability for Simple Sources

  2021cites this paper
• Sharp indistinguishability bounds from non-uniform approximations

  2021cites this paper
• Quantum supremacy and hardness of estimating output probabilities of quantum circuits

  2021influential citation
• Noise and the Frontier of Quantum Supremacy

  2021cites this paper
• SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization

  2021cites this paper
• On Query Complexity Measures and Their Relations for Symmetric Functions

  2021cites this paper
• Improved robustness of quantum supremacy for random circuit sampling

  2021cites this paper
• Lower bounds on quantum query complexity for symmetric functions

  2021cites this paper
• Unconditional Lower Bounds for Adaptive Massively Parallel Computation

  2020cites this paper
• The approximate degree of bipartite perfect matching

  2020cites this paper
• Computational Barriers to Estimation from Low-Degree Polynomials

  2020cites this paper
• Sampling and the complexity of nature (Assessing, testing, and challenging the computational power of quantum devices)

  2020cites this paper
• The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning

  2020influential citation
• The Role of Symmetry in Quantum Query-to-Communication Simulation

  2020cites this paper
• Fermion Sampling: A Robust Quantum Computational Advantage Scheme Using Fermionic Linear Optics and Magic Input States

  2020cites this paper
• 1 Classical and Quantum computation : circuit model 1 . 1 Reversible Computation

  2020cites this paper
• Symmetry and Quantum Query-to-Communication Simulation

  2020cites this paper
• Quantum Communication Complexity of Distribution Testing

  2020cites this paper
• Guest Column

  2020cites this paper
• Lower Bounding the AND-OR Tree via Symmetrization

  2019cites this paper
• Approximate Degree-Weight and Indistinguishability Xuangui Huang

  2019cites this paper
• A study in Rashomon curves and volumes: A new perspective on generalization and model simplicity in machine learning

  2019cites this paper
• Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics.

  2019cites this paper
• On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes

  2019influential citation
• Near-optimal lower bounds on the threshold degree and sign-rank of AC0

  2019cites this paper
• On the Existence of Simpler Machine Learning Models

  2019cites this paper
• The hardest halfspace

  2019cites this paper
• QMA Lower Bounds for Approximate Counting

  2019cites this paper
• $\mathsf{QMA}$ Lower Bounds for Approximate Counting

  2019cites this paper
• Efficient classical simulation of random shallow 2D quantum circuits

  2019cites this paper
• Quantum lower bounds for approximate counting via laurent polynomials

  2019cites this paper
• Cayley path and quantum computational supremacy: A proof of average-case #P-hardness of Random Circuit Sampling with quantified robustness

  2019cites this paper
• On the Probabilistic Degrees of Symmetric Boolean functions

  2019cites this paper
• Sum-Of-Squares Bounds via Boolean Function Analysis

  2019cites this paper
• Approximate degree, secret sharing, and concentration phenomena

  2019cites this paper
• Quantum supremacy and random circuits.

  2019cites this paper
• Approximate degree of AND via Fourier analysis

  2018cites this paper
• Quantum Lower Bound for Approximate Counting Via Laurent Polynomials

  2018cites this paper
• Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling

  2018cites this paper
• 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, Kanpur, India, December 11-15, 2017

  2018cites this paper
• Algorithmic polynomials

  2018cites this paper
• On multiparty communication with large versus unbounded error

  2018cites this paper
• Notes on Fourier Analysis of Boolean Functions

  2018cites this paper
• Classical Lower Bounds from Quantum Upper Bounds

  2018influential citation
• Post-selected Classical Query Complexity

  2018influential citation
• AC0∘MOD2 lower bounds for the Boolean Inner Product

  2018cites this paper
• On the complexity and verification of quantum random circuit sampling

  2018cites this paper
• Contracting projected entangled pair states is average-case hard

  2018cites this paper
• On the Spectral Properties of Symmetric Functions

  2017cites this paper
• Small-Bias is Not Enough to Hit Read-Once CNF

  2017cites this paper
• Quantum Query Complexity of Entropy Estimation

  2017cites this paper
• Dual polynomials and communication complexity of $\textsf{XOR}$ functions

  2017influential citation
• COUNT AND CRYPTOGRAPHIC PROPERTIES OF GENERALIZED SYMMETRIC BOOLEAN FUNCTIONS

  2017cites this paper
• Dual polynomials and communication complexity of XOR functions

  2017cites this paper
• Learning Neural Networks with Two Nonlinear Layers in Polynomial Time

  2017cites this paper
• A Lifting Theorem with Applications to Symmetric Functions

  2017cites this paper
• A Nearly Optimal Lower Bound on the Approximate Degree of AC^0

  2017cites this paper
• On the tightness of Tietäväinen's bound for distributions with limited independence

  2017cites this paper
• Communication Complexity

  2016cites this paper
• Polynomial Representations of Threshold Functions and Algorithmic Applications

  2016influential citation
• On the sum-of-squares degree of symmetric quadratic functions

  2016cites this paper
• Bounded Indistinguishability and the Complexity of Recovering Secrets

  2016cites this paper
• On SZK and PP

  2016cites this paper
• Polynomial-Time Algorithms for Checking Some Properties of Boolean Functions Given by Polynomials

  2016cites this paper
• On the Power of Statistical Zero Knowledge

  2016cites this paper
• Dual Polynomials for Collision and Element Distinctness

  2015cites this paper
• Quantum Query Complexity of Subgraph Isomorphism and Homomorphism

  2015cites this paper
• AC 0 ◦ MOD 2 lower bounds for the Boolean Inner Product

  2015cites this paper
• Applications of Adversary Method in Quantum Query Algorithms

  2014cites this paper
• The Information Complexity of Hamming Distance

  2014cites this paper
• Lower Bounds for the Approximate Degree of Block-Composed Functions

  2014cites this paper
• Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness

  2014cites this paper