Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Srikanth Srinivasan:

TR17-138 | 17th September 2017
Srikanth Srinivasan, Madhu Sudan

Local decoding and testing of polynomials over grids

The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that $n$-variate
polynomials of total degree at most $d$ over
grids, i.e. sets of the form $A_1 \times A_2 \times \cdots \times A_n$, form
error-correcting codes (of distance at least $2^{-d}$ provided $\min_i\{|A_i|\}\geq 2$).
In this work we explore their local
decodability and local testability. ... more >>>

TR17-077 | 30th April 2017
Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>>

TR17-022 | 13th February 2017
Benjamin Rossman, Srikanth Srinivasan

Separation of AC$^0[\oplus]$ Formulas and Circuits

This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the $\mathrm{AC}^0[\oplus]$ basis (unbounded fan-in AND, OR, NOT and MOD$_2$ gates). We show, for all $d(n) \le O(\frac{\log n}{\log\log n})$, that there exist {\em polynomial-size depth-$d$ circuits} that are not equivalent ... more >>>

TR16-204 | 20th December 2016
Prahladh Harsha, Srikanth Srinivasan

Robust Multiplication-based Tests for Reed-Muller Codes

We consider the following multiplication-based tests to check if a given function $f: \mathbb{F}_q^n\to \mathbb{F}_q$ is the evaluation of a degree-$d$ polynomial over $\mathbb{F}_q$ for $q$ prime.

* $\mathrm{Test}_{e,k}$: Pick $P_1,\ldots,P_k$ independent random degree-$e$ polynomials and accept iff the function $fP_1\cdots P_k$ is the evaluation of a degree-$(d+ek)$ polynomial.

... more >>>

TR16-068 | 28th April 2016
Prahladh Harsha, Srikanth Srinivasan

On Polynomial Approximations to $\mathrm{AC}^0$

Revisions: 1

We make progress on some questions related to polynomial approximations of $\mathrm{AC}^0$. It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. $6$th CCC 1991), that any $\mathrm{AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$-error probabilistic polynomial over the reals ... more >>>

TR15-191 | 26th November 2015
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits

We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is \epsilon_d > 0 such that Parity has correlation at most 1/n^{\Omega(1)} with depth-d threshold circuits which have at most
n^{1+\epsilon_d} ... more >>>

TR15-142 | 28th August 2015
Srikanth Srinivasan

A Compression Algorithm for $AC^0[\oplus]$ circuits using Certifying Polynomials

A recent work of Chen, Kabanets, Kolokolova, Shaltiel and Zuckerman (CCC 2014, Computational Complexity 2015) introduced the Compression problem for a class $\mathcal{C}$ of circuits, defined as follows. Given as input the truth table of a Boolean function $f:\{0,1\}^n \rightarrow \{0,1\}$ that has a small (say size $s$) circuit from ... more >>>

TR13-100 | 15th July 2013
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Lower bounds for depth $4$ formulas computing iterated matrix multiplication

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth $4$ arithmetic formula computing the product of $d$ generic matrices of size $n \times n$, IMM$_{n,d}$, has size $n^{\Omega(\sqrt{d})}$ as long as $d \leq n^{1/10}$. This improves the result of Nisan and Wigderson (Computational ... more >>>

TR12-102 | 16th August 2012
Swastik Kopparty, Srikanth Srinivasan

Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ circuits, with applications

In this paper, we introduce and develop the method of certifying polynomials for proving $\mathrm{AC}^0[\oplus]$ circuit lower bounds.

We use this method to show that Approximate Majority cannot be computed by $\mathrm{AC}^0[\oplus]$ circuits of size $n^{1+o(1)}$. This implies a separation between the power of $\mathrm{AC}^0[\oplus]$ circuits of near-linear size and ... more >>>

TR12-051 | 25th April 2012
Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan

A Tail Bound for Read-k Families of Functions

We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables $Y_1,\ldots,Y_r$ are arbitrary Boolean functions of independent random variables $X_1,\ldots,X_m$, modulo a restriction that every $X_i$ influences at most $k$ of the variables $Y_1,\ldots,Y_r$.

more >>>

TR11-131 | 29th September 2011
Rahul Santhanam, Srikanth Srinivasan

On the Limits of Sparsification

Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs:
every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear
number of clauses. This lemma has subsequently played a key role in the study
of the exact complexity of the satisfiability problem. A natural question is
more >>>

TR09-122 | 23rd November 2009
Vikraman Arvind, Srikanth Srinivasan

Circuit Lower Bounds, Help Functions, and the Remote Point Problem

We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Remote Point Problem (introduced by Alon, Panigrahy, and Yekhanin (RANDOM '09)). More precisely, proving ... more >>>

TR09-105 | 27th October 2009
Vikraman Arvind, Srikanth Srinivasan

The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets

Using $\epsilon$-bias spaces over F_2 , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an $NC^2$ algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace F_n by G^n for an arbitrary fixed ... more >>>

TR09-103 | 26th October 2009
Vikraman Arvind, Srikanth Srinivasan

On the Hardness of the Noncommutative Determinant

In this paper we study the computational complexity of computing the noncommutative determinant. We first consider the arithmetic circuit complexity of computing the noncommutative determinant polynomial. Then, more generally, we also examine the complexity of computing the determinant (as a function) over noncommutative domains. Our hardness results are summarized below:

... more >>>

TR09-073 | 6th September 2009
Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan

On Lower Bounds for Constant Width Arithmetic Circuits

The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following.
1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit ... more >>>

TR08-025 | 3rd January 2008
Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

New results on Noncommutative and Commutative Polynomial Identity Testing

Revisions: 2

Using ideas from automata theory we design a new efficient
(deterministic) identity test for the \emph{noncommutative}
polynomial identity testing problem (first introduced and studied by
Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely,
given as input a noncommutative
circuit $C(x_1,\cdots,x_n)$ computing a ... more >>>

ISSN 1433-8092 | Imprint