Projects

Hardness of Approximate Coloring

Improved lowerbounds for graph/hypergraph coloring.

Model Compression

Make deep learning models deployable in constrained memory devices.

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.

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.

CONTINUE READING

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.

CONTINUE READING

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.

CONTINUE READING

Contact