Algorithms and Complexity
|
November 2024 | Paper "Graph Reconstruction via MIS Queries" (by Christian Konrad, Conor O'Sullivan, Victor Traistaru) accepted at ITCS 2025! |
October 2024 | Paper "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 2024 | Paper "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 2024 | We welcome the new PhD students Archie Walton and Conor O'Sullivan to the team! |
June 2024 | Paper "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 2024 | We recently organized a joint Algo-Cryto-Programming Languages workshop for the Bristol research groups in Bath. |
April 2024 | Paper "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 2024 | Paper "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 2023 | Paper "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 2023 | Paper "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 2023 | Paper "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 2023 | Paper "Set Cover in the One-pass Edge-arrival Streaming Model" (by Sanjeev Khanna, Christian Konrad, and Cezar Alexandru) accepted at PODS 2023! |
March 2023 | Our 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 2022 | Two 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 2022 | Paper Instability of backoff protocols with arbitrary arrival rates by John Lapinskas (joint work with Leslie Ann Goldberg) accepted at SODA 2023! |
October 2022 | Paper "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 2022 | We welcome Research Associate Chhaya Trehan and PhD student Adithya Diddapur to the group! |
June 2022 | Raphael 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 2022 | Congratulations 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 2021 | Paper "Optimal Bounds for Dominating Set in Graph Streams" by Sanjeev Khanna and Christian Konrad accepted at ITCS 2022! |
October 2021 | We welcome our new Research Associate Dr Pavel Dvorak to the group! |
September 2021 | We welcome our new PhD student Cezar Alexandru to the group! |
August 2021 | PhD student Kheeran Naidu presented his recent work at APPROX'21. Check out his presentation here. |
July 2021 | Group webpage goes online! |
Core Faculty | ||
---|---|---|
Raphaël Clifford |
(Head of Group) |
John Lapinskas |
Postdocs |
---|
PhD Students | ||
---|---|---|
since 2024 Supervisor: Christian Konrad |
since 2024 Supervisor: Christian Konrad |
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 |
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 |