On the hierarchical community structure of practical Boolean formulas

DOI10.1007/978-3-030-80223-3_25OpenAlexW3184756489MaRDI QIDQ2118321

Vijay Ganesh, Jonathan Chung, Marc Vinyals, Antonina Kolokolova, Chun-Xiao Li, Alice Mu, Soham Mukherjee, Noah Fleming

Publication date: 22 March 2022

Full work available at URL: https://arxiv.org/abs/2103.14992

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational aspects of satisfiability (68R07)

Uses Software

• MiniSat
• Saturn
• Graphplan
• Scikit
• CNFgen
• STP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating SAT instances with community structure
• Satisfiability, branch-width and Tseitin tautologies
• Fast planning through planning graph analysis
• Random 3-SAT: The plot thickens
• Generating hard satisfiability problems
• Learning Rate Based Branching Heuristic for SAT Solvers
• On the Hardness of SAT with Community Structure
• The Community Structure of SAT Formulas
• Impact of Community Structure on SAT Solver Performance
• The Fractal Dimension of SAT Formulas
• Expander graphs and their applications
• Short proofs are narrow—resolution made simple
• Fast unfolding of communities in large networks
• Determining computational complexity from characteristic ‘phase transitions’
• The complexity of theorem-proving procedures
• Theory and Applications of Satisfiability Testing
• Computer Aided Verification
• Random forests

This page was built for publication: On the hierarchical community structure of practical Boolean formulas