Utilizing Structure in Combinatorial Solving and Reasoning

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


Duration: 39:38
768 views
25

Markus Hecher (MIT)
https://simons.berkeley.edu/talks/markus-hecher-mit-2023-10-20
Probabilistic Circuits and Logic

In this talk we show how to efficiently utilize structure for combinatorial problem solving. We mainly focus on the prominent measure treewidth and the answer set programming framework, thereby establishing tight runtime upper and lower bounds for treewidth, under reasonable assumptions in complexity theory. These bounds will be presented in the context of decomposition-guided reductions, which are polynomial-time reductions that are guided along a specific structural representation, i.e., a tree decomposition, of the instance. In the course of this talk we also show empirical results in order to underline the role of structure in solving computationally hard reasoning modes like counting.



Other Videos By Simons Institute for the Theory of Computing


2023-10-28Matching and Disclosure
2023-10-27Simple Proofs of Important Results in Market Design
2023-10-27Stable Matching by Optimal Transport
2023-10-27Revealed Preferences of One-Sided Matching
2023-10-27Strict Core Stability and Strategy-Proofness for Hedonic Games with Friend-Oriented Preferences
2023-10-27Market Design for Priority-Based Assignment with Distributional Objectives
2023-10-27Estimating Separable Matching Models
2023-10-27The Intractability of Hylland-Zeckhauser and its Aftermath
2023-10-27Endogenous Market Formation: Theory and Evidence from Chilean College Admissions
2023-10-26Algorithmic Mechanism Design with Investment
2023-10-20Utilizing Structure in Combinatorial Solving and Reasoning
2023-10-20Approximating the TV Distance Between Two Product Distributions
2023-10-20Tractable Control for Autoregressive Language Generation
2023-10-20On Finding Modes of Gaussian Sum-Product Networks
2023-10-20Marginal Determinism in Structured Decomposable Circuits
2023-10-19Weighted Model Integration
2023-10-19An Approximate Skolem Function Counter
2023-10-19Subtractive Mixture Models: Representation and Learning
2023-10-19The Rise of Tractable Circuits: From Cryptography to Continuous Generative Models
2023-10-19Decision Diagrams for Efficient Inference and Optimization in Expressive Discrete+Continuous Domains
2023-10-18Solving Marginal MAP Exactly by Probabilistic Circuit Transformations


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Probabilistic Circuits and Logic
Markus Hecher