All reports by Author Adam Smith:

__
TR10-077
| 26th April 2010
__

Venkatesan Guruswami, Adam Smith#### Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate

__
TR06-089
| 16th July 2006
__

Sofya Raskhodnikova, Adam Smith#### A Note on Adaptivity in Testing Properties of Bounded Degree Graphs

__
TR05-125
| 2nd November 2005
__

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith#### Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

We raise the question of approximating compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present algorithms and lower bounds for approximating compressibility with respect to ... more >>>

Venkatesan Guruswami, Adam Smith

In this paper, we consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently ... more >>>

Sofya Raskhodnikova, Adam Smith

We show that in the bounded degree model for graph property testing,

adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ...
more >>>

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith