Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMATION BY POLYNOMIALS:
Reports tagged with Approximation by polynomials:
TR07-116 | 25th September 2007
Alexander A. Sherstov

Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

Comments: 1

Let A_1,...,A_n be events in a probability space. The
approximate inclusion-exclusion problem, due to Linial and
Nisan (1990), is to estimate Pr[A_1 OR ... OR A_n] given
Pr[AND_{i\in S}A_i] for all |S|<=k. Kahn et al. (1996) solve
this problem optimally for each k. We study the following more
general question: ... more >>>


TR25-101 | 18th July 2025
Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis

A seminal result of Nisan and Szegedy (STOC, 1992) shows that for any total Boolean function, the degree of the real polynomial that computes the function, and the minimal degree of a real polynomial that point-wise approximates the function, are at most polynomially separated. Extending this result from degree to ... more >>>




ISSN 1433-8092 | Imprint