hardness-of-approximation

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