Sunday, January 16, 14:15-15:15
at 14:00
Schreiber Building, Room 309
For the DNF variant, a completeness proof was recently given, so
the
next step is to investigate the approximability of this problem.
I
will present a proof that DNF minimization is $\Sigma_2^p$-hard
to
approximate to within $n^{\epsilon}$ factors. The main technical
tool
is a novel use of explicit dispersers to achieve strong, direct
inapproximability results for this problem and a number of other
$\Sigma_2^p$ optimization problems.
Time permitting, I will also describe some recent work on approximation
algorithms for some of these $\Sigma_2^p$ minimization problems.
For colloquium schedule, see http://www.math.tau.ac.il/~zwick/colloq.html