Conference paper
The invasiveness of off-line memory checking
Miklós Ajtai
STOC 2002
We formulate a conjecture about random n-dimensional lattices with a suitable distribution. The conjecture says that every polynomial time computable property of a random lattice holds with a probability either close to 0 or close to 1. Accepting the conjecture we get a large class of hard lattice problems. We describe an analogy between our conjecture and a set theoretical axiom, which cannot be proved in ZFC. This axiom says that there exists a nontrivial σ-additive 0 - 1 measure defined on the set of all subsets of some set S.
Miklós Ajtai
STOC 2002
Miklós Ajtai, Nathan Linial
Combinatorica
Miklós Ajtai
CIC 2005
Miklós Ajtai
STOC 2003