Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with gap-ETH:
TR17-063 | 10th April 2017
Benny Applebaum

Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions

The gap-ETH assumption (Dinur 2016; Manurangsi and Raghavendra 2016) asserts that it is exponentially-hard to distinguish between a satisfiable 3-CNF formula and a 3-CNF formula which is at most 0.99-satisfiable. We show that this assumption follows from the exponential hardness of finding a satisfying assignment for *smooth* 3-CNFs. Here smoothness ... more >>>

TR18-057 | 26th March 2018
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$. Here, $k$ ... more >>>

ISSN 1433-8092 | Imprint