All reports by Author Atri Rudra:

__
TR18-027
| 8th February 2018
__

Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan#### General Strong Polarization

Revisions: 1

__
TR16-130
| 11th August 2016
__

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra#### Tight Network Topology Dependent Bounds on Rounds of Communication

__
TR14-104
| 9th August 2014
__

Atri Rudra, Mary Wootters#### It'll probably work out: improved list-decoding through random operations

__
TR14-074
| 14th May 2014
__

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra#### Topology matters in communication

__
TR13-140
| 8th October 2013
__

Atri Rudra, Mary Wootters#### Every list-decodable code for high noise has abundant near-optimal rate puncturings

__
TR12-093
| 1st July 2012
__

Charanjit Jutla, Vijay Kumar, Atri Rudra#### On the Circuit Complexity of Composite Galois Field Transformations

__
TR11-080
| 11th May 2011
__

mohammad iftekhar husain, steve ko, Atri Rudra, steve uurtamo#### Storage Enforcement with Kolmogorov Complexity and List Decoding

__
TR10-007
| 12th January 2010
__

Atri Rudra, steve uurtamo#### Two Theorems in List Decoding

__
TR09-013
| 4th February 2009
__

Atri Rudra#### Limits to List Decoding Random Codes

__
TR08-054
| 13th May 2008
__

Venkatesan Guruswami, Atri Rudra#### Concatenated codes can achieve list-decoding capacity

__
TR08-036
| 14th March 2008
__

Venkatesan Guruswami, Atri Rudra#### Soft decoding, dual BCH codes, and better list-decodable eps-biased codes

__
TR07-109
| 7th October 2007
__

Venkatesan Guruswami, Atri Rudra#### Better Binary List-Decodable Codes via Multilevel Concatenation

__
TR05-133
| 17th November 2005
__

Venkatesan Guruswami, Atri Rudra#### Explicit Capacity-Achieving List-Decodable Codes

Revisions: 1

__
TR05-131
| 7th November 2005
__

Don Coppersmith, Lisa Fleischer, Atri Rudra#### Ordering by weighted number of wins gives a good ranking for weighted tournaments

__
TR05-104
| 16th September 2005
__

Don Coppersmith, Atri Rudra#### On the Robust Testability of Product of Codes

__
TR05-019
| 9th February 2005
__

Venkatesan Guruswami, Atri Rudra#### Tolerant Locally Testable Codes

Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan

Ar\i kan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix $M$, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the $\textit{polarization}$ of an associated $[0,1]$-bounded martingale, ... more >>>

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent ... more >>>

Atri Rudra, Mary Wootters

In this work, we introduce a framework to study the effect of random operations on the combinatorial list decodability of a code.

The operations we consider correspond to row and column operations on the matrix obtained from the code by stacking the codewords together as columns. This captures many natural ...
more >>>

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra

We provide the first communication lower bounds that are sensitive to the network topology for computing natural and simple functions by point to point message passing protocols for the `Number in Hand' model. All previous lower bounds were either for the broadcast model or assumed full connectivity of the network. ... more >>>

Atri Rudra, Mary Wootters

We show that any $q$-ary code with sufficiently good distance can be randomly punctured to obtain, with high probability, a code that is list decodable up to radius $1 - 1/q - \epsilon$ with near-optimal rate and list sizes.

Our results imply that ``most" Reed-Solomon codes are list decodable ... more >>>

Charanjit Jutla, Vijay Kumar, Atri Rudra

We study the circuit complexity of linear transformations between Galois fields GF(2^{mn}) and their isomorphic composite fields GF((2^{m})^n). For such a transformation, we show a lower bound of \Omega(mn) on the number of gates required in any circuit consisting of constant-fan-in XOR gates, except for a class of transformations between ... more >>>

mohammad iftekhar husain, steve ko, Atri Rudra, steve uurtamo

We consider the following problem that arises in outsourced storage: a user stores her data $x$ on a remote server but wants to audit the server at some later point to make sure it actually did store $x$. The goal is to design a (randomized) verification protocol that has the ... more >>>

Atri Rudra, steve uurtamo

We prove the following results concerning the list decoding of error-correcting codes:

We show that for any code with a relative distance of $\delta$

(over a large enough alphabet), the

following result holds for random errors: With high probability,

for a $\rho\le \delta -\eps$ fraction of random errors (for any ...
more >>>

Atri Rudra

It has been known since [Zyablov and Pinsker 1982] that a random $q$-ary code of rate $1-H_q(\rho)-\eps$ (where $0<\rho<1-1/q$, $\eps>0$ and $H_q(\cdot)$ is the $q$-ary entropy function) with high probability is a $(\rho,1/\eps)$-list decodable code. (That is, every Hamming ball of radius at most $\rho n$ has at most $1/\eps$ ... more >>>

Venkatesan Guruswami, Atri Rudra

We prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. In particular, for any $0 < \rho < 1/2$ and $\epsilon > 0$, there exist concatenated codes of ... more >>>

Venkatesan Guruswami, Atri Rudra

We construct binary linear codes that are efficiently list-decodable

up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits

into $n = {\rm poly}(k/\eps)$ bits and are constructible and

list-decodable in time polynomial in $k$ and $1/\eps$ (in

particular, in our results $\eps$ need ...
more >>>

Venkatesan Guruswami, Atri Rudra

We give a polynomial time construction of binary codes with the best

currently known trade-off between rate and error-correction

radius. Specifically, we obtain linear codes over fixed alphabets

that can be list decoded in polynomial time up to the so called

Blokh-Zyablov bound. Our work ...
more >>>

Venkatesan Guruswami, Atri Rudra

For every $0 < R < 1$ and $\eps > 0$, we present an explicit

construction of error-correcting codes of rate $R$ that can be list

decoded in polynomial time up to a fraction $(1-R-\eps)$ of errors.

These codes achieve the ``capacity'' for decoding from {\em ...
more >>>

Don Coppersmith, Lisa Fleischer, Atri Rudra

We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of $5$ if the weights satisfy \textit{probability constraints}

(for any pair of vertices $u$ and $v$, $w_{uv}+w_{vu}=1$). Special cases ...
more >>>

Don Coppersmith, Atri Rudra

Ben-Sasson and Sudan in~\cite{BS04} asked if the following test

is robust for the tensor product of a code with another code--

pick a row (or column) at random and check if the received word restricted to the picked row (or column) belongs to the corresponding code. Valiant showed that ...
more >>>

Venkatesan Guruswami, Atri Rudra

An error-correcting code is said to be {\em locally testable} if it has an

efficient spot-checking procedure that can distinguish codewords

from strings that are far from every codeword, looking at very few

locations of the input in doing so. Locally testable codes (LTCs) have

generated ...
more >>>