Venkatesan Guruswami (University of California, Berkeley)
Biography
Venkatesan Guruswami is a Professor of Computer Science and Mathematics at UC Berkeley and senior scientist at the Simons Institute for the Theory of Computing. Venkat received his Bachelor's degree from the Indian Institute of Technology, Madras, and his Ph.D. from MIT.
Venkat's research interests include coding theory, constraint satisfaction, approximate optimization, and computational complexity. He is the Editor-in-Chief of JACM, and was previously president of the Computational Complexity Foundation. Venkat is a recipient of the Presburger Award, a Simons Investigator award, Guggenheim, Packard and Sloan Fellowships, the ACM Doctoral Dissertation Award, and a distinguished alumnus award from IIT Madras. He is a fellow of the ACM, IEEE, and AMS.
Title
When and Why do Efficient Algorithms Exist (for Constraint Satisfaction and Beyond)?
Abstract
Computational problems exhibit a diverse range of behaviors in terms of how quickly and effectively they can be solved. What underlying mathematical structure (or lack thereof) in a computational problem leads to an efficient algorithm for solving it (or dictates its intractability)? Given the vast landscape of problems and algorithmic approaches, it would be too much to hope for a universal theory explaining the underpinnings of easiness/hardness. Yet, in the realm of constraint satisfaction problems (CSP), the algebraic dichotomy theorem gives a definitive answer: a polynomial time algorithm exists when there are non-trivial local operations called polymorphisms under which the solution space is closed; otherwise the problem is NP-complete.
Inspired by this, one might speculate a polymorphic principle in more general contexts, with appropriate notions of symmetries governing the existence of efficient algorithms. Beginning with some background on CSP and the polymorphic approach to understand their complexity, the talk will discuss some extensions beyond CSP where the polymorphic principle seems promising (yet far from understood). In particular, we will discuss “promise CSP' where one is allowed to satisfy a relaxed version of the constraints, a framework that includes problems such as approximate graph coloring. We will provide glimpses of the emerging theory characterizing the (in)tractability of interesting classes of promise CSP, touch upon connections to optimization (linear and affine relaxations), and highlight some of the many challenges that remain.
Ken-ichi Kawarabayashi (National Institute of Informatics, Japan)
Biography
Ken-ichi Kawarabayashi has been a professor at the National Institute of Informatics since 2009 and became a professor at the University of Tokyo in 2022. From 2019 to 2021, he also served as the deputy director general of the National Institute of Informatics. His research interests include graph theory, combinatorics, scalable algorithms, combinatorial optimization, and their application to machine learning, as well as the theoretical analysis of deep learning. In addition to his academic roles, Ken-ichi serves as an editor for Algorithmica, Journal of Graph Theory, Graphs and Combinatorics, TheoriTCS, and four other prestigious journals. He has been recognized with SODA'13 best paper award, Japan Academy medal in 2013, and the Fulkerson Prize in 2021 for his contributions to the field.
Title
Three-edge-coloring cubic graphs on surfaces of low genus
Abstract
It is well-known that every bridgeless planar cubic graph admits a three-edge coloring. Indeed, it has been known since 1890 that this is equivalent to the four color theorem.
Our recent work extended this result to graphs on the projective plane and the torus. On the projective plane there is, essentially, a single exception of the Petersen graph, while on the torus one obtains an infinite collection of "Petersen-like" exceptions. As a corollary, we obtain a strengthening of the well-known Grunbaum's conjecture from 1968 that every cubic graph with a polyhedral embedding in the torus is 3-edge-colorable.
We report more progress on this line of work.
Daniel Lokshtanov (University of California, Santa Barbara)
Biography
Daniel Lokshtanov is a Professor of Computer Science at UCSB, and a Visiting Professor at the University of Bergen. He received his PhD in Computer Science (2009), from the University of Bergen. Lokshtanov spent two years (2010-2012) as a Simons Postdoctoral Fellow at University of California at San Diego. His main research interests are in graph algorithms, parameterized algorithms and complexity. He is a recipient of the Meltzer prize, and a co-author of the Parameterized Algorithms book and the Kernelization book.
Title
Structure and Quasi-Polynomial Time Algorithms
Abstract
A substantial number of prominent computational problems in algorithmic graph theory still resist classification into polynomial time solvable or NP-hard. For example, is the Independent Set problem polynomial time solvable on every hereditary graph class that excludes some path as an induced subgraph? What about the 3-coloring problem on the same classes of graphs? What about Independent Set and Coloring on even-hole-free graphs? While we are still far away from being able to answer these questions, in the past 5 years many of these problems have been shown to admit quasi-polynomial time algorithms. This implies that the problems are very unlikely to be NP-hard. The new quasi-polynomial time algorithms are built on structural insights which are specifically tailored to the design of quasi-polynomial, instead of polynomial time algorithms. In this talk I will survey some of the recent quasi-polynomial time algorithms and the related developments in structural graph theory.