All reports by Author Leonard Schulman:

__
TR18-032
| 14th February 2018
__

Gil Cohen, Bernhard Haeupler, Leonard Schulman#### Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

Revisions: 1

__
TR16-014
| 3rd February 2016
__

Gil Cohen, Leonard Schulman#### Extractors for Near Logarithmic Min-Entropy

__
TR12-104
| 8th August 2012
__

Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman#### Optimal Coding for Streaming Authentication and Interactive Communication

Revisions: 1

__
TR04-050
| 13th June 2004
__

Michelle Effros, Leonard Schulman#### Deterministic clustering with data nets

__
TR01-080
| 14th November 2001
__

Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan#### Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval

Revisions: 3

__
TR99-035
| 6th July 1999
__

Leonard Schulman#### Clustering for Edge-Cost Minimization

Gil Cohen, Bernhard Haeupler, Leonard Schulman

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

For every constant $\delta < 1$ we give an explicit binary tree code with distance $\delta$ and alphabet size $(\log{n})^{O(1)}$, where $n$ is the depth of the tree. This ... more >>>

Gil Cohen, Leonard Schulman

The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any $\delta > 0$ we construct an extractor for $O(1/\delta)$ $n$-bit sources with min-entropy $(\log{n})^{1+\delta}$. This is most interesting when $\delta$ is set to a small constant, though the result also yields an ... more >>>

Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman

Error correction and message authentication are well studied in the literature, and various efficient solutions have been suggested and analyzed. This is however not the case for data streams in which the message is very long, possibly infinite, and not known in advance to the sender. Trivial solutions for error-correcting ... more >>>

Michelle Effros, Leonard Schulman

We consider the $K$-clustering problem with the $\ell_2^2$

distortion measure, also known as the problem of optimal

fixed-rate vector quantizer design. We provide a deterministic

approximation algorithm which works for all dimensions $d$ and

which, given a data set of size $n$, computes in time

more >>>

Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan

We prove that if a linear error correcting code

$\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can

be probabilistically reconstructed by looking at two entries of a

corrupted codeword, then $m = 2^{\Omega(n)}$. We also present

several extensions of this result.

We show a reduction from the ... more >>>

Leonard Schulman

We address the problem of partitioning a set of $n$ points into

clusters, so as to minimize the sum, over all intracluster pairs of

points, of the cost associated with each pair. We obtain a randomized

approximation algorithm for this problem, for the cost functions

$\ell_2^2,\ell_1$ and $\ell_2$, as ...
more >>>