(Last updated in August 2025)
I am a Ph.D. student at the Department of Computer Science, University of Copenhagen and a member of BARC. I am glad to be advised by Prof. Srikanth Srinivasan.
I completed my master's at the Department of Computer Science, Aarhus University, and my undergraduate studies at the Chennai Mathematical Institute.
My interests are primarily in Complexity Theory.
Check out this cool video by the theory group at the Aarhus University :)
We consider random walks on the balanced multislice of {0,1,...,s}^{n}, i.e., the set of points with equal number of 0's, equal number of 1's, and so on. We say a random walk respects symmetries if the transition probability remains the same when the coordinates of the initial and final states are permuted simultaneously.
We show that random walks on balanced multislices that respect symmetries and satisfy a couple of other properties have good spectral expansion.
As applications,
We give a polynomial distance lemma over balanced multislices
Local (list) correction algorithms for variants of Reed-Muller codes.
[RANDOM 2025] [ECCC] [arXiv] [doi]
A classical result on low-degree polynomials shows that every non-zero degree-d polynomial over the Boolean cube is non-zero on at least 1/2^{d} fraction of points. In this work, we consider the following generalization:
Given a degree-d non-zero polynomial (in n variables) over any Boolean slice, on how many points is it non-zero over that slice?
The k^{th} slice refers to the set of all Boolean points of Hamming weight exactly k.
We show that the answer is nearly (k/n)^{d}. In particular, for the middle slice (k = n/2), our bound is nearly 1/2^{d}.
[ICALP 2025] [ECCC] [arXiv] [doi]
Ideal Proof System is an algebraic proof system, where Hilbert's Nullstellensatz gives the refutations, and the complexity is measured in terms of the algebraic complexity of the certificate. Motivated by proof complexity, we are typically interested in understanding whether a model of computation can refute a system of polynomials. In this work, we consider IPS over fields of positive characteristic.
We prove lower bounds for various restricted models of computation, such as multilinear constant-depth algebraic circuits, roABPs, and more.
We also prove upper bounds for restricted systems of polynomials:
A sparse polynomial.
A system of symmetric polynomials.
[ICALP 2025] [ECCC] [arXiv] [doi]
A constrained PRF is a PRF that has a constrained key that allows evaluations on a specific subset of the domain. Such PRFs are private if the constrained key returns no information about the subset.
In this work, we look at private constrained PRFs where the PRF evaluates everywhere except a fixed point in the domain. This is known as private punctured PRFs. Previous constructions either used assumptions such as LWE/IO or supported only polynomial-sized domains.
We construct private punctured PRFs using group assumptions (in particular, the Decisional Composite Residuosity assumption) that support exponential-sized domains.
In the problem of local correction, we are given a function promised to be close to a unique low-degree polynomial, and the task is to recover local information of the low-degree polynomial by making queries to the input function. We consider low-degree polynomials with Boolean cube as the domain and coefficients are real numbers.
We give a sublinear query local corrector algorithm.
We also consider the problem of local list correction, we are given a function, which is close to several low-degree polynomials. The task is to recover local information of all the close low-degree polynomials by making queries to the input function (the setup is the same as local correction).
We show that the number of close linear functions is small (a combinatorial bound) and give a local list corrector algorithm.
This work extends the results of [ABPSS'24], who considered these problems for linear functions.
[SODA 2025] [ECCC] [arXiv] [doi]
[Talk by Prashanth Amireddy] [Slides of a talk by Amik] [Slides of a talk by Prashanth]
In the problem of local correction, we are given a polynomial promised to be close to a unique linear function, and the task is to recover local information of the linear function by making queries to the input polynomial. We consider linear functions with Boolean cube as the domain and coefficients are real numbers.
We give a nearly optimal local corrector algorithm (in terms of queries).
We also consider the problem of local list correction, we are given a polynomial, which is close to several linear functions. The task is to recover local information of all the close linear functions by making queries to the input polynomial (the setup is the same as local correction).
We show that the number of close linear functions is small (a combinatorial bound) and give a local list corrector algorithm.
[STOC 2024] [ECCC] [arXiv] [doi]
[Talk by Madhu Sudan] [Slides of a talk by Amik] [STOC Recorded Video] [Slides of a talk by Prashanth]
Email - ambe [at] di [dot] ku [dot] dk
BARC, Vibenshuset, Lyngbyvej
Department of Computer Science, University of Copenhagen
"It is only those who have neither fired a shot nor heard the shriek and groans of the wounded and lacerated who cry aloud for blood, more vengeance, more desolation." - General Sherman, from a letter sent in May of 1865 in the midst of his march to the sea.
"I hear babies cry, I watch them grow
They'll learn much more, Than I'll ever know
And I think to myself, What a wonderful world" - What a Wonderful World, Louis Armstrong
“If you cannot solve a problem, then there is an easier problem that you cannot solve: find that problem.” - George Pólya