Algorithms and Theory

Researchers

Current Researchers

Sabbaticals & Visiting Faculty (Long-term and Frequent Visitors)

Visitors (37)
  • Prof. Slobodan Mitrovic, UC Davis (2026, 2025)
  • Prof. Harald Raecke, Technical University of Munich
  • Prof. Venkat Guruswami, Simons Institute and University of California, Berkeley
  • Prof. Adi Shamir, Weizmann Institute for Science
  • Prof. Christoph Lenzen, CISPA
  • Prof. Ohad Trabelsi, University of Haifa
  • Prof. Gregory Schwarzman, Japan Institute of Science and Technology (JAIST)
  • Prof. Jakub Radoszewski, University of Warsaw
  • Christoph Grunau, Postdoc, ETH Zurich
  • Sorrachai Yingchareonthawornchai, Postdoc, ETH Zurich
  • Ce Jin, Postdoc, University of California, Berkeley
  • Itai Boneh, Postdoc, Reichman University and University of Haifa
  • Christian Lebeda, Postdoc, University of Montpellier
  • Jacob Imola, Postdoc, University of Copenhagen
  • Jad Silbak, Postdoc, Northeastern University Boston
  • Antti Roeyskoe, PhD student, ETH Zurich
  • Richard Hladik, PhD student, ETH Zurich
  • Wen-Horng Sheu, PhD student, UC Davis
  • Srikkanth Ramachandran, PhD student, UC Davis
  • Benyu Wang, PhD student, University of Michigan
  • Yaowei Long, PhD student, University of Michigan
  • Mursalin Habib, PhD student, Rutgers University
  • Adarsh Srinivasan, PhD student, Rutgers University
  • Zohar Barak, PhD student, Tel Aviv University
  • Anton Paramonov, PhD student, ETH Zurich
  • Shengzhe Wang, PhD student, ETH Zurich
  • Zhongtian He, PhD student, ETH Zurich
  • Thiago Bergamaschi, PhD student, University of California, Berkeley
  • Yonggang Jiang, PhD student, MPII
  • Petr Chmel, PhD student, Charles University Prague
  • Ron Safier, PhD student, Weizmann Institute for Science
  • Omri Shmueli, PhD student, Tel Aviv University
  • Tomas Domes, PhD student, Charles University Prague
  • Nathan Wallheimer, PhD student, Weizmann Institute for Science
  • Lukas Retschmeier, PhD student, University of Copenhagen
  • Egor Gorbachev, PhD student, University of Saarland
  • Ondrej Sladky, Master’s student, ETH Zurich
Alumni (7)
  • Amir Abboud — Weizmann Institute for Science
  • Václav Rozhoň — now Faculty at Charles University, Prague
  • Jakub Tětek — now CTO at Stealth Start-up
  • Seri Khoury — now Co-Founder at Stealth Start-up
  • Nick Fischer — now Group Leader at MPII
  • Tomasz Kociumaka — now Group Leader at MPII
  • Shyan Akmal — now Postdoc at MPII
We are hiring!

We invite excellent faculty applicants of all ranks. This includes tenure-track faculty, as well as tenured faculty who are excited to co-lead, shape and grow the newly established Theory@INSAIT group.

Open the INSAIT application page

QR code placeholder

Publications since 2025 (39)

Open Publication List

All Theory Publications since 2025

