Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-053 | 17th July 2001 00:00

Efficient Amplifiers and Bounded Degree Optimization



This paper studies the existence of efficient (small size)
amplifiers for proving explicit inaproximability results for bounded degree
and bounded occurrence combinatorial optimization problems, and gives
an explicit construction for such amplifiers. We use this construction
also later to improve the currently best known approximation lower bounds
for bounded occurrence instances of linear equations mod 2, and
for bounded degree (regular) instances of MAX-CUT.
In particular we prove the approximation lower bound of 152/152 for
exactly 3-occurrence E3-OCC-E2-LIN-2 problem, and MAX-CUT problem on
3-regular graphs, E3-MAX-CUT, and the approximation lower bound
of 121/120 for E3-OCC-2-LIN-2 problem. As an application we are
able to improve also the best known approximation lower bound for

ISSN 1433-8092 | Imprint