Workshop Details

[Video]

[Video]   [Slides]

Exponential time hypothesis (ETH)--which postulates that no sub-exponential time algorithm can solve 3-SAT--is one of the main assumptions in proving tight running time lower bounds for exponential-time and parameterized algorithms. Gap-ETH is an extension of ETH which roughly asserts that even approximating Max-3-SAT requires exponential time. This stronger assumption helps facilitate the proofs in hardness of approximation results for parameterized algorithms. While some of these results have now been proved under the weaker ETH, others remain known only under Gap-ETH. This talk will discuss Gap-ETH hardness results, especially those that are not yet known under ETH. Finally, we will discuss some problems whose (tight) hardness of approximation results are not even known under Gap-ETH.

[Video]   [Slides]

[Video]   [Slides]

The talk will overview challenges in the fine-grained complexity of approximation in P and what we know about them so far. A large number of conditional lower bounds have been established in the last decade under a small number of core conjectures. Whether similar lower bounds hold for the approximate versions of these problems is often a meaningful open question. It is natural to seek “gap versions” of the core conjectures, as well as “gap amplification” techniques that relate a conjecture to its gap version. The talk will discuss the extent to which this has been accomplished for each conjecture.

[Video]

[Video]   [Slides]

While the area of fine-grained and parameterized complexity has provided a framework for proving computational hardness of many fundamental problems, approximation algorithms in this regime have not been well understood until recent years, principally due to a lack of unified tool for proving hardness of approximation. Distributed PCPs--proposed by Abboud, Rubinstein and Williams (FOCS'17)--is a framework that overcomes such a limitation. This approach allows one to translate certain communication protocols to hardness of approximation results in the fine-grained and parameterized regime. It has been successfully employed to proved hardness of approximation for well-studied problems such as nearest neighbor search (Rubinstein, STOC'18) and k-dominating set (Karthik, Laekhanukit and Manurangsi, STOC'18). This talk will give an overview of this framework, with specific focus on these two results.

[Video]   [Slides]

[Video]   [Karthik's slides]

In the Disjoint Paths problem, one is given a graph with a set of k vertex pairs (s_i,t_i) and the task is to connect each s_i to t_i with a path, so that the k paths are pairwise disjoint. In the optimization variant, Max Disjoint Paths, the goal is to maximize the number of vertex pairs to be connected. We study this problem on acyclic directed graphs, where Disjoint Paths is known to be W[1]-hard when parameterized by k. We show that in this setting Max Disjoint Paths is W[1]-hard to c-approximate for any constant c. To the best of our knowledge, this is the first non-trivial result regarding the parameterized approximation for Max Disjoint Paths with respect to the natural parameter k. Our proof is based on an elementary self-reduction that is guided by a certain combinatorial object constructed by the probabilistic method.

[Video]   [Slides]

The Parameterized Inapproximability Hypothesis (PIH) conjectures that no FPT algorithm can distinguish a satisfiable 2‑variable CSP (2CSP) instance from one in which only a constant fraction of constraints can be satisfied. A minimization analogue introduces r‑list‑satisfiability, where each variable may carry an r‑element list of values and a constraint is deemed satisfied if some choice from the Cartesian product of its two lists meets the allowed pair.

The Baby PIH states that, for every integer r≥1, it is W[1]‑hard to tell a satisfiable 2CSP apart from one that is not even r‑list‑satisfiable. The reduction adapts core combinatorial ideas from the Baby PCP theorem and runs in time polynomial in both variable count and alphabet size, thereby recovering the original Baby PCP as a special case.

Building on this, the Average Baby PIH is shown under the sole assumption W[1]≠FPT. Here, any multi‑assignment that satisfies all constraints must assign on average more than r values per variable, yielding a gap between “exactly one value” versus “average > r values.” A novel FPT self‑reduction amplifies the per‑variable gap of Baby PIH to an average‑value gap.

[Video]   [Slides]

The Parameterized Inapproximability Hypothesis (PIH) posits that no fixed-parameter tractable algorithm can distinguish between a satisfiable CSP and one where every assignment violates an $varepsilon$ fraction of constraints, mirroring the foundational role of the PCP theorem in classical complexity. In this talk, I will present a self-contained and elementary proof of PIH, assuming Exponential Time Hypothesis (ETH). The proof proceeds via a reduction from ETH to an ETH-hard, "vector-structured" CSP, where the constraints can be checked for constant soundness using a new, parallel PCP of proximity based on the Walsh–Hadamard code.

After establishing this framework, I will discuss quantitative refinements: specifically, under the same ETH assumption, we show that even sparse k-variable CSPs are hard to approximate within any constant factor in time $n^{k^{1-o(1)}}$. This result yields broad near-optimal inapproximability consequences across parameterized optimization problems.

[Video]

I discuss the n^2-space lower bound for all-pairs maximum flows in graphs with unit-vertex capacity. I explain the gap amplification idea inside this lower bound.

[Video]   [Slides]

In this talk we consider the classical k-Center problem in undirected graphs: given a graph G, find a set of k vertices that minimizes the biggest distance of a vertex to the set. The problem is known to have a polynomial-time 2-approximation and even (2 + ε)-approximation algorithms for every ε >0 running in near-linear time. The conventional wisdom is that the problem is closed, as a reduction from k-Dominating-Set shows that any (2 − ε)-approximation requires n^{k−o(1)} time.

Our first set of results show that one can beat the multiplicative factor of 2 in undirected unweighted graphs if one is willing to allow additional small additive error, obtaining various (2−ε, O(1)) approximations running in time O(n^{k−δ}) for any k. We will discuss the approach to these algorithms and see that when the k-Center is not a k-Dominating-Set we do in fact obtain a (2-ε)-approximation.

Our second set of results are strong fine-grained lower bounds for k-Center. We use the powerful but underutilized tool of \`gap set cover’ to show that the dependence on k in the exponent in the runtime of our algorithms is necessary, and the approximation ratio 2 cannot be improved by any algorithm whose running time is a polynomial independent of k, even if one allows additive error. 

Based on joint work with Ce Jin, Virginia Vassilevska Williams and Nicole Wein, SODA25.

[Video]   [Slides]