2026

  • Tree-Like Shortcuttings of Trees
    Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than
    SoCG 2026: International Symposium on Computational Geometry
  • Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity
    Sujoy Bhore, Sandor Kisfaludi-Bak, Lazar Milenkovic, Csaba D. Toth, Karol Wegrzycki, Sampson Wong
    SoCG 2026: International Symposium on Computational Geometry
  • Reviving Thorup’s Shortcut Conjecture
    Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, Leon Schiller
    STOC 2026: ACM Symposium on Theory of Computing
  • Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
    Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
    STOC 2026: ACM Symposium on Theory of Computing
  • A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
    Bernhard Haeupler, Yaowei Long, Antti Roeyskoe, Thatchaphol Saranurak
    STOC 2026: ACM Symposium on Theory of Computing
  • DAG Projections: Reducing Distance and Flow Problems to DAGs
    Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
    STOC 2026: ACM Symposium on Theory of Computing
  • Breaking Barriers for Distributed MIS by Faster Degree Reduction
    Seri Khoury, Aaron Schild
    STOC 2026: ACM Symposium on Theory of Computing
  • White-Box Adversarial Streaming Lower Bounds beyond Two-Party Communication
    Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
    ICALP 2026: EATCS International Colloquium on Automata, Languages, and Programming
  • Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
    Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Mursalin Habib, Bernhard Haeupler, Karthik C. S., Michal Koucký
    ICALP 2026: EATCS International Colloquium on Automata, Languages, and Programming
  • Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
    Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Mursalin Habib, Bernhard Haeupler, Karthik C. S., Michal Koucký
    ICALP 2026: EATCS International Colloquium on Automata, Languages, and Programming
  • Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs
    Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
    ITCS 2026: Innovations in Theoretical Computer Science Conference
  • Reducing Shortcut and Hopset Constructions to Shallow Graphs
    Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
    SOSA 2026: SIAM Symposium on Simplicity in Algorithms
  • Simple Length-Constrained Expander Decompositions
    Greg Bodwin, Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan
    SOSA 2026: SIAM Symposium on Simplicity in Algorithms
  • A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
    Amir Abboud, Shyan Akmal, Nick Fischer
    SODA 2026: ACM-SIAM Symposium on Discrete Algorithms

2025

  • Parallel (1+epsilon)-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
    Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang
    FOCS 2025: IEEE Symposium on Foundations of Computer Science
  • Round Elimination via Self Reduction: Closing Gaps for Distributed Maximal Matching
    Seri Khoury, Aaron Schild
    FOCS 2025: IEEE Symposium on Foundations of Computer Science
  • ℓ2/ℓ2 Sparse Recovery via Weighted Hypergraph Peeling
    Nick Fischer, Vasileios Nakos
    FOCS 2025: IEEE Symposium on Foundations of Computer Science
  • All-Pairs Shortest Paths with Few Weights per Node
    Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi
    STOC 2025: ACM Symposium on Theory of Computing
  • On the Hardness Hierarchy for the O(n √log n) Complexity in the Word RAM
    Dominik Kempa, Tomasz Kociumaka
    STOC 2025: ACM Symposium on Theory of Computing
  • Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
    Egor Gorbachev, Tomasz Kociumaka
    STOC 2025: ACM Symposium on Theory of Computing
  • Fast and Simple Sorting Using Partial Information
    Bernhard Haeupler, Richard Hladik, John Iacono, Vaclav Rozhon, Robert Tarjan, Jakub Tetek
    SODA 2025: ACM-SIAM Symposium on Discrete Algorithms
  • A Cut-Matching Game for Constant-Hop Expanders
    Bernhard Haeupler, Jonas Huebotter, Mohsen Ghaffari
    SODA 2025: ACM-SIAM Symposium on Discrete Algorithms
  • New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
    Nick Fischer, Ce Jin, Yinzhan Xu
    SODA 2025: ACM-SIAM Symposium on Discrete Algorithms
  • Sumsets, 3SUM, Subset Sum: Now for Real!
    Nick Fischer
    SODA 2025: ACM-SIAM Symposium on Discrete Algorithms
  • Recognizing Sumsets is NP-Complete
    Amir Abboud, Nick Fischer, Ron Safier, Nathan Wallheimer
    SODA 2025: ACM-SIAM Symposium on Discrete Algorithms
  • Beating Bellman’s Algorithm for Subset Sum
    Karl Bringmann, Nick Fischer, Vasileios Nakos
    SODA 2025: ACM-SIAM Symposium on Discrete Algorithms
  • Near-Optimal Quantum Algorithms for Approximate Pattern Matching
    Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
    SODA 2025: ACM-SIAM Symposium on Discrete Algorithms
  • On Beating 2^n for the Closest Vector Problem
    Amir Abboud, Rajendra Kumar
    SOSA 2025: SIAM Symposium on Simplicity in Algorithms
  • Bidirectional Dijkstra’s Algorithm is Instance-Optimal
    Bernhard Haeupler, Richard Hladík, Vaclav Rozhon, Robert E. Tarjan, Jakub Tětek
    SOSA 2025: SIAM Symposium on Simplicity in Algorithms
  • Testing Identity of Continuous Distributions in Polylogarithmic Space
    Christian Janos Lebeda, Jakub Tetek
    SOSA 2025: SIAM Symposium on Simplicity in Algorithms
  • A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
    Nick Fischer, Bernhard Haeupler, Rustam Latypov, Antti Roeyskoe and Aurelio Sulser
    SOSA 2025: SIAM Symposium on Simplicity in Algorithms
  • On the Randomized Locality of Matching Problems in Regular Graphs
    Seri Khoury, Manish Purohit, Aaron Schild, Joshua Wang
    DISC 2025: International Symposium on Distributed Computing
  • Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
    Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang
    ESA 2025: European Symposium on Algorithms
  • Hardness of Median and Center in the Ulam Metric
    Nick Fischer, Elazar Goldenberg, Mursalin Habib, Karthik C. S
    ESA 2025: European Symposium on Algorithms
  • A Simple Algorithm for Trimmed Multipoint Evaluation
    Nick Fischer, Melvin Kallmayer, Leo Wennmann
    ESA 2025: European Symposium on Algorithms
  • Near-Optimal Directed Low-Diameter Decompositions
    Karl Bringmann, Nick Fischer, Bernhard Haeupler, Rustam Latypov
    ICALP 2025: EATCS International Colloquium on Automata, Languages, and Programming
  • The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
    Nick Fischer, Marvin Künnemann, Mirza Redzic, Julian Stieß
    ICALP 2025: EATCS International Colloquium on Automata, Languages, and Programming
  • Graph Coloring Below Guarantees via Co-Triangle Packing
    Shyan Akmal, Tomohiro Koana
    ISAAC 2025: International Symposium on Algorithms and Computation
  • Faster Edge Coloring by Partition Sieving
    Shyan Akmal, Tomohiro Koana
    STACS 2025: Symposium on Theoretical Aspects of Computer Science
  • A Faster Algorithm for Constrained Correlation Clustering
    Nick Fischer, Evangelos Kipouridis, Jonas Klausen, Mikkel Thorup
    STACS 2025: Symposium on Theoretical Aspects of Computer Science

