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)