Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SRIKANTH SRINIVASAN:
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

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


TR22-090 | 24th June 2022
Nutan Limaye, Srikanth Srinivasan, S├ębastien Tavenas

On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials

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


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

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


TR21-098 | 7th July 2021
Srikanth Srinivasan, S Venkitesh

On the Probabilistic Degree of an $n$-variate Boolean Function

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




ISSN 1433-8092 | Imprint