Just Beyond P

In this seminar, we will explore algorithmic problems that lie at the edge of our current understanding—problems that admit surprisingly efficient algorithms (e.g., quasipolynomial-time) but for which no polynomial-time solution is known, and no strong hardness evidence rules one out. These are often natural candidates for inclusion in the class NP ∩ coNP or are solvable by randomized algorithms with no known deterministic counterparts.

We will discuss a variety of such problems, including:

• Graph and Tournament Isomorphism: classic problems in NP ∩ co-AM, recently shown to be solvable in quasipolynomial time.
• Energy Games and Infinite Duration Games: fundamental problems lying in NP ∩ coNP, but not known to be in P.
• Min-Sum of Radii Clustering: admits a QPTAS and quasi-polynomial exact algorithms under reasonable assumptions, yet no known PTAS.
• Makespan Scheduling with Precedence Constraints: a well-studied scheduling problem with subtle complexity, lacking strong evidence for hardness or tractability.
• Exact Matching: solvable in randomized parallel polylogarithmic time, but no deterministic polynomial-time algorithm is known, even for bipartite graphs. The problem opens the door to discussions on derandomization and complexity classes like BPP and E.

This seminar will be informal, discussion-driven, and problem-oriented. Each session will spotlight one or two problems, exploring known results, open questions, and why these problems resist classification. Participants are encouraged to bring their own favorite "mysterious" problems to the table.

1. Deciding Parity Games in Quasi-polynomial Time  epubs.siam.org/doi/10.1137/17M1145288
2. A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints  epubs.siam.org/doi/10.1137/1.9781611978322.16
3. Approximation Schemes for Independent Set and Sparse Subsets of Polygons  dl.acm.org/doi/10.1145/3326122
4. A quasi-polynomial algorithm for well-spaced hyperbolic TSP jocg.org/index.php/jocg/article/view/3604
5. A faster deterministic exponential time algorithm for Energy Games and Mean Payoff Games  danidorfman.com/publication/energy-games/energy-games.pdf
6. Universal Algorithms for Parity Games and Nested Fixpoints   https://arxiv.org/pdf/2001.04333v2
7. Parity Games: Another View on Lehtinen’s Algorithm arxiv.org/pdf/1910.03919v1
8. Unique sink orientations of cubes ieeexplore.ieee.org/document/959931
9. A Subexponential Bound for Linear Programming https://people.inf.ethz.ch/emo/PublFiles/SubexLinProg_ALG16_96.pdf
10. A note on the graph isomorphism counting problem www.sciencedirect.com/science/article/abs/pii/0020019079900048
11. Isomorphism of graphs of bounded valence can be tested in polynomial time www.sciencedirect.com/science/article/pii/0022000082900095
12. An optimal lower bound on the number of variables for graph identifications  https://link.springer.com/article/10.1007/BF01305232
13. Random Facet Algorithm  https://people.inf.ethz.ch/gaertner/subdir/texts/own_work/rf.pdf
14. QPTAS for min-sum of radii  https://www.cs.utsa.edu/~gibson/MetricKClustering.pdf
15. New Algorithms for Pigeonhole Equal Subset Sum  https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.86

Each student will choose a research paper from a curated list provided by the organizers. Before presenting in class, students are required to give a practice talk to one of the instructors. The in-class presentation should clearly explain the problem addressed in the paper, outline the main techniques used, and discuss the significance of the results. Each participant must pass at least 80% of the quiz questions after each presentation.