Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DICTATORSHIP TESING:
Reports tagged with Dictatorship tesing:
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 >>>

TR17-030 | 15th February 2017
Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

#### An Improved Dictatorship Test with Perfect Completeness

A Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is called a dictator if it depends on exactly one variable i.e $f(x_1, x_2, \ldots, x_n) = x_i$ for some $i\in [n]$. In this work, we study a $k$-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems.

... more >>>

ISSN 1433-8092 | Imprint