All reports by Author Srikanth Srinivasan:

__
TR22-139
| 15th October 2022
__

Radu Curticapean, Nutan Limaye, Srikanth Srinivasan#### On the VNP-hardness of Some Monomial Symmetric Polynomials

__
TR22-090
| 24th June 2022
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials

__
TR22-075
| 21st May 2022
__

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan#### Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes

Revisions: 1

__
TR21-098
| 7th July 2021
__

Srikanth Srinivasan, S Venkitesh#### On the Probabilistic Degree of an $n$-variate Boolean Function

Radu Curticapean, Nutan Limaye, Srikanth Srinivasan

A polynomial $P\in F[x_1,\ldots,x_n]$ is said to be symmetric if it is invariant under any permutation of its input variables. The study of symmetric polynomials is a classical topic in mathematics, specifically in algebraic combinatorics and representation theory. More recently, they have been studied in several works in computer science, ... more >>>

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits.

More specifically, our previous work applied the well-known partial derivative method in a new setting, that of 'lopsided' set-multilinear polynomials. A ... more >>>

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

We study the following natural question on random sets of points in $\mathbb{F}_2^m$:

Given a random set of $k$ points $Z=\{z_1, z_2, \dots, z_k\} \subseteq \mathbb{F}_2^m$, what is the dimension of the space of degree at most $r$ multilinear polynomials that vanish on all points in $Z$?

We ... more >>>

Srikanth Srinivasan, S Venkitesh

Nisan and Szegedy (CC 1994) showed that any Boolean function $f:\{0,1\}^n\to\{0,1\}$ that depends on all its input variables, when represented as a real-valued multivariate polynomial $P(x_1,\ldots,x_n)$, has degree at least $\log n - O(\log \log n)$. This was improved to a tight $(\log n - O(1))$ bound by Chiarelli, Hatami ... more >>>