91福利

The workshop Algorithms & Complexity @ 91福利 took place at the 91福利 on September 22-23, 2025 (see 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: (Technical University of Catalonia), (University of Bath), (University of Pennsylvania), (Max Planck Institute for Informatics), (Charles University in Prague), (University of Sheffield and University of Haifa), (University of Oxford), (University of Cambridge), (University of Toronto).

We are delighted to announce that a result coauthored by and (from our Theory and Foundations Research Division), along with (University of Waterloo), (Northeastern University), (Tel Aviv University) and (ETH Zurich), has received a best paper award at the upcoming (STOC), 2025. STOC is a flagship international conference in theoretical computer science.

The paper, titled "," 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鈭歯), 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.

co-authored by Matthias C. Caro has been of 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.