p{margin: 2cm}

Research Interests



Parameterized and exact algorithms:
Fix a graph property P and a subset S of operations from {vertex deletion, vertex addition, edge deletion, edge addition}.
Given a graph G as input, we ask whether we can modify the graph with k operations from S so that the resulting graph has property P.
Since this problem is usually NP-hard, we are interested in parameterized and exact algorithms for such problems.



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.



Graph theory:
In the past, I've been interested in graph coloring with various restrictions, with the goal of obtaining bounds for the associated chromatic numbers, usually using the probabilitic method.
Other topics of interest include random graph models, geometric representations of graphs, discrepancy of set systems, computational number theory, and all combinatorial problems.