My research field is complexity theory, mainly algebraic complexity. In this area we study the complexity of computing certain algebraic problems. Most notably we are interested in the following questions:
Designing algorithms:
The first problem is coming up with efficient algorithms for computing certain polynomials. For example, one of the main questions in the field is to design a nearly linear time algorithm for multiplying two nxn matrices. Another major goal is finding a nearly linear time algorithm for polynomial factorization.
Proving lower bounds:
The opposite (complementary) research goal is to prove lower bounds on the efficiency of algorithms computing certain algebraic problems. For example, is it possible to prove that any algorithm that computes the permanent of an nxn matrix requires a super polynomial number of arithmetic operations? If such a lower bound is proved then we will get that P is not equal NP in the algebraic world.
Derandomization of Polynomial Identity Testing:
Assume that we are given an algorithm (that only uses the operations +, x) that computes a certain n-variate polynomial P(x1,...,xn). How can we verify whether this polynomial is the zero polynomial? One natural approach is to pick a random point (a1,...,an) from a large enough domain and check whether P(a1,...,an)=0. This is a good algorithm but an interesting question is whether this can be done deterministically without using any randomness.
Learning/Interpolating/Reconstructing polynomials:
Assume that there is a black box containing a polynomial P(x1,...,xn). we are allowed to ask the black box for values of the polynomial at points of our choice. I.e. we can get P(a1,...,an), for any point (a1,...,an) that we choose. It is clear that if we make enough queries then we have enough information that should allow us to reconstruct the polynomial. The problem is to come up with an efficient algorithm that uses a small number of queries for this task.