TU Dresden to Present Three Outstanding Papers at FOCS 2026

The TUD Dresden University of Technology was represented at FOCS 2026, held in New York from November 8 to 11, with three research papers. The IEEE Symposium on Foundations of Computer Science (FOCS) is regarded worldwide as one of the most important conferences in theoretical computer science. FOCS sets the standard, particularly in the fields of algorithms and complexity. A publication there is considered one of the most prestigious honors for researchers in this field.

This year, only four German universities were represented at the conference with a total of nine papers—three of which came from TU Dresden. Researchers from the fields of algorithms, algebra, and logic participated:

- Justin Dallant and László Kozma: “Improved space-time tradeoff for TSP via extremal set
  systems”
- Daniel Neuen and co-authors: “Can We Break Fine-Grained and NP-Hardness Barriers if      
  We’ve Seen the Graph Before? The Isomorphic-Priors Model”
- Andrew Moorhead and Manuel Bodirsky: “Conservative Maltsev Constraint Satisfaction
  Problems”

The first paper was presented by Justin Dallant, a postdoctoral researcher at the Chair of Algorithmics. It addresses the Traveling Salesperson Problem (TSP). The TSP involves determining the shortest possible round trip for a given number of locations. The TSP is one of the best-known and most difficult problems in computer science. It plays a central role not only in theoretical research but is also relevant for practical applications—such as planning delivery and transportation routes, in logistics, or in production planning.
The work by Dallant and Kozma investigates how much computation time and how much memory an algorithm requires to solve the TSP. Both resources are crucial for the capabilities of algorithms. The paper identifies a new relationship between these two quantities and enables a particularly balanced trade-off between them. The result is achieved through a new connection to “extremal combinatorics.”

The second paper, by Daniel Neuen and his co-authors, examines what happens when algorithms already possess relevant prior knowledge. The focus here is on the so-called “Isomorphic Priors Model.” It aims to create a general framework for systematically analyzing how much computation time can be reduced when the structure of the data is already known in advance. A clear example would be a transportation network. Suppose the basic layout of the roads is already known. The specific locations or names may differ, but the connections follow the same pattern. An algorithm could use this knowledge to process new tasks—such as those involving reachability or optimal routing—more quickly.

The paper by Andrew Moorhead and Manuel Bodirsky deals with so-called conservative Maltsev constraint satisfaction problems. Many problems in computer science can be reduced to a simple question: Is there a suitable solution that satisfies a set of conditions simultaneously? For example, when creating class schedules, assigning locations, or linking data in a way that adheres to specific rules, this constitutes a so-called Constraint Satisfaction Problem, or CSP for short. In a CSP, there are variables, possible values, and relationships between these values. The goal is to find an arrangement that satisfies all the given constraints.

What all three papers have in common is that they ask fundamental questions: How can resources such as time and memory be used optimally? What information can algorithms utilize? And what structural properties determine whether a problem can be solved efficiently?

“FOCS is an important gathering for global research on the fundamentals of computer science,” says Justin Dallant. “The three papers demonstrate the diversity of theoretical computer science at TU Dresden.”

The conference is also noteworthy for another reason: it may be the last major event at which the vast majority of results were achieved without the use of AI support. As generative AI tools have improved significantly in recent months, research in theoretical computer science and mathematics is currently undergoing dramatic changes. The number of submissions for the next major conference, STOC 2027, has already more than doubled, with a significant portion of the results attributed to AI support.