Sharp thresholds of graph properties, and the k-sat problem
From MaRDI portal
Sharp thresholds of graph properties, and the $k$-sat problem
Recommendations
Cites work
- scientific article; zbMATH DE number 437557 (Why is no real title available?)
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 3904630 (Why is no real title available?)
- scientific article; zbMATH DE number 3503316 (Why is no real title available?)
- scientific article; zbMATH DE number 1256700 (Why is no real title available?)
- A note on percolation
- An approximate zero-one law
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Boolean functions with low average sensitivity depend on few coordinates
- Component structure in the evolution of random hypergraphs
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Every monotone graph property has a sharp threshold
- Inequalities with applications to percolation and reliability
- Influences of variables and threshold intervals under group symmetries
- Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
- On Random 3-sat
- On Russo's approximate zero-one law
- Perfect matchings in random s‐uniform hypergraphs
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Tail bounds for occupancy and the satisfiability threshold conjecture
- Threshold Functions for H-factors
- Threshold functions
Cited in
(only showing first 100 items - show all)- The scaling window of the 2-SAT transition
- Thresholds versus fractional expectation-thresholds
- Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities
- On the concentration of the number of solutions of random satisfiability formulas
- The threshold for integer homology in random \(d\)-complexes
- GD-SAT model and crossover line
- The unsatisfiability threshold revisited
- Computational approaches to finding and measuring inconsistency in arbitrary knowledge bases
- Super solutions of random \((3 + p)\)-SAT
- A hierarchy of randomness for graphs
- A sharp threshold for a random constraint satisfaction problem
- Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP
- Graph bootstrap percolation
- Storage capacity in symmetric binary perceptrons
- Pairs of SAT-assignments in random Boolean formulæ
- The state of SAT
- On sharp thresholds in random geometric graphs
- Instability, complexity, and evolution
- Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
- Typical case complexity of satisfiability algorithms and the threshold phenomenon
- Bounds on the satisfiability threshold for power law distributed random SAT
- Combinatorial theorems in sparse random sets
- The Complexity of Propositional Proofs
- Phase transition of multivariate polynomial systems
- On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
- A structure theorem for Boolean functions with small total influences
- Solving non-uniform planted and filtered random SAT formulas greedily
- Exploring the sharp propagation connectivity threshold in hypergraphs
- The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
- On the satisfiability threshold of formulas with three literals per clause
- On smoothed analysis in dense graphs and formulas
- scientific article; zbMATH DE number 1984544 (Why is no real title available?)
- Connectivity and equilibrium in random games
- Continuous phase transitions on Galton–Watson trees
- Boolean functions: influence, threshold and noise
- Phase transitions in discrete structures
- Sharp threshold rates for random codes
- Random 2-XORSAT at the Satisfiability Threshold
- Space proof complexity for random 3-CNFs
- Clique percolation
- The property of having a k-regular subgraph has a sharp threshold
- An efficient local search method for random 3-satisfiability
- On threshold properties of k-SAT: An additive viewpoint
- Analytic description of the phase transition of inhomogeneous multigraphs
- Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
- Phase transitions in discrete structures
- Optimal flow through the disordered lattice
- Sharp thresholds for constraint satisfaction problems and homomorphisms
- Hunting for sharp thresholds
- Branching process approach for 2-SAT thresholds
- Random sum-free subsets of abelian groups
- Lower bounds for k-DNF resolution on random 3-CNFs
- A sharp threshold for van der Waerden's theorem in random subsets
- Proof of a hypercontractive estimate via entropy
- Monotone properties of random geometric graphs have sharp thresholds
- Random k-SAT and the power of two choices
- Topological transition in disordered planar matching: combinatorial arcs expansion
- The large deviations of the whitening process in random constraint satisfaction problems
- Upper bounds on the satisfiability threshold
- Constructing concrete hard instances of the maximum independent set problem
- Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs
- Hypercontractivity for global functions and sharp thresholds
- Between 2- and 3-colorability
- Noise sensitivity of Boolean functions and applications to percolation
- Gibbs states and the set of solutions of random constraint satisfaction problems
- A new upper bound for random (2 + p)-SAT by flipping two variables
- On the structure of subsets of the discrete cube with small edge boundary
- On the threshold for rainbow connection number \(r\) in random graphs
- A threshold for the maker-breaker clique game
- Hypercontractivity via tensor calculus
- Noise stability of functions with low influences: invariance and optimality
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- A stability result for the cube edge isoperimetric inequality
- Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
- Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
- Sharp thresholds for Ramsey properties
- Threshold for Steiner triple systems
- Turánnical hypergraphs
- The Normalized Autocorrelation Length of Random Max $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
- The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
- A proof of the Kahn–Kalai conjecture
- An algorithm for random signed 3-SAT with intervals
- Colorings of partial Steiner systems and their applications
- Critical window of the symmetric perceptron
- Hypercontractivity on the symmetric group
- Random subcube intersection graphs. I: Cliques and covering
- Random \(\mathbb{Z}^d\)-shifts of finite type
- Around two theorems and a lemma by Lucio Russo
- Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances
- Rigorous results for random (2+p)-SAT
- Results related to threshold phenomena research in satisfiability: Lower bounds
- The threshold for the square of a Hamilton cycle
- Sharp thresholds for certain Ramsey properties of random graphs
- A general model and thresholds for random constraint satisfaction problems
- Towards a proof of the Fourier-entropy conjecture?
- A lower bound for the 4-satisfiability threshold
- Length of prime implicants and number of solutions of random CNF formulae
- A Sharp Threshold for Network Reliability
- On the random satisfiable process
- Another look at the phenomenon of phase transition
This page was built for publication: Sharp thresholds of graph properties, and the $k$-sat problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4257709)
