9:15 AM - 10 AM: Morning Tea
10 AM - 10:45 AM: Talk 1
10:45 AM - 10:55 AM: Brief Introduction
10:55 AM - 11:40 AM: Talk 2
12 Noon - 2 PM: Lunch
2 PM - 2:45 PM: Talk 3
2:45 PM - 3:30 PM: Talk 4
3:30 PM - 4 PM: Tea
4 PM onwards: Open problem session
Talk 1: Constant Rate Isometric Embedding of Hamming Metric into Edit Metric
Speaker: Karthik C. S.
A function phi: {0,1}^n -> {0,1}^N is called an isometric embedding from the n-dimensional Hamming metric space to the N-dimensional edit metric space if, for all x, y in {0,1}^n, the Hamming distance between x and y is equal to the edit distance between phi(x) and phi(y). The rate of such an embedding is defined as the ratio n/N. It is well known in the literature how to construct isometric embeddings with a rate of 1/log n. In this talk, I will present an isometric embedding with a rate of 1/8 and mention its consequences to fine-grained complexity.
Talk 2: Polynomial formulations in fine-grained complexity
Speaker: Sasha Golovnev
The field of fine-grained complexity has leveraged the Strong Exponential Time Hypothesis to prove quite tight conditional lower bounds for dozens of problems in various domains and complexity classes, including Edit Distance, Graph Diameter, Hitting Set, Independent Set, and Orthogonal Vectors. Yet, it has been repeatedly asked in the literature whether SETH-hardness results can be proven for other fundamental problems such as Hamiltonian Path, Independent Set, Chromatic Number, MAX-k-SAT, and Set Cover. In this talk, we'll connect these challenges in fine-grained complexity to some of the main open questions in circuit lower bounds.
Talk 3: On Average Baby PIH and Its Applications
Speaker: Xin Zheng
We prove the Average Baby PIH, a weaker variant of PIH, under W[1] ≠ FPT, by a self-reduction for 2CSP instances which transforms gaps for each variable into a gap on average. As an application, we establish for the first time the W[1]-hardness for approximating k-ExactCover.
Talk 4: Statistical inference and (fine-grained) cryptography
Speaker: Andrej Bogdanov
In a statistical inference problem we are given samples from some distribution D with a planted signal. The objective is to recover the signal, or to distinguish D from a null distribution. Many problems of this type exhibit statistical-computational gaps: For a given range of sample complexities the solution is statistically determined, but appears hard to find efficiently. Statistical-computational gaps are sufficient for private-key cryptography. How about more advanced functionalities like collision resistance and public-key encryption? I will talk about some ongoing attempts to answer this question using two incomplete methods for predicting average-case hardness: low-degree analysis and the overlap gap property.
9:15 AM - 10 AM: Morning Tea
10 AM - 10:45 AM: Talk 1
10:45 AM - 11:30 AM: Talk 2
12 Noon - 2 PM: Lunch
2 PM - 2:45 PM: Talk 3
2:45 PM - 3:30 PM: Talk 4
3:30 PM - 4 PM: Tea
4 PM onwards: Open problem session
Talk 1: The Parameterized Complexity of Coordinated Motion Planning
Speaker: Eduard Eiben
In the Coordinated Motion Planning problem, sometimes referred to as Multiagent Pathfinding (MAPF), we are given a graph together with starting positions and destinations of k distinct robots. The goal is to route a set of k robots to their destinations without any collision while minimizing a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. In this talk, we will discuss some parameterized algorithmic results related to the problem and its generalizations.
Talk 2: The Parameterized Complexity of Drawing Extension
Speaker: Robert Ganian
Many different ways of visually representing (i.e., drawing) graphs have been considered in the literature, and the associated problems of computing drawings in the respective styles have been extensively studied. However, in some cases it is either undesirable or infeasible to compute a drawing from scratch - instead, the task is to extend a provided partial drawing of an input graph into a complete one. I will provide an overview of recent parameterized algorithms for extending partial drawings of graphs and discuss the specific challenges and techniques arising in this setting.
Talk 3: 3SUM in Preprocessed Universes: Faster and Simpler
Speaker: Adam Polak
We give an algorithm for the 3SUM problem in the "preprocessed universes" setting running in time O(n^{3/2} log n). While the previous algorithms, running in time O(n^{13/7}) and O(n^{11/6}), are based on the Balog–Szemerédi–Gowers theorem from additive combinatorics, our algorithm uses only standard 3SUM-related techniques, namely FFT and linear hashing modulo a prime – it is therefore not only faster but also simpler. This is joint work with Shashwat Kasliwal and Pratyush Sharma, first presented at SOSA 2025.
Talk 4: Local Enumeration and Majority Lower Bounds
Speaker: Mohit Gurumukhani
We study the problem of enumerating all solutions of a k-CNF of Hamming weight r where we are promised all solutions of k-CNF have Hamming weight at least r. We focus on the case of k = 3 and r = n / 2, and provide near optimal algorithm. We also obtain an optimal algorithm for the special case of enumerating all the not-all-equal solutions of such a 3-CNF. Using this, we obtain near optimal circuit lower bounds for depth 3 circuits with bottom fan in 3 computing the MAJORITY function. Based on joint works with Ramamohan Paturi, Pavel Pudlák, Michael Saks, and Navid Talebanfard.
9:15 AM - 10 AM: Morning Tea
10 AM - 10:45 AM: Talk 1
10:45 AM - 11:30 AM: Talk 2
12 Noon - 2 PM: Lunch
2 PM - 2:45 PM: Talk 3
2:45 PM - 3:30 PM: Talk 4
3:30 PM - 4 PM: Tea
4 PM - 4:45 PM: Talk 5
4:45 PM - 5:30 PM: Talk 6
Talk 1: Introduction to Threshold Graph Composition
Speaker: Bingkai Lin
To prove the inapproximability of a problem, we usually show the hardness of its gap version. A technique for such proof is the Threshold Graph Composition. It combines instances of problem A with graphs having threshold properties to construct equivalent instances of the gap version of problem B. If problem A is hard, this method allows us to prove that approximating problem B is also intractable. In this talk, I will introduce the Threshold Graph Composition method and its applications in proving inapproximability of several fundamental parameterized problems.
Talk 2: A survey on multidimensional packing and covering
Speaker: Arindam Khan
In this talk, we will discuss results related to several multidimensional packing and covering problems such as geometric bin packing, geometric knapsack, maximum independent set in geometric intersection graphs, etc. We will also mention some potential open problems related to parameterized complexity and fine-grained algorithms.
Talk 3: Metric Sketching: Towards Ideal Trades Among Parameters
Speaker: Sujoy Bhore
In many applications—including machine learning, robotics, distributed systems, and network design—the input data can be modeled as points in a finite metric space and is often massive in scale. Efficient processing of such data requires compact representations that preserve essential structural properties. Sketching compresses large datasets into smaller summaries that approximately retain key metric properties. Among the most fundamental sketching structures are spanners and tree covers. This talk will present recent advances in metric sketching, focusing on optimal trade-offs among parameters such as size, weight, degree, and diameter.
Talk 4: Mind the Gap? Not for SVP Hardness under ETH!
Speaker: Rishav Gupta
We show the hardness of constant factor approximation of lattice problems like CVP and SVP under the Exponential Time Hypothesis (ETH) in various \ell_p norms. Precisely, we will show that assuming ETH, there exists a constant f>1, such that no sub exponential algorithm can approximate SVP (in all \ell_p norms, where p>2) and CVP (in all \ell_p norms where p >= 1) to within a factor f (f depends on p). Combining our reductions with ideas from prior work, we also get hardness of BDD assuming ETH, for parameters which were previously known only under Gap-ETH.
Talk 5: Algorithms for Generating Diverse Solutions to SAT
Speaker: Mayank Goswami
For a given k-CNF formula and an integer s, we study algorithms that obtain s solutions to the formula that are as dispersed as possible. This problem has previously been raised in the SAT community and several heuristics have been proposed for it, but no algorithms with theoretical guarantees were known prior to this. Our techniques also extend to finding diverse solutions to NP-complete optimization problems such as Maximum Independent Set, Minimum Vertex Cover, Minimum Hitting Set and Feedback Vertex Set.
Talk 6: Prize-collecting Framework: Classic Problems with Modern Techniques
Speaker: Mohammad Taghi Hajiaghayi
The Prize-collecting Framework encompasses classic optimization problems where multiple demands seek to be served by the lowest-cost structure. If serving some demands proves too costly, they can be declined with a penalty paid instead. Within this framework, our primary focus lies on classic network design problems such as Minimum Spanning Tree, Steiner Tree, TSP, Steiner Forest, and Steiner Networks, among others and present state-of-the-art approximation algorithms for these problems. However, our approach integrates a robust and modern array of techniques ranging from clustering algorithms to recursive methodologies, offering solutions that extend beyond the confines of Prize-collecting Framework. We conclude by presenting very recent best approximation algorithms for Prize-collecting Steiner Forest and Prize-collecting Steiner Tree.encompasses classic optimization problems where multiple demands seek to be served by the lowest-cost structure. If serving some demands proves too costly, they can be declined with a penalty paid instead. Within this framework, our primary focus lies on classic network design problems such as Minimum Spanning Tree, Steiner Tree, TSP, Steiner Forest, and Steiner Networks, among others and present state-of-the-art approximation algorithms for these problems. However, our approach integrates a robust and modern array of techniques ranging from clustering algorithms to recursive methodologies, offering solutions that extend beyond the confines of Prize-collecting Framework. We conclude by presenting very recent best approximation algorithms for Prize-collecting Steiner Forest and Prize-collecting Steiner Tree.
9:15 AM - 10 AM: Morning Tea
10 AM - 10:45 AM: Talk 1
10:45 AM - 11:30 AM: Talk 2
12 Noon - 2 PM: Lunch
2 PM - 2:45 PM: Talk 3
2:45 PM - 3:30 PM: Talk 4
3:30 PM - 4 PM: Tea
4 PM - 4:45 PM: Talk 5
Talk 1: Lattice problems beyond polynomial time
Speaker: Noah Stephens-Davidowitz
We will revisit five different decades-old results that together largely laid the foundations of lattice-based cryptography (and which are conveniently numbered below). These are the celebrated worst-case to average-case reductions for lattice problems due to Ajtai [1996] and Regev [2005]; Ajtai’s NP-hardness result for lattice problems [1998]; and the celebrated proof systems of Goldreich and Goldwasser [1998] and of Aharonov and Regev [2005]. All of these results are about the gap between polynomial time and super polynomial time: relying on polynomial-time reductions and proof systems.
While the distinction between polynomial and super polynomial time is extremely convenient and has proven to be an incredibly fruitful way of thinking about the world, it is also rather arbitrary. We will show that all 5 of the above results are even more interesting if we relax the restriction that reductions and proof systems should run in polynomial time (and we will mention a bonus 6th result that only makes sense in a superpolynomial setting).
Talk 2: Worst case to average case hardness of LWE, a new perspective
Speaker: Divesh Aggarwal
We present a new perspective on the worst-case to average-case hardness of the Learning with Errors (LWE) problem, focusing on the maximum success probability achievable by polynomial-time algorithms. Our approach yields a much tighter reduction from the Bounded Distance Decoding (BDD) problem to LWE, establishing a nearly optimal connection between their hardness. These results advance our understanding of LWE's computational complexity and offer valuable insights into its practical security.
Talk 3: New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
Speaker: Ce Jin
I will discuss several variants of the 3SUM-counting problem, their efficient algorithms (with an emphasis on derandomization), and their applications in conditional lower bounds and pattern matching algorithms.
This talk will be mostly based on a SODA'25 paper joint with Nick Fischer and Yinzhan Xu (full version at https://arxiv.org/abs/2410.20764).
Talk 4: A Fine-Grained Theory for Computing with SAT Solvers: What's the Power of a Satisfying Assignment?
Speaker: Kuldeep S. Meel
The past two decades have witnessed dramatic improvements in SAT solving, enabling today's solvers to handle problems involving millions of variables. Motivated by the power of SAT solvers, there is a growing interest in tackling problems that lie in higher classes of the polynomial hierarchy, wherein NP calls are to be replaced by SAT solvers in practice. Traditional complexity analysis measures such algorithms purely in terms of calls to NP oracles, providing only coarse-grained bounds that fail to capture the nuanced computational landscape. However, SAT solvers are not mere decision oracles: they also provide a satisfying assignment when the formula is satisfiable, offering richer information than standard oracle models account for. This additional structure calls for a fine-grained complexity theory that distinguishes between different types of oracle access and leverages the full computational power that modern SAT solvers provide. In this talk, I will discuss how such fine-grained considerations lead to new algorithms with improved complexity bounds and new conditional lower bounds that reveal fundamental barriers in the context of two fundamental problems: model counting and sampling. Our analysis demonstrates that accounting for the fine-grained structure of SAT solver outputs can yield both algorithmic improvements and deeper complexity-theoretic insights.
Based on joint work (LICS-22 and ICALP-23) with Diptarka Chakaraborty, Sourav Chakraborty, Remi Delannoy, and Gunjan Kumar
Talk 5: The Planted Orthogonal Vectors Problem
Speaker: Adam Polak
We propose a way to plant a solution among vectors with i.i.d. $p$-biased entries, for appropriately chosen $p$, so that the planted solution is the unique one. Our conjecture is that the resulting $k$-OV instances still require time $n^{k-o(1)}$ to solve, on average. Our planted distribution has the property that any subset of strictly less than $k$ vectors has the same marginal distribution as in the model distribution, consisting of i.i.d. $p$-biased random vectors. We use this property to give average-case search-to-decision reductions for $k$-OV.
Joint work with David Kühnemann and Alon Rosen
9:15 AM - 10 AM: Morning Tea
10 AM - 10:45 AM: Talk 1
10:45 AM - 11:30 AM: Talk 2
12 Noon - 2 PM: Lunch
Talk 1: Parameterized approximability of k-median: original and supplier versions
Speaker: Euiwoong Lee
We revisit the classical metric k-median problem from the parameterized approximability perpsective. For the supplier version, where centers can only be open in a separately given candidate set, 1+2/e ~= 1.73 is proved to be the optimal approximation ratio in the parameterized regime. We will discuss recent progress on the less-understood "original" version where a center can be open anywhere in the metric space.
Talk 2: Multivariate Exploration of Metric Dilation
Speaker: Aritra Banik
We study Dilation t-Augmentation, where the objective is, given a metric M, a graph G, and numerical values k and t, to determine whether G can be transformed into a graph with dilation t by adding at most k edges. Our primary focus is on the scenario where the metric M is the shortest path metric of an unweighted graph H. Even in this specific case, Dilation t-Augmentation remains computationally challenging. In particular, the problem is W[2]-hard parameterized by k when H is a complete graph, already for t = 2. Our main contribution lies in providing new insights into the impact of combinations of various parameters on the computational complexity of the problem.
This talk is based on a recent paper accepted to STACS 2025.