Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Satyanarayana V. Lokam:

TR16-132 | 23rd August 2016
Mitali Bafna, Satyanarayana V. Lokam, S├ębastien Tavenas, Ameya Velingker

On the Sensitivity Conjecture for Read-k Formulas

Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision ... more >>>

TR13-052 | 3rd April 2013
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

{Upper Bounds on Fourier Entropy

Revisions: 2

iven a function $f : \{0,1\}^n \to \reals$, its {\em Fourier Entropy} is defined to be $-\sum_S \fcsq{f}{S} \log \fcsq{f}{S}$, where $\fhat$ denotes the Fourier transform of $f$. This quantity arises in a number of applications, especially in the study of Boolean functions. An outstanding open question is a conjecture ... more >>>

TR11-153 | 13th November 2011
Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam

Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2

We present a randomized algorithm for reconstructing multilinear depth-4 arithmetic circuits with fan-in 2 at the top + gate. The algorithm is given blackbox access to a multilinear polynomial f in F[x_1,..,x_n] computable by a multilinear Sum-Product-Sum-Product(SPSP) circuit of size s and outputs an equivalent multilinear SPSP circuit, runs ... more >>>

TR09-106 | 28th October 2009
Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma

Using Elimination Theory to construct Rigid Matrices

The rigidity of a matrix A for target rank r is the minimum number of entries
of A that must be changed to ensure that the rank of the altered matrix is at
most r. Since its introduction by Valiant (1977), rigidity and similar
rank-robustness functions of matrices have found ... more >>>

ISSN 1433-8092 | Imprint