Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HASHING:
Reports tagged with hashing:
TR98-075 | 9th December 1998

#### Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

We establish hardness versus randomness trade-offs for a
broad class of randomized procedures. In particular, we create efficient
nondeterministic simulations of bounded round Arthur-Merlin games using
a language in exponential time that cannot be decided by polynomial
language with ... more >>>

TR11-113 | 11th August 2011
Emanuele Viola

#### Reducing 3XOR to listing triangles, an exposition

The 3SUM problem asks if there are three integers $a,b,c$ summing to $0$ in a given set of $n$ integers of magnitude poly($n$). Patrascu (STOC '10) reduces solving 3SUM in time $n^{2-\Omega(1)}$ to listing $m$ triangles in a graph with $m$ edges in time $m^{4/3-\Omega(1)}$.
In this note we present ... more >>>

TR11-152 | 12th November 2011
Emanuele Viola

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>> TR15-116 | 21st July 2015 Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky #### Efficient Low-Redundancy Codes for Correcting Multiple Deletions Revisions: 1 We consider the problem of constructing binary codes to recover from$k$-bit deletions with efficient encoding/decoding, for a fixed$k$. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with$\approx 2^n/n$codewords of length$n$, i.e., at most$\log n\$ ... more >>>

ISSN 1433-8092 | Imprint