Doctoral Thesis: Parameterized Relaxations for Circuits and Graphs

By: Shyan Akmal

Supervisor: Virginia Vassilevska Williams & Ryan Williams

Details

• Date: Wednesday, May 8
• Time: 10:00 am - 11:30 am
• Location: 32-G882 (Hewlett Room)

Additional Location Details:

Thesis Committee:
Virginia Vassilevska Williams (Advisor)
Ryan Williams (Advisor)
Ronitt Rubinfeld

Abstract:
What makes some problems hard to solve, and others easy? In situations where complexity-theoretic hypotheses rule out the possibility of fast algorithms for problems, are there nonetheless instances for which we can “evade intractability” and still design efficient algorithms? In this thesis, we investigate these questions from the perspective of parameterized relaxations. We investigate computational problems on circuits and graphs, and design fast algorithms for relaxed versions of these tasks, thereby identifying tractable instances of problems which are provably hard in general. In this talk, we focus on parameterized relaxations for Majority-SAT, a problem on circuits, and All-Pairs Connectivity, a problem on graphs.

Majority-SAT is the problem of determining whether a given n-variable formula has at least 2^{n-1} satisfying assignments. Majority-SAT has been studied extensively in computer science communities interested in the complexity of probabilistic planning and inference. Although this problem has been known to be PP-complete for fifty years, the complexity of a natural variant remained open: Majority-kSAT, where the input is a formula in conjunctive normal form with clause width at most k (i.e., the input is a k-CNF formula). In work with Ryan Williams, we resolve this open problem, and determine the complexity of Majority-kSAT for all constant k.

All-Pairs Connectivity (APC) is the problem of computing the maximum flow from s to t for all pairs of nodes (s,t) in a given unweighted graph. Although APC can be solved in optimal near-quadratic time over undirected graphs, in general directed graphs it is known that APC cannot be solved in truly subcubic time assuming the Strong Exponential Time Hypothesis. Consequently, on directed graphs researchers have studied a variant of APC: k-APC, where we are given a positive integer k, and must return the maximum flow from s to t only for pairs of nodes (s,t) with maximum flow value less than k (i.e., return all “small maximum flow values”). Despite significant research in flow problems, it was an open question to determine whether k-APC could be solved faster than the general APC problem even for k=3. In work with Ce Jin, we resolve this open problem, and determine the optimal time complexity for solving k-APC for all constant k (up to conjectures in fine-grained complexity).