Senior Project Scientist

Center for Visual Information Technology

International Institute of Information Technology Hyderabad

Gachibowli, Hyderabad

Email: [firstname.lastname] at iiit.ac.in

Puzzling Computers
A gentle introduction to the theory of NP-Completeness.

Approximation and its Limits
An introduction to probabilistically checkable proofs and hardness of approximation.

Hardness of Coloring
On the impossibility of finding efficient algorithms for coloring problems.

Hardness of Graph Coloring

Hardness of Hypergraph Coloring

A Characterization of Hard-to-cover CSPs

- 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)$.

Theory

Playing Games in an Uncertain World

GV14: arXiv

that Compute

Physarum Can Compute Shortest Paths

Algorithms

Streaming Algorithms for Language Recognition Problems