All reports by Author Don Coppersmith:

__
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

__
TR04-052
| 14th June 2004
__

Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld#### Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions

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

Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld

In this paper, we study two questions related to

the problem of testing whether a function is close to a homomorphism.

For two finite groups $G,H$ (not necessarily Abelian),

an arbitrary map $f:G \rightarrow H$, and a parameter $0 < \epsilon <1$,

say that $f$ is $\epsilon$-close to a homomorphism ...
more >>>