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
∙
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
∙
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
∙
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
∙
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
