Tail bounds for occupancy and the satisfiability threshold conjecture
From MaRDI portal
Publication:4847396
DOI10.1002/rsa.3240070105zbMath0834.68051OpenAlexW1985250014WikidataQ123201026 ScholiaQ123201026MaRDI QIDQ4847396
Krishna V. Palem, Anil P. Kamath, Paul G. Spirakis, Rajeev Motwani
Publication date: 18 March 1996
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.3240070105
Related Items
Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT ⋮ GD-SAT model and crossover line ⋮ Ordered binary decision diagrams and the Shannon effect ⋮ Sharp thresholds of graph properties, and the $k$-sat problem ⋮ Large deviation asymptotics for occupancy problems. ⋮ Fast computation by population protocols with a leader ⋮ On threshold properties of \(k\)-SAT: An additive viewpoint ⋮ Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ A Glimpse at Paul G. Spirakis ⋮ The unsatisfiability threshold revisited ⋮ Refined large deviation asymptotics for the classical occupancy problem ⋮ Unnamed Item ⋮ Multiple Round Random Ball Placement: Power of Second Chance ⋮ Unnamed Item ⋮ Pseudorandom correlation functions from variable-density LPN, revisited ⋮ Regular and General Resolution: An Improved Separation ⋮ On good algorithms for determining unsatisfiability of propositional formulas ⋮ The Effects of Local Randomness in the Adversarial Queueing Model ⋮ Secure and highly-available aggregation queries in large-scale sensor networks via set sampling ⋮ The scaling window of the 2-SAT transition ⋮ Tight minimax rates for manifold estimation under Hausdorff loss ⋮ On the satisfiability threshold and clustering of solutions of random 3-SAT formulas ⋮ Mobile facility location: combinatorial filtering via weighted occupancy ⋮ On the false-positive rate of Bloom filters ⋮ Sharp thresholds for Hamiltonicity in random intersection graphs ⋮ On the satisfiability threshold of formulas with three literals per clause ⋮ Near-optimal radio use for wireless network synchronization ⋮ Rigorous results for random (\(2+p)\)-SAT ⋮ Upper bounds on the satisfiability threshold ⋮ Estimating satisfiability ⋮ Entropy of theK-Satisfiability Problem ⋮ Randomized path coloring on binary trees. ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ Selecting Complementary Pairs of Literals
Cites Work
