## complexity-theory

### Publications

#### Hardness of Approximate Coloring

Phd Thesis advised by Prof. Prahlad Harsha

Supported by Google India Phd Fellowship in Algorithms

Tata Institute of Fundamental Research, Mumbai.

#### A Characterization of Hard-to-cover CSPs

Amey Bhangale, Prahladh Harsha, Girish Varma

Theory of Computing Journal (**ToC**)

Computational Complexity Conference (**CCC**)

#### Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

Venkat Guruswami, Prahladh Harsha, Johan Hastad, Srikanth Srinivasan, Girish Varma

SIAM Journal on Computing (**SICOMP**)

Sym. of Theory of Computing (**STOC**)

#### On Fortification of Projection Games

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

Randomization and Computation (RANDOM'15)

#### Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions

Girish Varma
*Chicago J. Theor. Comp. Sci*.

#### Derandomized Graph Product Results using the Low Degree Long Code

Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma

Symp. on Theor. Aspects of Comp. Sci. (STACS)