Research Areas

Graph and Network Optimization Algorithms Efficient algorithms for shortest paths, flows, routing, connectivity, and large-scale graph optimization. Network and Graph Structures Expanders, spanners, sparsifiers, decompositions, and structural tools for understanding complex networks. Beyond-Worst-Case Complexity and Universal Optimality Sharper algorithmic guarantees that explain performance on realistic and instance-specific inputs. Computational Geometry Algorithms for geometric data, spatial structures, shapes, proximity, intersections, and high-dimensional problems. Parallel and Distributed Computing Theory for scalable computation across many processors, machines, or networked nodes. Complexity Theory Fundamental limits of efficient computation, communication, lower bounds, and hardness.

News and Updates

Research Area Details

Graph and Network Optimization Algorithms

Graph and Network Optimization Algorithms illustration

Graph and network optimization algorithms address problems such as finding shortest paths, maximum flows, and minimum spanning trees in networks modeled as graphs. Applications of graph algorithms span routing, scheduling, matching and assignment problems, clustering, and connectivity problems, which are crucial in domains like transportation, communication networks, and logistics. Key challenges include efficiently handling large-scale graphs, managing dynamic updates, and balancing efficiency with accuracy. The techniques used range from combinatorial and continuous optimization to linear programming and approximation algorithms.

INSAIT researchers in this area

  • Bernhard Haeupler
  • Bundit Laekhanukit
  • Zhijun Zhang
  • Lazar Milenkovic

Former researchers and visitors

  • Robert Tarjan
  • Thatchaphol Saranurak
  • Slobodan Mitrovic
  • Václav Rozhoň
  • Nick Fischer
  • Yonggang Jiang
  • Antti Roeyskoe

