Algorithms and Complexity


Welcome to the website of the Algorithms and Complexity research group at the University of Bristol.

Our Research Interests. Our current research focusses on: Getting involved. We offer BSc/MEng projects for Bristol students (implementation/engineering of algorithms, algorithmic theory) as well as PhD positions in all areas relevant to our research. Students with an interest in algorithmic theory and a solid foundation in mathematics are strongly encouraged to get in touch.


April 2024Paper "Nearly optimal independence oracle algorithms for edge estimation in hypergraphs" (by Holger Dell, John Lapinskas, Kitty Meeks) accepted at ICALP 2024! See here for a pre-print.
February 2024Paper "O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set" (by Sepehr Assadi, Christian Konrad, Kheeran Naidu, Janani Sundaresan) accepted at STOC 2024!
October 2023Paper "An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation" (by Christian Konrad, Kheeran Naidu) accepted at SODA 2024! Kheeran will present the paper at the conference.
September 2023Paper "Interval Selection in Data Streams: Weighted Intervals and the Insertion-deletion Setting" (by Jacques Dark, Adithya Diddapur, Christian Konrad) accepted at FSTTCS 2023! Adi will present the paper at the conference.
May 2023Paper "Graph Ranking and the Cost of Sybil Defense" (by Gwendolyn Farach-Colton, Martin Farach-Colton, Leslie Goldberg, Hanna Komlos, John Lapinskas, Reut Levi, Moti Medina and Miguel Mosteiro) accepted at EC 2023! See here for a pre-print.
March 2023Paper "Set Cover in the One-pass Edge-arrival Streaming Model" (by Sanjeev Khanna, Christian Konrad, and Cezar Alexandru) accepted at PODS 2023!
March 2023Our PhD students Cezar and Kheeran presented the papers Improved Weighted Matching in the Sliding Window Model and Maximum Matching via Maximal Matching Queries at STACS 2023 in Hamburg!


December 2022Two papers "Maximum Matching via Maximal Matching Queries" (by Christian Konrad, Kheeran Naidu and Arun Steward) and Improved Weighted Matching in the Sliding Window Model (by Cezar Alexandru, Pavel Dvorak, Christian Konrad, Kheeran Naidu) accepted at STACS 2023!
October 2022Paper Instability of backoff protocols with arbitrary arrival rates by John Lapinskas (joint work with Leslie Ann Goldberg) accepted at SODA 2023!
October 2022Paper "When you come at the king you best not miss" by Chhaya Trehan (joint work with Oded Lachish and Felix Reidl) accepted at FSTTCS 2022. Congratulations to Chhaya!
September 2022We welcome Research Associate Chhaya Trehan and PhD student Adithiya Diddapur to the group!
June 2022Raphael Clifford received the Best Paper Award at CPM'22 for his paper The Dynamic k-Mismatch Problem (joint work with Pawel Gawrychowski, Tomasz Kociumaka, Daniel Martin, and Przemysław Uznanski), congratulations!
June 2022Congratulations to our PhD student Kheeran Naidu on his student paper "Space Optimal Vertex Cover in Dynamic Streams" accepted at APPROX 2022 (joint work with Vihan Shah, Rutgers University)!
November 2021Paper "Optimal Bounds for Dominating Set in Graph Streams" by Sanjeev Khanna and Christian Konrad accepted at ITCS 2022!
October 2021We welcome our new Research Associate Dr Pavel Dvorak to the group!
September 2021We welcome our new PhD student Cezar Alexandru to the group!
August 2021PhD student Kheeran Naidu presented his recent work at APPROX'21. Check out his presentation here.
July 2021Group webpage goes online!


Core Faculty

Raphaël Clifford

Christian Konrad
(Head of Group)

John Lapinskas
PhD Students

Adithya Diddapur
since 2022
Supervisor: Christian Konrad

Cezar Alexandru
since 2021
Supervisor: Christian Konrad

Kheeran Naidu
since 2020
Supervisor: Christian Konrad
Former Members
Chhaya Trehan (Sept 2022 - January 2024)
Pavel Dvorak (Sept 2021 - April 2022), now at Tata Institute of Fundamental Research, Mumbai

Publications (since 2020)

2024 2023 2022 2021 2020


Algorithms and Complexity research group
School of Computer Science, Electrical and Electronic Engineering, and Engineering Maths (SCEEM)
Faculty of Engineering
University of Bristol
Merchant Venturers Building
Woodland Road
BS8 1UB, Bristol
United Kingdom

Group contact email: