Approximate inclusion-exclusion for arbitrary symmetric functions

DOI10.1007/s00037-009-0274-4zbMath1217.68107OpenAlexW2173499948MaRDI QIDQ626621

Alexander A. Sherstov

Publication date: 18 February 2011

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

Full work available at URL: https://doi.org/10.1007/s00037-009-0274-4

zbMATH Keywords

approximation by polynomialsapproximate degree of Boolean functionapproximate inclusion-exclusion

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Symmetric functions and generalizations (05E05) Approximation by polynomials (41A10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Algorithmic Polynomials ⋮ The hardest halfspace ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities

This page was built for publication: Approximate inclusion-exclusion for arbitrary symmetric functions