Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GADGETS:
Reports tagged with gadgets:
TR99-043 | 5th November 1999
Venkatesan Guruswami

The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses


We prove hardness results for approximating set splitting problems and
also instances of satisfiability problems which have no ``mixed'' clauses,
i.e all clauses have either all their literals unnegated or all of them
negated. Recent results of Hastad imply tight hardness results for set
splitting when all sets ... more >>>




ISSN 1433-8092 | Imprint