Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Noam Livne:

TR09-143 | 22nd December 2009
Noam Livne

On the Construction of One-Way Functions from Average Case Hardness

In this paper we study the possibility of proving the existence of
one-way functions based on average case hardness. It is well-known
that if there exists a polynomial-time sampler that outputs
instance-solution pairs such that the distribution on the instances
is hard on average, then one-way functions exist. We study ... more >>>

TR06-122 | 20th September 2006
Noam Livne

All Natural NPC Problems Have Average-Case Complete Versions

Revisions: 1

In 1984 Levin put forward a suggestion for a theory of {\em average
case complexity}. In this theory a problem, called a {\em
distributional problem}, is defined as a pair consisting of a
decision problem and a probability distribution over the instances.
Introducing adequate notions of simple distributions and average
more >>>

ISSN 1433-8092 | Imprint