research
∙
09/15/2023
The discrepancy of greater-than
The discrepancy of the n × n greater-than matrix is shown to be π/2 ln n...
share
research
∙
05/08/2023
Low-Degree Testing Over Grids
We study the question of local testability of low (constant) degree func...
research
∙
02/14/2023
Towards Optimal Depth-Reductions for Algebraic Formulas
Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 197...
research
∙
05/22/2022
Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
We study the following natural question on random sets of points in 𝔽_2^...
research
∙
02/10/2022
A Robust Version of Hegedűs's Lemma, with Applications
Hegedűs's lemma is the following combinatorial statement regarding polyn...
research
∙
07/07/2021
On the Probabilistic Degree of an n-variate Boolean Function
Nisan and Szegedy (CC 1994) showed that any Boolean function f:{0,1}^n→{...
research
∙
11/28/2019
Schur Polynomials do not have small formulas if the Determinant doesn't!
Schur Polynomials are families of symmetric polynomials that have been c...
research
∙
10/06/2019
On the Probabilistic Degrees of Symmetric Boolean functions
The probabilistic degree of a Boolean function f:{0,1}^n→{0,1} is define...
research
∙
08/20/2019
Decoding Downset codes over a finite grid
In a recent paper, Kim and Kopparty (Theory of Computing, 2017) gave a d...
research
∙
03/05/2019
Strongly Exponential Separation Between Monotone VP and Monotone VNP
We show that there is a sequence of explicit multilinear polynomials P_n...
research
∙
12/05/2018
On the Probabilistic Degree of OR over the Reals
We study the probabilistic degree over reals of the OR function on n var...
research
∙
09/16/2018
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates
We show that there is a randomized algorithm that, when given a small co...
research
∙
09/11/2018
A Fixed-Depth Size-Hierarchy Theorem for AC^0[⊕] via the Coin Problem
We prove the first Fixed-depth Size-hierarchy Theorem for uniform AC^0[⊕...
research
∙
09/11/2018
The Coin Problem in Constant Depth: Sample Complexity and Parity Gates
The δ-Coin Problem is the computational problem of distinguishing betwee...
research
∙
06/16/2018
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
We show average-case lower bounds for explicit Boolean functions again...
research
∙
04/07/2018
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
We study the size blow-up that is necessary to convert an algebraic circ...
research
∙
10/16/2017
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
In this paper, we study the algebraic formula complexity of multiplying ...
research
∙
09/18/2017