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

TR95-031 | 25th June 1995
Dorit Dor, Uri Zwick

Selecting the median

Improving a long standing result of Sch\"{o}nhage, Paterson
and Pippenger we show that the MEDIAN of a set containing n
elements can always be found using at most 2.95n comparisons.

This is the full version of the paper. An extended abstract
version ... more >>>


TR95-030 | 20th June 1995
Marek Karpinski, Alexander Zelikovsky

New Approximation Algorithms for the Steiner Tree Problems

The Steiner tree problem asks for the shortest tree connecting
a given set of terminal points in a metric space. We design
new approximation algorithms for the Steiner tree problems
using a novel technique of choosing Steiner points in dependence
on the possible deviation from ... more >>>


TR95-029 | 15th June 1995
Oded Goldreich, Leonid Levin, Noam Nisan

On Constructing 1-1 One-Way Functions

We show how to construct length-preserving 1-1 one-way
functions based on popular intractability assumptions (e.g., RSA, DLP).
Such 1-1 functions should not
be confused with (infinite) families of (finite) one-way permutations.
What we want and obtain is a single (infinite) 1-1 one-way function.

more >>>


previous PreviousNext next


ISSN 1433-8092 | Imprint