## 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

#### 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**)