Tail bounds for occupancy and the satisfiability threshold conjecture

DOI10.1002/RSA.3240070105zbMATH Open0834.68051OpenAlexW1985250014WikidataQ123201026 ScholiaQ123201026MaRDI QIDQ4847396FDOQ4847396

Authors: Anil P. Kamath, Krishna Palem, P. 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

Recommendations

• The unsatisfiability threshold revisited
• The unsatisfiability threshold revisited
• Bounding the unsatisfiability threshold of random 3-SAT
• scientific article; zbMATH DE number 1114008
• Approximating the unsatisfiability threshold of random formulas

zbMATH Keywords

occupancy problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (35)

• Randomized path coloring on binary trees.
• Entropy of theK-Satisfiability Problem
• GD-SAT model and crossover line
• The unsatisfiability threshold revisited
• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• On good algorithms for determining unsatisfiability of propositional formulas
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• On the false-positive rate of Bloom filters
• On the satisfiability threshold of formulas with three literals per clause
• Refined large deviation asymptotics for the classical occupancy problem
• Ordered binary decision diagrams and the Shannon effect
• On threshold properties of \(k\)-SAT: An additive viewpoint
• Near-optimal radio use for wireless network synchronization
• Sharp thresholds of graph properties, and the $k$-sat problem
• Upper bounds on the satisfiability threshold
• Regular and General Resolution: An Improved Separation
• Rigorous results for random (\(2+p)\)-SAT
• Large deviation asymptotics for occupancy problems.
• Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
• Title not available (Why is that?)
• The Effects of Local Randomness in the Adversarial Queueing Model
• Pseudorandom correlation functions from variable-density LPN, revisited
• Fast computation by population protocols with a leader
• Estimating satisfiability
• Multiple Round Random Ball Placement: Power of Second Chance
• The Complexity of Deciding Strictly Non-Blocking Concentration and Generalized-Concentration Properties
• Tight minimax rates for manifold estimation under Hausdorff loss
• The unsatisfiability threshold revisited
• A glimpse at Paul G. Spirakis
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• Secure and highly-available aggregation queries in large-scale sensor networks via set sampling
• Mobile facility location: combinatorial filtering via weighted occupancy
• Selecting Complementary Pairs of Literals
• Sharp thresholds for Hamiltonicity in random intersection graphs
• The scaling window of the 2-SAT transition

This page was built for publication: Tail bounds for occupancy and the satisfiability threshold conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4847396)