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
- 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
- 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?)
- 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
- Threshold Functions for H-factors
Cited in
(only showing first 100 items - show all)- The SAT-UNSAT transition for random constraint satisfaction problems
- Instability, complexity, and evolution
- When does the giant component bring unsatisfiability?
- Length of prime implicants and number of solutions of random CNF formulae
- Generalized satisfiability problems: Minimal elements and phase transitions.
- Weak lumpability in the \(k\)-SAT problem
- Boolean functions: influence, threshold and noise
- Phase transitions in discrete structures
- Around two theorems and a lemma by Lucio Russo
- A stability result for the cube edge isoperimetric inequality
- The junta method in extremal hypergraph theory and Chvátal's conjecture
- Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome?
- On a biased edge isoperimetric inequality for the discrete cube
- Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances
- Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT
- On the distribution of the Fourier spectrum of Boolean functions
- A sharp threshold for a random constraint satisfaction problem
- A sharp threshold in proof complexity yields lower bounds for satisfiability search
- Thresholds versus fractional expectation-thresholds
- Space proof complexity for random 3-CNFs
- Random sum-free subsets of abelian groups
- Probabilistic characterization of random Max r-Sat
- Sharp threshold for the Ising perceptron model
- Belief propagation on the random \(k\)-SAT model
- Using the method of conditional expectations to supply an improved starting point for CCLS
- Concentration on the Boolean hypercube via pathwise stochastic analysis
- Solving non-uniform planted and filtered random SAT formulas greedily
- Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP
- Proof of the satisfiability conjecture for large \(k\)
- Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities
- Towards a proof of the Fourier-entropy conjecture?
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- On the satisfiability threshold of formulas with three literals per clause
- Destruction of dissipative structures under random actions
- Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
- Super solutions of random \((3 + p)\)-SAT
- The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
- Analytic description of the phase transition of inhomogeneous multigraphs
- Waiter-client and client-waiter Hamiltonicity games on random graphs
- The threshold for integer homology in random \(d\)-complexes
- Many hard examples in exact phase transitions
- Optimal flow through the disordered lattice
- Phase transition in a random NK landscape model
- On the freezing of variables in random constraint satisfaction problems
- Pairs of SAT-assignments in random Boolean formulæ
- Monotone properties of random geometric graphs have sharp thresholds
- Colorings of partial Steiner systems and their applications
- The structure of the set of satisfying assignments for a random \(k\)-CNF
- A hierarchy of randomness for graphs
- A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
- Typical case complexity of satisfiability algorithms and the threshold phenomenon
- Threshold properties of random Boolean constraint satisfaction problems
- An algorithm for random signed 3-SAT with intervals
- The state of SAT
- The unsatisfiability threshold revisited
- CHAMP: a multipass algorithm for Max Sat based on saver variables
- Phase transition of degeneracy in minor-closed families
- Go-MOCE: greedy order method of conditional expectations for Max Sat
- Hypercontractivity via tensor calculus
- The scaling window of the 2-SAT transition
- The unsatisfiability threshold revisited
- On topological minors in random simplicial complexes
- The typical structure of sparse \(K_{r+1}\)-free graphs
- Phase transitions in discrete structures
- The Normalized Autocorrelation Length of Random Max $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
- A sharp threshold for van der Waerden's theorem in random subsets
- The property of having a k-regular subgraph has a sharp threshold
- Delaying satisfiability for random 2SAT
- On the rank of higher inclusion matrices
- A threshold for the maker-breaker clique game
- On the concentration of the number of solutions of random satisfiability formulas
- On sharp thresholds in random geometric graphs
- HOW SMART DOES AN AGENT NEED TO BE?
- Clique percolation
- Phase transitions of EXPSPACE-complete problems
- Random subcube intersection graphs. I: Cliques and covering
- Graph bootstrap percolation
- TRANSITIONS TO INTERMITTENCY AND COLLECTIVE BEHAVIOR IN RANDOMLY COUPLED MAP NETWORKS
- Random \(\mathbb{Z}^d\)-shifts of finite type
- 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
- On Random Ordering Constraints
- On smoothed analysis in dense graphs and formulas
- Recognizing more random unsatisfiable 3-SAT instances efficiently
- Selecting Complementary Pairs of Literals
- An efficient local search method for random 3-satisfiability
- Random instances of problems in NP -- algorithms and statistical physics
- Running Time Predictions for Factoring Algorithms
- Combinatorial theorems in sparse random sets
- On the random satisfiable process
- Decision Trees and Influences of Variables Over Product Probability Spaces
- A general model and thresholds for random constraint satisfaction problems
- Sharp thresholds for constraint satisfaction problems and homomorphisms
- Phase transition of multivariate polynomial systems
- Combinatorial Problems for Horn Clauses
- Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
- Lower bounds for k-DNF resolution on random 3-CNFs
- On sharp transitions in making squares
- scientific article; zbMATH DE number 1984544 (Why is no real title available?)
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)
