All reports by Author Noam Livne:

__
TR09-143
| 22nd December 2009
__

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

__
TR06-122
| 20th September 2006
__

Noam Livne#### All Natural NPC Problems Have Average-Case Complete Versions

Revisions: 1

Noam Livne

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 >>>

Noam Livne

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 >>>