Girish Varma

Senior Project Scientist
Center for Visual Information Technology
International Institute of Information Technology Hyderabad
Gachibowli, Hyderabad
Email: [firstname.lastname] at


Puzzling Computers A gentle introduction to the theory of NP-Completeness.
Dec, 2014
Approximation and its Limits An introduction to probabilistically checkable proofs and hardness of approximation.
Dec, 2014
Hardness of Coloring On the impossibility of finding efficient algorithms for coloring problems.
Dec, 2014

Limits of Approximation

poster | article | slides | thesis
Hardness of Graph Coloring
October, 2014
Joint work with Irit Dinur, Prahladh Harsha and Srikanth Srinivasan [DHSV14]. We show that assuming a version of UGC, given a (almost) $3$-colorable graph, no efficient algorithm can find a $2^{poly(\log \log n)}$-coloring. This is an improvement over $C=poly(\log \log n)$ hardness result of Dinur and Shinkar, using similar assumtions.
DHSV14: arXiv | STACS'15 | slides
Hardness of Hypergraph Coloring
March, 2014
Joint work with Venkatesh Guruswami, Johan Hastad, Prahladh Harsha, Srikanth Srinivasan [GHHSV14] and [V14]. For the problem of $C$-coloring a $4$-colorable $4$-uniform hypergraph, we show that no efficient algorithm can guarantee $C=2^{(\log n)^{1/19}}$, an improvement over $C=poly(\log n)$. First the result was shown for a super-polylogarithmic $C$. Subsequently Subhash Khot and Rishi Saket proved a result for $C=2^{(\log n)^{1/18}}$, but only for $12$-uniform hypergraphs. I observed that by combining the methods, the same result can be obtained for $4$-colorable $4$-uniform hypergraphs.
GHHSV14: arXiv | STOC'14 | slides V14: arXiv
A Characterization of Hard-to-cover CSPs
November, 2014
Joint work with Amey Bhangale and Prahladh Harsha [BHV14]. The covering number of a CSP instance, is the gv-smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. We show the following results:
- Assuming a covering unique games conjecture, introduced by Dinur and Kol, we show that it is hard to approximate the covering number within any constant factor. Our generalization yields a complete characterization of CSPs over constant sized alphabet $\Sigma$ that are hard to cover since CSPs over odd predicates are trivially coverable with $|\Sigma|$ assignments.
- For a large class of predicates that are contained in the $2k$-LIN predicate, we show that it is quasi-NP-hard to distinguish between instances which have covering number at most two and covering number at least $\Omega(\log\log n)$. This generalizes the $4$-LIN result of Dinur and Kol that states it is quasi-NP-hard to distinguish between $4$-LIN-CSP instances which have covering number at most two and covering number at least $\Omega(\log \log\log n)$.
BHV14: arXiv | CCC'15 slides


Playing Games in an Uncertain World
January, 2014
Joint work with Manoj Gopalkrishnan [GV14]. Traditional game theory assumes that the players in the game are aware of the rules of the game. However, in practice, often the players are unaware or have only partial knowledge about the game they are playing. They may also have knowledge that other players have only partial knowledge of the game they are playing, which they can try to exploit. We present a novel mathematical formulation of such games. We make use of Kripke semantics, which are a way to keep track of what different players know and do not know about the world. We propose a notion of equilibrium for such games, and show that equilibrium always exists.
GV14: arXiv

Biological Systems
that Compute

youtube | popular science | Lipton's Blog
Physarum Can Compute Shortest Paths
March, 2011
Joint work with Vincenzo Bonifaci and Kurt Mehlhorn [BMV12]. Physarum or slime mold is a fungi. Researchers observed that it has fascinating computational capabilities like solving a maze, even without a central coordination mechanism. They modeled the creature grown in a maze with food at end points, as a flow of fluid over a graph of tubes, with time varying diameters. Simulations of this model revealed that the diameters of tubes along the shortest paths converged to 1 and the rest to 0. We prove these convergence results formally for all graphs. We used tools from electrical network and network flow theory to show exponential rate of convergence for a large class of graphs.
BMV12: arXiv | SODA'12 | JTB


Streaming Algorithms for Language Recognition Problems
Joint work with Ajesh Babu, Nutan Limaye and Jaikumar Radhakrishnan [BLRV13]. Streaming algorithms are motivated by situations where the input data is huge and is read in an online fashion. The efficiency of algorithms is measured with respect to the space used. We study streaming algorithms for checking whether an input string(of length $n$) can be parsed in a fixed context free grammar. Even for simple grammars, one can prove that deterministic algorithms cannot do anything better than storing the entire input. Using the technique of fingerprinting, we gave a randomized streaming algorithm that uses only $\log n$ space, for a sub-class of context free grammars. We also showed that for simple grammars outside this class, any randomized algorithm will require $\Omega(n)$ space. Furthermore we gave an $O(\log n)$ space randomized streaming algorithm for checking degree sequence of a graphs (where $n$ is the number of vertices), and prove that it is optimal in its space usage.
BLRV13: arXiv | TAMC'10 | TCS | slides