Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR16-014 | 3rd February 2016
Gil Cohen, Leonard Schulman

Extractors for Near Logarithmic Min-Entropy

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

TR12-104 | 8th August 2012
Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman

Optimal Coding for Streaming Authentication and Interactive Communication

Revisions: 1

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

TR04-050 | 13th June 2004
Michelle Effros, Leonard Schulman

Deterministic clustering with data nets

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

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

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

TR99-035 | 6th July 1999
Leonard Schulman

Clustering for Edge-Cost Minimization

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

ISSN 1433-8092 | Imprint