research
∙
02/14/2023
Towards Optimal Depth-Reductions for Algebraic Formulas
Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 197...
share
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
∙
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
∙
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