Algorithms for intractable problems.
Many real-world problems are NP-hard and may not admit efficient (polynomial-time) algorithms.
One approach towards this is parameterized algorithms,
where we identify tractable input instances by a parameter
that measures how easy or difficult the instance is.
Informally, a fixed parameter tractable (FPT) algorithm gives faster
algorithms for smaller values of the parameter, and which run in polynomial-time
when these values are constant.
Another successful approach is approximation algorithms: by spending more time, we aim
to get closer solutions to optimization problems.
Graph theory and social networks
I am interested in structural questions about graph theory, including graph coloring,
asymptotic bounds for graph parameters.
Social networks have led to interesting problems in graph theory, including that of
finding good random graph models, and algorithms for solving problems on such networks.
Determinantal complexity:
The determinantal complexity of a polynomial f(X) is the size of the smallest matrix M whose entires are linear forms in variables of X,
and such that det(M)=f(X).
A classic open problem is to show that the permanent has super-polynomial (or even exponential) determinantal complexity.
We (Pushkar Joglekar and I) are interested in showing lower bounds for explicit polynomials,
assuming restrictions on the matrix, for example, restricting the number of occurrences of the variables.