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

__
TR13-052
| 3rd April 2013
__

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh#### {Upper Bounds on Fourier Entropy

Revisions: 2

__
TR11-153
| 13th November 2011
__

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam#### Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2

__
TR09-106
| 28th October 2009
__

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma#### Using Elimination Theory to construct Rigid Matrices

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker

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

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

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

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam

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

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma

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