Automata, Languages and Programming
Volume 5555 of the series Lecture Notes in Computer Science pp 292-303
A Better Algorithm for Random k-SAT
- Amin Coja-OghlanAffiliated withSchool of Informatics, University of Edinburgh
Abstract
Let Φ be a uniformly distributed random k-SAT formula with n variables and m clauses. We present a polynomial time algorithm that finds a satisfying assignment of Φ with high probability for constraint densities
Reference tools
Other actions
- Title
- A Better Algorithm for Random k-SAT
- Book Title
- Automata, Languages and Programming
- Book Subtitle
- 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I
- Pages
- pp 292-303
- Copyright
- 2009
- DOI
- 10.1007/978-3-642-02927-1_25
- Print ISBN
- 978-3-642-02926-4
- Online ISBN
- 978-3-642-02927-1
- Series Title
- Lecture Notes in Computer Science
- Series Volume
- 5555
- Series ISSN
- 0302-9743
- Publisher
- Springer Berlin Heidelberg
- Copyright Holder
- Springer-Verlag Berlin Heidelberg
- Additional Links
- Topics
- Industry Sectors
- eBook Packages
- Editors
-
- Susanne Albers (16)
- Alberto Marchetti-Spaccamela (17)
- Yossi Matias (18)
- Sotiris Nikoletseas (19)
- Wolfgang Thomas (20)
- Editor Affiliations
-
- 16. Department of Computer Science, University of Freiburg
- 17. Department of Computer and Systems Sciences, Sapienza University of Rome
- 18. Google R&D Center, School of Computer Science, Tel Aviv University
- 19. University of Patras and CTI
- 20. RWTH Aachen, Lehrstuhl Informatik 7, Ahornstraße 55
- Authors
-
- Amin Coja-Oghlan (21)
- Author Affiliations
-
- 21. School of Informatics, University of Edinburgh, Edinburgh, EH8 9AB, UK
Continue reading...
To view the rest of this content please follow the download PDF link above.