### DIMACS Theoretical Computer Science Seminar

Title: Transitive reductions, Horn formula optimizations and Parallel repetition
theorem

Speaker: **Bhaskar DasGupta**, University of Illinois at Chicago (UIC).

Date: Wednesday, December 3, 2008 11:00-12:00pm

Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

In this talk, I will discuss our ongoing investigations of approximability
issues of a few somewhat-related optimization problems.

We first consider the Minimum Equivalent Digraph problem (also known as the
Strong Transitive Reduction problem) and its maximum objective function
variant, with two types of extensions. For both problems we establish the
following:

* a polynomial time algorithm for the minimization version within ratio 1.5

* an algorithm for the maximization version within ratio 2, and

* MAX-SNP hardness for both versions, even if the length of simple cycles

is limited to 5.

Very roughly speaking, the Horn formula optimization problem asks, for a
given Horn formula, if there is another equivalent Horn formula optimizing
certain objective criteria. We will discuss approximability of a special
case of this problem via transitive reductions, and inapproximability for a
slightly more general case using Raz's parallel repetition theorem.

(Ongoing work with Piotr Berman, Marek Karpinspki, Gyorgy Turan and
others. None of the results have been published yet.)