Constrained Optimization Over Semirings
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore the complexity of constraint optimization problems over semirings in this 29-minute lecture by Kuldeep Meel from the University of Toronto. Delve into the OptConf problem, which involves finding the maximum value of propositional formula interpretations over semirings. Learn about the FP^{NP} complexity class for Viterbi semirings and the FP^{NP[log]} hardness results. Examine similar complexity findings for tropical, fuzzy, and access control semirings. Discover potential opportunities for developing algorithmic procedures leveraging SAT solver capabilities. Gain insights into applications of logical formula interpretations over semirings in logic, AI, databases, and security.
Syllabus
Constrained Optimization Over Semirings
Taught by
Simons Institute
Related Courses
Constrained And Unconstrained OptimizationIndian Institute of Technology, Kharagpur via Swayam Constrained and Unconstrained Optimization
NPTEL via YouTube Physics of Functional Networks - Henrik Ronellenfitsch
Institute for Advanced Study via YouTube Trust Region & Proximal Policy Optimization
Pascal Poupart via YouTube Calculus 3 Lecture - Constrained Optimization with LaGrange Multipliers
Professor Leonard via YouTube