XNet : Efficient Deep Networks

Use Expander graphs for making Deep Neural Networks Efficient

Deep Reinforcement Learning

Surveying Deep learning methods used in Reinforcement Learning

Model Compression

Make deep learning models deployable in constrained memory devices.

Hardness of Approximate Coloring

Improved lowerbounds for graph/hypergraph coloring.

Physarum Computer

Formal proof for slime-molds finding shortest paths in maze.

Probabilitically Checkable Proofs

Improved PCPs using low-degree codes and using product constructions.

Streaming Algorithms

Few pass, small memory algorithms for big data.

Selected Publications

SICOMP, 2017.

JTB’12, 2012.

Recent & Upcoming Talks

Deep Learning Programming & Deployment
Sep 1, 2017 12:00 AM
Introduction to Machine Learning
Jul 9, 2017 12:00 AM
Model Compression
Jul 15, 2017 12:00 AM

Recent Posts

This is the third part, of a series of blog posts, on the impossibility of finding efficient algorithms for certain problems. In the first, we saw that for sudoku and many other puzzles, there is a single explanation for our inability to find polynomial time algorithms. The explanation is that, any one problem (say sudoku) that is NP-Complete, does not have a polynomial time algorithm. This is commonly known as the P $\neq$ NP assumption.


In the previous blog post, we saw that a computer as we know it, cannot help in solving many puzzles. But some of these puzzles need to be solved, routinely in real life programs. So should we give up hope? Is there another way out? One way out, is to relax the conditions that is required of the solutions. For the sudoku puzzle, we might say that, we are happy with solutions with just the rows and columns having all distinct numbers and not the blocks.


Sudoku Above is an instance of the sudoku puzzle. The goal is to fill in numbers from $1$ to $9$ in the blanks such that, every row, column and $3 \times 3$ block has all the $9$ different numbers. Beside is a solution for the puzzle instance and it is easy to verify that the constraints on the rows, columns and sub blocks are satisfied. Since very few numbers are given, it is difficult to solve.