All reports by Author Girish Varma:

__
TR15-069
| 21st April 2015
__

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat#### On Fortification of General Games

Revisions: 1

__
TR13-167
| 28th November 2013
__

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma#### Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

__
TR10-094
| 17th May 2010
__

Ajesh Babu, Nutan Limaye, Girish Varma#### Streaming algorithms for some problems in log-space.

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

A recent result of Moshkovitz~\cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel ... more >>>

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the “short code” of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results.

In particular, we prove quasi-NP-hardness of the following problems on ... more >>>

Ajesh Babu, Nutan Limaye, Girish Varma

In this paper, we give streaming algorithms for some problems which are known to be in deterministic log-space, when the number of passes made on the input is unbounded. If the input data is massive,

the conventional deterministic log-space algorithms may not run efficiently. We study the complexity of the ...
more >>>