complexity-theory

Publications

Jan, 2016

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.

Thumbnail [200x250]
Dec, 2015

A Characterization of Hard-to-cover CSPs

Amey Bhangale, Prahladh Harsha, Girish Varma
Theory of Computing Journal (ToC)
Computational Complexity Conference (CCC)

Thumbnail [200x250]
Sep, 2015

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)

Thumbnail [200x250]
Aug, 2015

On Fortification of Projection Games

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat
Randomization and Computation (RANDOM'15)

Feb, 2015

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)

Thumbnail [200x250]