The impact of heterogeneity and geometry on the proof complexity of random satisfiability
From MaRDI portal
Publication:6063345
DOI10.1002/rsa.21168arXiv2004.07319OpenAlexW3117273226MaRDI QIDQ6063345
Thomas Bläsius, Ralf Rothenberger, Tobias Friedrich, Andreas Göbel, Jordi Levy
Publication date: 7 November 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.07319
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of clause-learning SAT solvers as resolution engines
- On the complexity of d-dimensional Voronoi diagrams
- An optimal algorithm for constructing the weighted Voronoi diagram in the plane
- Higher-dimensional Voronoi diagrams in linear expected time
- On levels in arrangements and Voronoi diagrams
- Voronoi diagrams in higher dimensions under certain polyhedral distance functions
- Geometric inhomogeneous random graphs
- Dense point sets have sparse Delaunay triangulations or ``\dots but not too nasty
- Space bounds for resolution
- Connected components in random graphs with given expected degree sequences
- On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
- On Voronoi diagrams in the \(L_p\)-metric in \(\mathbb{R}^D\).
- On the complexity of randomly weighted multiplicative Voronoi diagrams
- On the complexity of higher order abstract Voronoi diagrams
- A multiplicatively-weighted Voronoi diagram approach to logistics districting
- Random 2-SAT with prescribed literal degrees
- Solving vertex cover in polynomial time on hyperbolic random graphs
- On the Hardness of SAT with Community Structure
- The Community Structure of SAT Formulas
- Higher Order City Voronoi Diagrams
- An Output-Sensitive Approach for the L 1/L ∞ k-Nearest-Neighbor Voronoi Diagram
- Impact of Community Structure on SAT Solver Performance
- Many hard examples for resolution
- On k-Nearest Neighbor Voronoi Diagrams in the Plane
- Short proofs are narrow—resolution made simple
- Space complexity of random formulae in resolution
- On the Expected Complexity of Voronoi Diagrams on Terrains
- The diameter of KPKVB random graphs
- Nice point sets can have nasty Delaunay triangulations
- On the Method of Typical Bounded Differences
- The average distances in random graphs with given expected degrees
- A Computing Procedure for Quantification Theory
- Concentration of Measure for the Analysis of Randomized Algorithms
- Satisfiability threshold for power law random 2-SAT in configuration model
- Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
