Certified Static and Dynamic Symmetry Breaking

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=n_JaAPFwjWk


Duration: 31:15
139 views
8

Bart Bogaerts (Vrije Universiteit Brussel (VUB))
https://simons.berkeley.edu/talks/bart-bogaerts-vrije-universiteit-brussel-vub-2023-04-20
Satisfiability: Theory, Practice, and Beyond

Symmetry breaking can be crucial for solving hard combinatorial search and optimisation problems​, but the correctness of these techniques sometimes relies on subtle arguments. For this reason, it is desirable to produce efficient, machine-verifiable certificates that solutions have been computed correctly.
In this talk, I will present our recent work on how to achieve certified static symmetry breaking (i.e., symmetry breaking as a preprocessor), as well as some yet-unpublished work demonstrating that the same techniques also apply to dynamic symmetry breaking, where the sy​mmetries are broken during search.



Other Videos By Simons Institute for the Theory of Computing


2023-04-24Multicalibration and Outcome Indistinguishability I
2023-04-22SAT Beyond Boolean Interpretations
2023-04-22Unification of SAT, Constraint Programming, and Pseudo-Boolean Solving: A Personal Story
2023-04-22Explaining SAT Solving Using Causal Reasoning
2023-04-22Knowledge Compilation for Quantification and Synthesis
2023-04-22Proving UNSAT in Zero Knowledge
2023-04-22Analysis of Core-Guided MaxSat Using Cores and Correction Sets
2023-04-21Homomorphism Counts: Expressive Power and Query Algorithms
2023-04-21Proof Logging for Constraint Programming
2023-04-21Proof Logging for MaxSAT – The Past, The Present and The Future
2023-04-21Certified Static and Dynamic Symmetry Breaking
2023-04-21Trustworthy Automated Reasoning
2023-04-21MCSat Approaches for Solving Non-linear Modular Arithmetic
2023-04-21Reactive Synthesis Empowered by Logical Reasoning
2023-04-20The Power of Extended Resolution: A Practitioner's Perspective
2023-04-20Exploiting Combinatorial Structure in Constraint Programming: ...
2023-04-20Benefits of Abstract Modelling using Conjure
2023-04-20Exact Covering with Colours
2023-04-20Rado numbers: SAT methods and connections to Nullstellensatz complexity
2023-04-20Modern Constraint Programming, For People Who Know SAT
2023-04-20ASP: Theory, Practice, and Beyond


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Satisfiability: Theory Practice and Beyond
Bart Bogaerts