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