SAT Beyond Boolean Interpretations

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


Duration: 18:26
232 views
1

Vinodchandran Variyam (University of Nebraska - Lincoln)
https://simons.berkeley.edu/talks/2023-04-21
Satisfiability: Theory, Practice, and Beyond

Interpretations of logical formulas over semirings, other than the Boolean semiring, have applications in areas such as AI, databases and security. These interpretations offer richer information beyond the simple truth or falsity of statements. In this talk, we will consider the following problem: Given a propositional formula F with n variables, find the maximum value over all possible interpretations of F over a given semiring K. The related search problem is to identify an interpretation that achieves the maximum value. We will explore the complexity of these problems over semirings other than the Boolean semiring.



Other Videos By Simons Institute for the Theory of Computing


2023-04-26Loss Minimization Yields Multicalibration for Large Neural Networks
2023-04-26Measuring Distribution Drift via Multicalibration
2023-04-26Phase Transition in Random Circuit Sampling | Quantum Colloquium
2023-04-26Online Omniprediction
2023-04-26Robust Multivalid Conformal Prediction
2023-04-25Calibration: Unbiased Answers to Arbitrary Questions
2023-04-25Validity of Decision Making Algorithms
2023-04-25Multi-Group Fairness and Loss Minimization
2023-04-25Multicalibration and Outcome Indistinguishability II
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


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