Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Yi Wu:

TR10-185 | 2nd December 2010
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

Agnostic Learning of Monomials by Halfspaces is Hard

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\epsilon)$ of the examples, it is $\mathrm{NP}$-hard to find a halfspace that is correct on $(1/2+\epsilon)$ of the examples, for arbitrary constants $\epsilon ... more >>>

TR10-177 | 16th November 2010
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

Bypassing UGC from some optimal geometric inapproximability results

Revisions: 1

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this ... more >>>

ISSN 1433-8092 | Imprint