All reports by Author Ameya Velingker:

__
TR21-086
| 22nd June 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy#### Linear Space Streaming Lower Bounds for Approximating CSPs

Revisions: 1

__
TR16-132
| 23rd August 2016
__

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker#### On the Sensitivity Conjecture for Read-k Formulas

__
TR16-090
| 27th May 2016
__

Bernhard Haeupler, Ameya Velingker#### Bridging the Capacity Gap Between Interactive and One-Way Communication

__
TR14-165
| 3rd December 2014
__

Venkatesan Guruswami, Ameya Velingker#### An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets

__
TR14-067
| 4th May 2014
__

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang#### Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

__
TR12-082
| 28th June 2012
__

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker#### Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on instances with $O(n)$ constraints. We also identify ... more >>>

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

Bernhard Haeupler, Ameya Velingker

We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise.

Recently, Haeupler (FOCS '14) showed that if an $\epsilon > 0$ fraction of transmissions are corrupted, adversarially or randomly, then it is possible to ... more >>>

Venkatesan Guruswami, Ameya Velingker

We prove a lower estimate on the increase in entropy when two copies of a conditional random variable $X | Y$, with $X$ supported on $\mathbb{Z}_q=\{0,1,\dots,q-1\}$ for prime $q$, are summed modulo $q$. Specifically, given two i.i.d. copies $(X_1,Y_1)$ and $(X_2,Y_2)$ of a pair of random variables $(X,Y)$, with $X$ ... more >>>

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length $N$ and distance $d$ is known to ... more >>>

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker

We prove that a random linear code over $\mathbb{F}_q$, with probability arbitrarily close to $1$, is list decodable at radius $1-1/q-\epsilon$ with list size $L=O(1/\epsilon^2)$ and rate $R=\Omega_q(\epsilon^2/(\log^3(1/\epsilon)))$. Up to the polylogarithmic factor in $1/\epsilon$ and constant factors depending on $q$, this matches the lower bound $L=\Omega_q(1/\epsilon^2)$ for the list ... more >>>