loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
Miklós Ajtai, IBM Almaden Research Center
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 probabiltiy 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 \sigma -additive 0 - 1 measure defined on the set of all subsets of some set S.
Citation:
Miklós Ajtai, "Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties," focs, pp.733, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.