Constrained Optimization Over Semirings

on YouTube ↗29m

" summary

Defines OptConf: given propositional F and semiring K, compute the maximum interpretation value. Proves for Viterbi/tropical semirings the problem sits between FP^{NP[log]} (hardness via reduction from MaxSAT) and FP^{NP} (upper bound via binary search over exponentially many candidate maxima coming from Farey-type fractions). Uses NP oracles / MaxSAT encodings; constructs F' with paired clauses and fresh yi so OptVal = 1/4^{m−r}, linking OptConf to MaxSAT.

AI-written summary · about

" chapters (11)

1. 0:00Introduction and context
2. 0:33Speaker introduction
3. 1:34Problem formulation
4. 3:48Negation and axioms
5. 6:02Complexity analysis
6. 8:23Clarifying semi-ring operators
7. 10:13Upper bound and optimization
8. 15:41Hardness proof
9. 18:56Technical details and gaps
10. 22:21Future directions
11. 26:00Concluding Q&A

" related talks

• 01h 02mAlgebraic Structures in Logic and Query Evaluation 3Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 24mIntroduction to Constraint Logic ProgrammingSergii Dymchenko · LambdaConf 2015
• 18mMaximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear(…)Santosh Nagarakatte, Mridul Aanjaneya · PLDI 2024
• 49mCompiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the CircuitDan Suciu · Probabilistic Circuits and Logic 2023
• 36mOptimizing Relational Programs IIRemy Wang · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 01h 05mAlgebraic Structures in Logic and Query Evaluation 2Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 06mAlgebraic Structures in Logic and Query Evaluation 1Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp
• 18mParikh's Theorem Made SymbolicAnthony W. Lin, Matthew Hague, Artur Jez · POPL 2024