Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Eric Lehman:

TR04-034 | 12th April 2004
April Rasala Lehman, Eric Lehman

Network Coding: Does the Model Need Tuning?

We consider the general network information flow problem, which was
introduced by Ahlswede et. al. We show a periodicity effect: for
every integer m greater than 1, there exists an instance of the
network information flow problem that admits a solution if and only if
the alphabet size is a ... more >>>

TR99-017 | 4th June 1999
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

Improved Testing Algorithms for Monotonicity.

Revisions: 1

We present improved algorithms for testing monotonicity of functions.
Namely, given the ability to query an unknown function $f$, where
$\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a
monotone $f$, and rejects $f$ with high probability if it is $\e$-far
from being monotone (i.e., every ... more >>>

ISSN 1433-8092 | Imprint