ÌÇÐÄTV

In a recent work, visiting undergraduate student Yahel Manor and ÌÇÐÄTV DCS researchers and addressed a fundamental question relevant to the security of cryptographic protocols.

The symmetry of information principle says that the amount of information that a sequence x of bits reveals about another sequence y is essentially the same in either direction. This is known to hold in an idealised world where computations can take an arbitrarily long time, as demonstrated by A. Kolmogorov and L. Levin in the 1970s. In contrast, modern cryptography is built around deliberate asymmetry—for example, functions of the form y = f(x) that are easy to compute but hard to invert (one-way functions).

The new work shows that, once one moves from the idealised setting of time-unbounded computations to the more realistic world of efficient, randomised computations (algorithms that must run quickly and may use randomness), this symmetry can fail in a strong and unconditional way. In other words, computational constraints can yield information asymmetry. In practical terms, this supports the intuition that information may not be extracted efficiently: knowing y = f(x) may not make x efficiently recoverable to the extent that an (ineffective) symmetry principle would suggest, even when x and y are closely related.

Earlier work formally tied an average-case form of this symmetry failure to the existence of one-way functions, the central primitive in cryptography. By proving new failures of symmetry of information, the authors provide concrete progress towards the computational asymmetry that underpins encryption, digital signatures, and many other cryptographic protocols.

This work will be presented at the 58th Annual ACM Symposium on Theory of Computing (STOC) in June 2026 in Salt Lake City, Utah, USA.

Failure of Symmetry of Information for Randomised Computations
Jinqiao Hu (University of ÌÇÐÄTV); Yahel Manor (University of Haifa); Igor C. Oliveira (University of ÌÇÐÄTV)

The paper describing this research is available .

Many congratulations to for passing his PhD viva, with Prof Long Tran-Thanh (ÌÇÐÄTV) and (Bristol) as examiners. Martin has worked on two different fundamental topics in algorithms - clustering and edge coloring. His work on clustering led to a Google PhD fellowship, and his work on edge coloring (the topic of his ) led to a best paper award at STOC. During his PhD spanning 3 years, Martin published 7 papers in STOC/FOCS/SODA, 2 papers in ICML/NeurIPS, and 1 paper in ICALP. We wish him all the very best for the next stage of his career.

The workshop Algorithms & Complexity @ ÌÇÐÄTV took place at the University of ÌÇÐÄTV 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√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.

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.

We are happy to announce that an academic from our department, , is among the winners of . According to the European Research Council: "These grants, totalling €678 million, aim to support outstanding scientists and scholars as they establish their independent research teams and develop their most promising scientific ideas. The funding is provided through the EU's Horizon Europe programme."

has been awarded a €2million ERC Consolidator grant for a 5-year project entitled "Towards a Dynamic Algorithms Centric Theory of Linear Programming" (DYNALP). The project aims to build a new theory exploring the interplay between two key concepts, Linear Programming and Dynamic Algorithms, which, in turn, will pave the way towards attacking outstanding open questions in the field of Theoretical Computer Science.

In the 2024 round, this was the only project from the United Kingdom that was awarded an ERC Consolidator Grant in Computer Science and Informatics (PE6 panel). The contains more information about the ERC funding programme.

We are delighted to announce that , a PhD student at the Theory and Foundations research division, has received a highly competitive for his work on designing clustering algorithms for dynamic datasets. The Fellowship comes in the form of an unrestricted gift from Google, of 60,000 USD per year, for up to two years. Under the category of "Algorithms and Theory", besides Martin (from University of Cambridge and ETH Zurich) received a Google PhD Fellowship this year. Many congratulations to Martin for this achievement!