The shortest path problem is one of the central problems in graph theory and algorithms. In the Replacement Path problem, we are given the source vertex s, the target vertex t, and the shortest path between them. The goal is to compute the cost of replacing each edge in this path - that is, for every edge e on the shortest path, we must find the length of the shortest path from s to t that avoids e. We study this problem from a distributed perspective, where computational power is distributed among the vertices. The algorithm presented will be in the CONGEST model. This talk is based on the work Dipan co-authored with Yi-Jun Chang, Yanyu Chen, Gopinath Misra, Hung Thuan Nguyen, and Bryce Sanchez. This was accepted in PODC 2025. The paper can be found in this link.
In this talk, Dhara will discuss recent progress on the role of classical proofs in quantum complexity theory, with a focus on group-theoretic problems in the black-box model. We resolve two long-standing open questions in this area. First, we demonstrate that the Group Non-Membership problem—known to lie in QMA but not in MA—is, in fact, in QCMA, thereby settling a 2006 conjecture by Aaronson and Kuperberg. This result follows from a more general result that the Group Order Verification problem lies in QCMA ∩ coQCMA, answering an open question posed by Watrous in 2000. Our techniques also give improved quantum upper bounds on the complexity of many other group-theoretical problems, such as group isomorphism in black-box group settings. This talk is based on joint work with François Le Gall and Harumichi Nishimura.
With the recent advent of exploits like Spectre and Meltdown, the mitigation of side-channel attacks has become an important concern for security researchers. In this paper, we focus on timing-based side channels introduced through conditional branching on secret information within programs. We introduce a language that allows a programmer to write conditionals branching on secrets within its syntax, but has a semantics that keeps execution time constant with respect to an adversary under an observationally equivalent memory. We differ from other approaches that use program analysis methods, opting instead to modify the operational semantics to enforce the necessary properties. We formalize the semantics for our language with timing leak mitigations in Rocq (previously, Coq) and prove that these semantics satisfy the property of timing-sensitive non-interference. Since our system describes a mitigation approach for timing leaks in a general high-level imperative language, we believe that our semantics can be used as a basis for compiler construction for other high-level imperative languages that seek to be safe from timing side channels.
Separate from combinatorial games and games on graphs lies the world of modern board-gaming. We are currently witnessing a renaissance of analog games, with hundreds of new titles -- beyond those for children -- published each year. This is a rich mathematical and narrative universe. This survey talk introduces the world of no (or low)-luck modern board games and considers some analytic opportunities these games provide.
An influential result by Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2000) implies an algorithm that can compute approximate shortest paths for all vertex pairs in Õ(n² + O(1/k)) time, ensuring that the output distance is at most twice the actual shortest path, provided the pairs are at least k apart, where k ≥ 2. We present the first improvement on this result in over 25 years. Our algorithm achieves roughly the same Õ(n² + 1/k) runtime but applies to vertex pairs merely O(log k) apart, where log k ≥ 1. When k = log n, the running time of our algorithm is Õ(n²) and it works for all pairs at least O(log log n) apart. Our algorithm is combinatorial, randomized, and returns correct results for all pairs with a high probability. This talk is his latest work that got accepted in FOCS 2025.
We will examine our recent study on the complexity of graph problems on graphs defined over groups, particularly power graphs. In this study, we have observed that an isomorphism invariant problem, such as Hamiltonian Path, Feedback Vertex Set, Partition into Cliques, Subgraph Isomorphism, etc., cannot be NP-complete for power graphs, commuting graphs, enhanced power graphs, directed power graphs, and bounded-degree Cayley graphs, assuming the Exponential Time Hypothesis (ETH). Analogously, no isomorphism-invariant group problem can be NP-complete under ETH. We have shown that the Weighted Max-Cut problem is NP-complete in power graphs. Also, unless ETH is false, the Graph Motif problem cannot be solved in quasi-polynomial time on power graphs, even for power graphs of cyclic groups. Towards the end of the talk, we will briefly discuss the recognition problem of power graphs when the adjacency matrix or list is given as input. We have demonstrated that for abelian groups and certain classes of nilpotent groups, the problem is solvable in polynomial time.