Selected Publications

  • Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
    Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
    STOC 2026: ACM Symposium on Theory of Computing
  • Dynamic Construction of the Lovász Local Lemma
    Bernhard Haeupler, Slobodan Mitrović, Srikkanth Ramachandran, Wen-Horng Sheu, Robert Tarjan
  • DAG Projections: Reducing Distance and Flow Problems to DAGs
    Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
    STOC 2026: ACM Symposium on Theory of Computing
  • Parallel (1+epsilon)-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
    Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang
    FOCS 2025: IEEE Symposium on Foundations of Computer Science

Network and Graph Structures

Network and Graph Structures illustration

Network and graph structures such as expanders, graph decompositions, spanners, and sparsifiers are powerful tools in computer science and mathematics, used to simplify and analyze complex networks. Expanders are highly connected sparse graphs, important in network optimization algorithms, network design, and derandomization. Spanners and sparsifiers approximate and simplify the structure of a graph while preserving essential properties, aiding, for example, in speeding up algorithms for large-scale networks. The study of network and graph structures has applications in optimization, approximation algorithms, communication networks, and the design and operation of large-scale data centers.

INSAIT researchers in this area

  • Lazar Milenkovic
  • Zhijun Zhang
  • Bundit Laekhanukit
  • Bernhard Haeupler

Former researchers and visitors

  • Thatchaphol Saranurak
  • Yaowei Long
  • Antti Roeyskoe

Selected Publications

  • Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
    Bernhard Haeupler, Antti Roeyskoe, Zhijun Zhang
    ICALP 2026: EATCS International Colloquium on Automata, Languages, and Programming
  • Reviving Thorup's Shortcut Conjecture
    Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, Leon Schiller
    STOC 2026: ACM Symposium on Theory of Computing
  • Polynomial Integrality Gap of Flow LP for Directed Steiner Tree
    Shi Li, Bundit Laekhanukit
    TALG 2025: ACM Transactions on Algorithms
  • A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
    Bernhard Haeupler, Yaowei Long, Antti Roeyskoe, Thatchaphol Saranurak
    STOC 2026: ACM Symposium on Theory of Computing

Beyond-Worst-Case Complexity and Universal Optimality

Beyond-Worst-Case Complexity and Universal Optimality illustration

Beyond-worst-case complexity aims to refine traditional worst-case complexity analyses by considering more realistic settings and inputs. It explores average-case complexity, instance-specific guarantees, smoothed analysis, and parameterized complexity, providing a more nuanced understanding of how fast and well individual computational tasks can be solved. This approach is particularly useful for explaining the practical efficiency of algorithms that perform well on most inputs, even if their worst-case complexity is high. The framework helps bridge the gap between theoretical bounds and real-world performance.

INSAIT researchers in this area

  • Zhijun Zhang
  • Bernhard Haeupler

Former researchers, visitors, and collaborators

  • Robert Tarjan
  • Václav Rozhoň
  • Jakub Tětek
  • Shyan Akmal
  • Richard Hladík

Selected Publications

  • Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
    Bernhard Haeupler, Richard Hladik, Vaclav Rozhon, Robert Tarjan, Jakub Tetek
    FOCS 2024: IEEE Symposium on Foundations of Computer Science
    FOCS'24 Best Paper Award
  • Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs
    Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
    ITCS 2026: Innovations in Theoretical Computer Science Conference
  • Near-Universally-Optimal Differentially Private Minimum Spanning Trees
    Richard Hladík, Jakub Tětek
    FORC 2026: Symposium on Foundations of Responsible Computing
    Best Student Paper Award
  • Fast and Simple Sorting Using Partial Information
    Bernhard Haeupler, Richard Hladík, John Iacono, Vaclav Rozhon, Robert Tarjan, Jakub Tětek
    SODA 2025: ACM-SIAM Symposium on Discrete Algorithms

Computational Geometry

Computational Geometry illustration

Computational geometry studies algorithms for processing and analyzing geometric data, including points, lines, polygons, meshes, and higher-dimensional shapes. It addresses fundamental problems such as nearest-neighbor search, convex hulls, geometric intersection detection, motion planning, and spatial partitioning, with applications in computer graphics, robotics, computer vision, geographic information systems, CAD, and scientific computing. Key challenges in the field include handling high-dimensional data, designing algorithms that are both theoretically efficient and robust to noise and numerical imprecision, and scaling to massive geometric datasets. By combining combinatorial insight with algebraic and geometric techniques, computational geometry provides essential tools for reasoning about space, shape, and structure in modern computational systems.

