Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR96-044 | 6th August 1996
Yosi Ben-Asher, Ilan Newman

Optimal Search in Trees

Revisions: 1

It is well known that the optimal solution for
searching in
a finite total order set is the binary search.
In the binary search we
divide the set into two ``halves'', by querying the middle
element, and continue the search on the suitable half.
What is the equivalent of binary ... more >>>


TR96-043 | 16th August 1996
Edmund Ihler

On polynomial time approximation schemes and approximation preserving reductions

We show that a fully polynomial time approximation scheme given
for an optimization problem can always be simply modified to a
polynomial time algorithm solving the problem optimally if the
computation model is the deterministic Turing Machine or the
logarithmic cost RAM and ... more >>>


TR96-042 | 26th July 1996
Oded Goldreich, Shai Halevi

Collision-Free Hashing from Lattice Problems

Recently Ajtai described a construction of one-way functions whose
security is equivalent to the difficulty of some well known approximation
problems in lattices. We show that essentially the same
construction can also be used to obtain collision-free hashing.

more >>>


previous PreviousNext next


ISSN 1433-8092 | Imprint