
On the Probabilistic Degree of an nvariate Boolean Function
Nisan and Szegedy (CC 1994) showed that any Boolean function f:{0,1}^n→{...
read it

Schur Polynomials do not have small formulas if the Determinant doesn't!
Schur Polynomials are families of symmetric polynomials that have been c...
read it

On the Probabilistic Degrees of Symmetric Boolean functions
The probabilistic degree of a Boolean function f:{0,1}^n→{0,1} is define...
read it

Decoding Downset codes over a finite grid
In a recent paper, Kim and Kopparty (Theory of Computing, 2017) gave a d...
read it

Strongly Exponential Separation Between Monotone VP and Monotone VNP
We show that there is a sequence of explicit multilinear polynomials P_n...
read it

On the Probabilistic Degree of OR over the Reals
We study the probabilistic degree over reals of the OR function on n var...
read it

A #SAT Algorithm for Small ConstantDepth Circuits with PTF gates
We show that there is a randomized algorithm that, when given a small co...
read it

A FixedDepth SizeHierarchy Theorem for AC^0[⊕] via the Coin Problem
We prove the first Fixeddepth Sizehierarchy Theorem for uniform AC^0[⊕...
read it

The Coin Problem in Constant Depth: Sample Complexity and Parity Gates
The δCoin Problem is the computational problem of distinguishing betwee...
read it

AverageCase Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
We show averagecase lower bounds for explicit Boolean functions again...
read it

A NearOptimal DepthHierarchy Theorem for SmallDepth Multilinear Circuits
We study the size blowup that is necessary to convert an algebraic circ...
read it

Smalldepth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
In this paper, we study the algebraic formula complexity of multiplying ...
read it

Local decoding and testing of polynomials over grids
The wellknown DeMilloLiptonSchwartzZippel lemma says that nvariate ...
read it
Srikanth Srinivasan
is this you? claim profile