-----------
Tel-Aviv University - Computer Science Colloquium

Sunday, January 16, 14:15-15:15
COFFEE at 14:00

Schreiber Building, Room 309
-----------

Approximability of Circuit Minimization Problems

Chris Umans

UC Berkeley

Abstract:

A important hard optimization problem in logic synthesis is finding the
smallest circuit representing a given function. This problem and its
variants have been studied since the 1950s, and many heuristics have
been proposed. Circuit minimization problems are believed to be
$\Sigma_2^p$-complete; however, proofs of completeness are not known
for most variants.

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