Research
For everything, see my
Google Scholar.
Here are the more recent ones!
-
Communication Complexity of Collision Finding and Cutting Planes Proof Complexity of (Concise) Pigeonhole Principle
(Appeared in ICALP 2025) (manuscript: link)
-
joint work with Paul Beame.
-
We proved a fun collection of results about how much communication is required to find a collision on an input where there is guaranteed to be one!
-
Quantum Time-Space Tradeoffs for Matrix Problems
(appeared in STOC 2025) (SIAM version: pdf)
-
On the Rational Degree of Boolean Functions and Applications (To appear in CJTCS) (link)
-
Searching for Regularity in Bounded Functions (appeared in ICALP 2023) (link)
-
joint work with Siddharth Iyer
-
We spent some time trying to find subspaces for which bounded functions become pseudorandom.
-
Junta Distance Approximation with Sub-Exponential Queries (appeared in CCC 2021) (link)
-
joint work with Vishnu Iyer and Avishay Tal
-
Ever wondered how many (input, output) pairs from your function f you have to look at to estimate how close f is to only depending on a few of its inputs?
So did we.
This work gives an improved algorithm for answering this question for Boolean functions.
If you are really interested in questions like this, you can check out my master's thesis,
which starts with a survey of the previous work done on junta testing and (almost) all its variants.
-
Here's a talk I gave: link
and here is slightly more detailed talk that Avishay gave: link
