Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DICTATORSHIP TESTS:
Reports tagged with Dictatorship Tests:
TR10-185 | 2nd December 2010
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

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 >>> TR17-141 | 19th September 2017 Joshua Brakensiek, Venkatesan Guruswami #### A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover We give a family of dictatorship tests with perfect completeness and low-soundness for 2-to-2 constraints. The associated 2-to-2 conjecture has been the basis of some previous inapproximability results with perfect completeness. However, evidence towards the conjecture in the form of integrality gaps even against weak semidefinite programs has been elusive. ... more >>> TR18-037 | 21st February 2018 Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani #### Inapproximability of Matrix$p \rightarrow q$Norms We study the problem of computing the$p\rightarrow q$norm of a matrix$A \in R^{m \times n}$, defined as $\|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p}$ This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$,$q=1\$), and has been ... more >>>

ISSN 1433-8092 | Imprint