Pages that link to "Item:Q3581271"
From MaRDI portal
The following pages link to The threshold for random k-SAT is 2 <sup>k</sup> (ln 2 - O(k)) (Q3581271):
Displaying 27 items.
- A note on random \(k\)-SAT for moderately growing \(k\) (Q426783) (← links)
- A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming (Q507445) (← links)
- Connectivity and equilibrium in random games (Q549865) (← links)
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT (Q706614) (← links)
- Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability (Q840834) (← links)
- On threshold properties of \(k\)-SAT: An additive viewpoint (Q852710) (← links)
- Network models: structure and function. Abstracts from the workshop held December 10--16, 2017 (Q1731967) (← links)
- On the lower bounds of random Max 3 and 4-SAT (Q1752631) (← links)
- A sharp threshold for a random constraint satisfaction problem (Q1877674) (← links)
- A sharp threshold in proof complexity yields lower bounds for satisfiability search (Q1887710) (← links)
- Proof of the satisfiability conjecture for large \(k\) (Q2171413) (← links)
- Random \(k\)-SAT: A tight threshold for moderately growing \(k\) (Q2387184) (← links)
- Maximum independent sets on random regular graphs (Q2407501) (← links)
- Typical case complexity of satisfiability algorithms and the threshold phenomenon (Q2581549) (← links)
- A concentration inequality for the facility location problem (Q2670506) (← links)
- On smoothed analysis in dense graphs and formulas (Q3419587) (← links)
- Super Solutions of Random Instances of Satisfiability (Q3452579) (← links)
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae (Q4360139) (← links)
- Random MAX SAT, random MAX CUT, and their phase transitions (Q4739584) (← links)
- On the critical exponents of random <i>k</i>‐SAT (Q4803316) (← links)
- Counting Solutions to Random CNF Formulas (Q5096442) (← links)
- Superlogarithmic Cliques in Dense Inhomogeneous Random Graphs (Q5234663) (← links)
- On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT (Q5384461) (← links)
- A lower bound for the 4-satisfiability threshold (Q5439053) (← links)
- Biased random <i>k</i>‐SAT (Q6074657) (← links)
- Tractability from overparametrization: the example of the negative perceptron (Q6193766) (← links)
- Searching for (sharp) thresholds in random structures: where are we now? (Q6658193) (← links)
