Theory and Foundations News

The workshop Algorithms & Complexity @ Warwick took place at the University of Warwick on September 22-23, 2025 (see https://sites.google.com/view/algorithmscomplexitywarwick2/home for more details).

The aim of the event was to highlight several recent exciting advances in the field of Algorithms and Complexity, to facilitate interactions within the research community, and to provide an excellent opportunity for Theory researchers (including academics, postdocs, and students) to connect and collaborate.

We had a fantastic list of invited speakers by renowned world experts: Albert Atserias (Technical University of Catalonia), Raheleh Jalali (University of Bath), Sanjeev Khanna (University of Pennsylvania), Tomasz Kociumaka (Max Planck Institute for Informatics), Michal Koucký (Charles University in Prague), Or Meir (University of Sheffield and University of Haifa), Rahul Santhanam (University of Oxford), Thomas Sauerwald (University of Cambridge), Roei Tell (University of Toronto).

We are delighted to announce that a result coauthored by Sayan Bhattacharya and Martin Costa (from our Theory and Foundations Research Division), along with Sepehr Assadi (University of Waterloo), Soheil Behnezhad (Northeastern University), Shay Solomon (Tel Aviv University) and Tianyi Zhang (ETH Zurich), has received a best paper award at the upcoming ACM Symposium on Theory of Computing (STOC), 2025. STOC is a flagship international conference in theoretical computer science.

The paper, titled "Vizing's Theorem in Near-Linear Time," tackles a fundamental, textbook edge-coloring problem: Given a graph G with n vertices and m edges, the goal is to assign a color to each edge such that no two edges sharing a common endpoint receive the same color. A classical result by Vizing, dating back to 1960s, proves that any simple graph can always be edge-colored with at most Δ + 1 colors, where Δ is the maximum degree of a vertex. Vizing's original proof is inherently algorithmic and immediately gives an O(mn) time algorithm for computing such a coloring.

This problem has seen a long and influential line of research aimed at designing faster algorithms for this basic task. For over four decades, the best-known runtime was Õ(m√n), a significant barrier that was only broken in 2024 through concurrent, independent works. The recent paper culminates this effort by providing a randomized algorithm that computes a Δ + 1 edge coloring in O(m log Δ) time, a running time that is near-linear in the input size.

A paper co-authored by Matthias C. Caro has been featured on the cover of PRX Quantum. PRX Quantum is a premier journal for quantum information science and technology research. The work was a collaboration with Haimeng Zhao (Caltech & Tsinghua), Laura Lewis (Caltech & Google), Ishaan Kannan (Caltech), Yihui Quek (Harvard & MIT) and Hsin-Yuan Huang (Caltech, Google & MIT).

Characterizing a quantum system by learning its state or unitary evolution is a key tool in developing quantum devices, with applications in practical quantum machine learning, benchmarking, and error mitigation. However, in general, this task requires exponentially many resources. Prior knowledge is required to circumvent this exponential bottleneck. The paper pinpoints the complexity for learning states and unitaries that can be implemented by quantum circuits with a bounded number of gates, a broad setting that is topical for current quantum technologies. When measuring efficiency with respect to the number of accesses to the unknown quantum state or unitary, the paper presents and implements algorithms that are provably optimally efficient. Thereby, this work establishes the equivalence between the complexity of learning quantum states or unitaries and the complexity of creating them. However, it also shows that the data processing necessarily requires exponential computation time under reasonable cryptographic assumptions.