Utilizing Structure in Combinatorial Solving and Reasoning

Explore efficient methods for utilizing structure in combinatorial problem solving in this 40-minute lecture by Markus Hecher from MIT. Focus on the prominent measure of treewidth and the answer set programming framework, examining tight runtime upper and lower bounds for treewidth under reasonable complexity theory assumptions. Delve into decomposition-guided reductions, which are polynomial-time reductions guided by specific structural representations of instances, such as tree decompositions. Gain insights into empirical results that highlight the importance of structure in solving computationally hard reasoning modes like counting. This talk, part of the Probabilistic Circuits and Logic series at the Simons Institute, offers valuable perspectives on advanced problem-solving techniques in combinatorial reasoning.