Algorithms and Complexity

NEWS PEOPLE PUBLICATIONSCONTACT

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.

News

November 2024Paper "Graph Reconstruction via MIS Queries" (by Christian Konrad, Conor O'Sullivan, Victor Traistaru) accepted at ITCS 2025!
October 2024Paper "Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams" (by Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran Naidu, Janani Sundaresan) accepted at SODA 2025! See here for a preprint.
September 2024Paper "Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model" (by Christian Konrad, Andrew McGregor, Rik Sengupta and Cuong Than) accepted at FSTTCS 2024! A pre-print will be shared soon.
September 2024We welcome the new PhD students Archie Walton and Conor O'Sullivan to the team!
June 2024Paper "Interval Selection in Sliding Windows" (by Cezar-Mihail Alexandru, Christian Konrad) accepted at ESA 2024! Click here for a pre-print. Cezar will present the paper at the conference.
June 2024We recently organized a joint Algo-Cryto-Programming Languages workshop for the Bristol research groups in Bath.


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 Adithya 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!

People

Core Faculty


Raphaël Clifford


Christian Konrad
(Head of Group)


John Lapinskas
Postdocs
PhD Students


Conor O'Sullivan
since 2024
Supervisor: Christian Konrad


Archie Walton
since 2024
Supervisor: Christian Konrad


Adithya Diddapur
since 2022
Supervisor: Christian Konrad


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

Publications (since 2020)

2025 2024 2023 2022 2021 2020

Contact

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: christian.konrad@bristol.ac.uk