Gorav Jindal

Research

What I work on, and where the different threads connect.

My work sits in theoretical computer science, with a focus on algebraic complexity theory and computational complexity. I study algebraic models of computation, the complexity of polynomials, and the structure of algebraic and combinatorial problems.

01

Algebraic complexity theory (ACT)

I study the power and limits of algebraic models of computation: arithmetic circuits, polynomial identity testing, division and truncation, polynomial interpolation, and the geometric complexity theory program. A recurring theme is what algebraic algorithms can do without randomness, and how algebraic natural proofs and border complexity constrain lower-bound techniques.

02

Computational complexity (CC)

I study the structural and algorithmic complexity of algebraic and combinatorial problems: NP-hardness, parameterized complexity, real feasibility, PosSLP, sums of squares, and the complexity of deciding polynomial systems. Recent work connects Hilbert's Nullstellensatz and multivariate resultants to optimization, counting hierarchies, and real feasibility.

Developing interests

I have not published in automata and formal power series yet, but I am developing interests in them—especially deciding rationality of formal power series—and in problems about linear dynamical systems. If you are working on a related question and would like to collaborate, get in touch.