On Improved Degree Lower Bounds for Polynomial Approximation.
From MaRDI portal
Number-theoretic algorithms; complexity (11Y16) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Recommendations
- Polynomial approximation in \(L_ p (O<p<1)\)
- Improvements of Lagrange's bound for polynomial roots
- Another look at degree lower bounds for polynomial calculus
- A new polynomial bound and its efficiency
- scientific article; zbMATH DE number 4067511
- scientific article; zbMATH DE number 2068058
- Lower bounds for polynomial evaluation and interpolation problems
- scientific article; zbMATH DE number 5592923
- scientific article; zbMATH DE number 5286928
- scientific article; zbMATH DE number 3944469
Cited in
(18)- A \#SAT algorithm for small constant-depth circuits with PTF gates
- Continuous and discrete best polynomial degree reduction with Jacobi and Hahn weights
- Degree lower bounds of tower-type for approximating formulas with parity quantifiers
- An explicit VC-theorem for low-degree polynomials
- Approximating Boolean functions with depth-2 circuits
- Small Sample Spaces Cannot Fool Low Degree Polynomials
- Random Low Degree Polynomials are Hard to Approximate
- Random low-degree polynomials are hard to approximate
- scientific article; zbMATH DE number 2068058 (Why is no real title available?)
- On polynomial approximations to \(\mathrm{AC}^0\)
- Low order polynomial bounds on the expected performance of local improvement algorithms
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- On the probabilistic degree of OR over the reals
- Degree lower bounds of tower-type for approximating formulas with parity quantifiers
- Approximate degree, weight, and indistinguishability
- New degree bounds for polynomial threshold functions
- On the probabilistic degree of OR over the reals
- Fourier conjectures, correlation bounds, and majority
This page was built for publication: On Improved Degree Lower Bounds for Polynomial Approximation.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963913)
