The Power of Choice for Random Satisfiability

Varsha Dani, Josep Dı́az, Thomas P. Hayes, Cristopher Moore

Type: Book-Chapter

Publication Date: 2013-01-01

Citations: 1

DOI: https://doi.org/10.1007/978-3-642-40328-6_34

View Publication

Download PDF

Locations

Lecture notes in computer science - View
arXiv (Cornell University) - View - PDF
CiteSeer X (The Pennsylvania State University) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	On the Probabilistic Approach to the Random Satisfiability Problem	2004	Giorgio Parisi
+ PDF Chat	The Satisfiability Threshold For Random Linear Equations	2020	Peter Ayre Amin Coja‐Oghlan Pu Gao Noëla Müller
+ PDF Chat	Optimization and Physics: On the Satisfiability of Random Boolean Formulae	2003	Marc Mézard
+	The Power of Choice for Random Satisfiability	2012	Varsha Dani Josep Dı́az T. Hayes Cristopher Moore
+	The Power of Choice for Random Satisfiability	2012	Varsha Dani Josep Dı́az Thomas P. Hayes Cristopher Moore
+	Random Choices	1977	Steven M. Cahn
+	Randomness and Probability	2010	Shravan Vasishth Michael Broe
+ PDF Chat	Probability and randomness	2003	David Pratt
+	Probability and randomness	2017	R. Paul Thompson Ross Upshur
+ PDF Chat	Probability and Randomness	2010	Rodney Nillsen
+ PDF Chat	Randomness for Free	2010	Krishnendu Chatterjee Laurent Doyen Hugo Gimbert Thomas A. Henzinger
+ PDF Chat	The value of randomisation	2018	Conor Gissane
+	Logic and Random Structures	2007	Joel Spencer
+ PDF Chat	The Power of Two Random Choices: A Survey of Techniques and Results	2001	Michael Mitzenmacher Andréa W. Richa Ramesh K. Sitaraman
+ PDF Chat	Randomisation and Derandomisation in Descriptive Complexity Theory	2010	Kord Eickmeyer Martin Grohe
+	Chance and Randomness	2015	Francesca Merlin
+	Chance and Randomness	2016	William M. Briggs
+	Practical decidability	1975	Andrzej Ehrenfeucht
+ PDF Chat	Satisfiability Threshold for Random Regular nae-sat	2015	Jian Ding Allan Sly Nike Sun
+	Sufficiency and fuzziness in random experiments	1992	Marı́a Ángeles Gil

Works That Cite This (1)

Action	Title	Year	Authors
+ PDF Chat	Random <i>k</i>‐SAT and the power of two choices	2014	Will Perkins

Works Cited by This (16)

Action	Title	Year	Authors
+ PDF Chat	Sharp thresholds of graph properties, and the $k$-sat problem	1999	Ehud Friedgut appendix by Jean Bourgain
+	The Satisfiability Threshold of Random 3-SAT Is at Least 3.52	2003	MohammadTaghi Hajiaghayi Gregory B. Sorkin
+	Almost all graphs with average degree 4 are 3-colorable	2002	Dimitris Achlioptas Cristopher Moore
+	Birth control for giants	2007	Joel Spencer Nicholas Wormald
+ PDF Chat	Differential Equations for Random Processes and Random Graphs	1995	Nicholas Wormald
+ PDF Chat	Achlioptas process phase transitions are continuous	2012	Oliver Riordan Lutz Warnke
+ PDF Chat	Creating a Giant Component	2006	Tom Bohman David Kravitz
+	Explosive Percolation in Random Networks	2009	Dimitris Achlioptas Raissa M. D’Souza Joel Spencer
+ PDF Chat	Avoiding a giant component	2001	Tom Bohman Alan Frieze
+ PDF Chat	Threshold values of random <i>K</i>‐SAT from the cavity method	2005	Stephan Mertens Marc Mézard Riccardo Zecchina