Upcoming Talks
Join our group in order to receive emails with the link for the talks.
Date: Monday, December 13th, 2021 @ 1PM.
Talk Title: Majority-3SAT (and Related Problems) in Polynomial Time
Abstract: Majority-SAT is the problem of determining whether an input n-variable formula in conjunctive normal form (CNF) has at least 2^(n-1) satisfying assignments. Majority-SAT and related problems have been studied extensively in various AI communities interested in the complexity of probabilistic planning and inference. Although Majority-SAT has been known to be PP-complete for over 40 years, the complexity of a natural variant has remained open: Majority-kSAT, where the input CNF formula is restricted to have clause width at most k.
In recent work, joint with Ryan Williams, we prove that for every k, Majority-kSAT is in P. In fact, for any positive integer k and rational ρ in (0,1) with bounded denominator, we present an algorithm which determines whether a given k-CNF has at least ρ2^n satisfying assignments, in deterministic linear time (whereas the previous best-known algorithm ran in exponential time).
In this talk we give an overview of the main ideas behind these algorithms, and highlight the implications for some additional problems related to counting satisfying assignments.
Bio: Shyan Akmal is a PhD student and Siebel scholar studying theoretical computer science at MIT, jointly advised by Virginia Vassilevska Williams and Ryan Williams. He performs research in fine-grained complexity and algorithm design. He is broadly interested in problems with connections to graph theory and combinatorics, and especially enjoys applications of algebraic methods in computer science.
Talk Title: Majority-3SAT (and Related Problems) in Polynomial Time
Abstract: Majority-SAT is the problem of determining whether an input n-variable formula in conjunctive normal form (CNF) has at least 2^(n-1) satisfying assignments. Majority-SAT and related problems have been studied extensively in various AI communities interested in the complexity of probabilistic planning and inference. Although Majority-SAT has been known to be PP-complete for over 40 years, the complexity of a natural variant has remained open: Majority-kSAT, where the input CNF formula is restricted to have clause width at most k.
In recent work, joint with Ryan Williams, we prove that for every k, Majority-kSAT is in P. In fact, for any positive integer k and rational ρ in (0,1) with bounded denominator, we present an algorithm which determines whether a given k-CNF has at least ρ2^n satisfying assignments, in deterministic linear time (whereas the previous best-known algorithm ran in exponential time).
In this talk we give an overview of the main ideas behind these algorithms, and highlight the implications for some additional problems related to counting satisfying assignments.
Bio: Shyan Akmal is a PhD student and Siebel scholar studying theoretical computer science at MIT, jointly advised by Virginia Vassilevska Williams and Ryan Williams. He performs research in fine-grained complexity and algorithm design. He is broadly interested in problems with connections to graph theory and combinatorics, and especially enjoys applications of algebraic methods in computer science.