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
(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
(link)
-
On the Rational Degree of Boolean Functions and Applications (link)
-
Searching for Regularity in Bounded Functions (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 (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
