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.

pdf slides poster
hardness-of-approximation probabilistically-checkable-proofs complexity-theory
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)

paper slides
hardness-of-approximation probabilistically-checkable-proofs complexity-theory
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)

arXiv pdf slides
hardness-of-approximation complexity-theory
Thumbnail [200x250]
May, 2015

Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions

Girish Varma
Chicago J. Theor. Comp. Sci.

arXiv
hardness-of-approximation complexity-theory
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)

arXiv slides
hardness-of-approximation graph-theory complexity-theory
Thumbnail [200x250]