Tail bounds for occupancy and the satisfiability threshold conjecture

DOI10.1002/RSA.3240070105MaRDI QIDQ4847396zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

occupancy problem

Mathematics Subject Classification ID

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

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

Cited in

(35)

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

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)