Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Hamming distance:
TR98-077 | 19th December 1998
Miklos Ajtai

Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions

Revisions: 1

Our computational model is a random access machine with $n$
read only input registers each containing $ c \log n$ bits of
information and a read and write memory. We measure the time by the
number of accesses to the input registers. We show that for all $k$
there is ... more >>>

TR04-120 | 22nd November 2004
Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis

Lower bounds on the Deterministic and Quantum Communication Complexity of HAM_n^a

Alice and Bob want to know if two strings of length $n$ are
almost equal. That is, do they differ on at most $a$ bits?
Let $0\le a\le n-1$.
We show that any deterministic protocol, as well as any
error-free quantum protocol ($C^*$ version), for this problem
requires at ... more >>>

TR09-015 | 19th February 2009
Joshua Brody, Amit Chakrabarti

A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences

The Gap-Hamming-Distance problem arose in the context of proving space
lower bounds for a number of key problems in the data stream model. In
this problem, Alice and Bob have to decide whether the Hamming distance
between their $n$-bit input strings is large (i.e., at least $n/2 +
\sqrt n$) ... more >>>

TR15-111 | 8th July 2015
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

Low Distortion Embedding from Edit to Hamming Distance using Coupling

Revisions: 1

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings $x,y$ lying in the Boolean hypercube. The edit distance between $x$ and $y$ is defined as the minimum number of character insertion, deletion, and bit flips needed for converting $x$ into $y$. ... more >>>

TR15-128 | 10th August 2015
Roee David, Elazar Goldenberg, Robert Krauthgamer

Local Reconstruction of Low-Rank Matrices and Subspaces

Revisions: 2

We study the problem of \emph{reconstructing a low-rank matrix}, where the input is an $n\times m$ matrix $M$ over a field $\mathbb{F}$ and the goal is to reconstruct a (near-optimal) matrix $M'$ that is low-rank and close to $M$ under some distance function $\Delta$.
Furthermore, the reconstruction must be local, ... more >>>

ISSN 1433-8092 | Imprint