Approximating Boolean functions with depth-2 circuits
by Eric Blais and Li-Yang Tan
Oded's comments
This paper studies the DNF-complexity of approximating general
and specific Boolean functions, where approximation means obtaining
the value of the function of on an arbitrary large constant fraction
of the domain. Interestingly, the picture that arises
is different from the one for exactly computing these functions
(see details in the beginning of the introduction).
Although the DNF-complexity of functions is a rather ``weak'' complexity
measure, it is cedrtainly a natural one, and it is quite odd that
its systematic study was relatively neglected so far.
The abstract
We study the complexity of approximating Boolean functions with DNFs and
other depth-2 circuits, exploring two main directions: universal bounds on
the approximability of all Boolean functions, and the approximability of
the parity function.
In the first direction, our main positive results are the first non-trivial
universal upper bounds on approximability by DNFs:
- Every Boolean function can be approximated by a DNF of size O((2^n)/logn).
- Every Boolean function can be approximated by a DNF of width cn, where c<1.
Our techniques extend broadly to give strong universal upper bounds on
approximability by various depth-2 circuits that generalize DNFs, including
the intersection of halfspaces, low-degree PTFs, and unate functions. We
show that the parameters of our constructions come close to matching the
information-theoretic inapproximability of a random function.
In the second direction our main positive result is the construction of an
explicit DNF that approximates the parity function:
- PARITY can be approximated by a DNF of size $2^{cn}$ and width $cn$,
for $c<1$.
Using Fourier analytic tools we show that our construction is essentially
optimal not just within the class of DNFs, but also within the far more
expressive classes of the intersection of halfspaces and intersection of
unate functions.
See ECCC TR13-051/a>.
Back to
list of Oded's choices.