INSAIT researchers in this area

  • Lazar Milenkovic

Selected Publications

  • Tree-Like Shortcuttings of Trees
    Hung Le, Lazar Milenković, Shay Solomon, Cuong Than
    SoCG 2026: International Symposium on Computational Geometry
  • Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity
    Sujoy Bhore, Sándor Kisfaludi-Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, Sampson Wong
    SoCG 2026: International Symposium on Computational Geometry

Parallel and Distributed Computing

Parallel and Distributed Computing illustration

The theory of distributed computing explores how multiple computing entities, or nodes, collaborate to solve problems, often in an asynchronous, unreliable, or adversarial environment. It addresses key questions about coordination, communication, and symmetry breaking, while considering constraints like limited memory and communication, distributed storage of data, communication bottlenecks, and the role of randomization. This field plays a vital role in designing systems that are scalable, robust, and efficient, such as cloud infrastructure, computations in large data centers or distributed settings like blockchains.

Parallel algorithms are designed to exploit multiple processors or cores to solve problems faster by dividing tasks into independent subtasks. Theoretical research in this area involves creating algorithms that minimize communication, synchronization, and redundant work while maximizing parallel efficiency. It considers computational models like PRAM, Parallel Random Access Machine, and MPC, Massively Parallel Computations, and focuses on problems like connectivity, transitive closure, parallel shortest paths computations, clusterings, and graph traversal. Parallelism is crucial for handling big data in modern systems.

INSAIT researchers in this area

  • Bernhard Haeupler
  • Lazar Milenkovic
  • Zhijun Zhang

Former researchers and visitors

  • Seri Khoury
  • Václav Rozhoň
  • Nick Fischer
  • Yaowei Long

Selected Publications

  • Breaking Barriers for Distributed MIS by Faster Degree Reduction
    Seri Khoury, Aaron Schild
    STOC 2026: ACM Symposium on Theory of Computing
  • A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
    Nick Fischer, Bernhard Haeupler, Rustam Latypov, Antti Roeyskoe and Aurelio Sulser
    SOSA 2025: SIAM Symposium on Simplicity in Algorithms
  • Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
    Seri Khoury, Aaron Schild
    FOCS 2025: IEEE Symposium on Foundations of Computer Science

Complexity Theory

Complexity Theory illustration

Computational complexity and communication complexity study the fundamental limits of efficient computation. Computational complexity focuses on classifying problems according to the resources—such as time, memory, or randomness—required to solve them, and seeks to understand which problems can be solved efficiently and which are inherently hard. Communication complexity, on the other hand, examines the amount of information exchange needed between multiple parties to jointly compute a function when the input is distributed among them. Together, these areas provide powerful frameworks for proving lower bounds, guiding algorithm design, and understanding the intrinsic difficulty of problems across computer science, with applications ranging from data structures and streaming algorithms to distributed computing, cryptography, and optimization.

INSAIT researchers in this area

  • Zhijun Zhang
  • Bundit Laekhanukit

Former researchers and visitors

  • Karthik C.S.
  • Shyan Akmal
  • Mursalin Habib

Selected Publications

  • White-Box Adversarial Streaming Lower Bounds beyond Two-Party Communication
    Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
    ICALP 2026: EATCS International Colloquium on Automata, Languages, and Programming
  • Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
    Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Mursalin Habib, Bernhard Haeupler, Karthik C. S., Michal Koucký
    ICALP 2026: EATCS International Colloquium on Automata, Languages, and Programming
  • Graph Coloring Below Guarantees via Co-Triangle Packing
    Shyan Akmal, Tomohiro Koana
    ISAAC 2025: International Symposium on Algorithms and Computation
  • Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
    Bernhard Haeupler, Antti Roeyskoe, Zhijun Zhang
    ICALP 2026: EATCS International Colloquium on Automata, Languages, and Programming