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:
- String Algorithms (Raphaël Clifford)
- Algorithmic theory for processing massive data sets, streaming algorithms, communication complexity, theory of distributed computing (Christian Konrad)
- Counting complexity, parameterised complexity, random algorithms, random processes on networks, graph theory (John Lapinskas)
News
| 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 Adithiya 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! |
People
| Core Faculty | ||
|---|---|---|
 Raphaël Clifford |
 (Head of Group) |
 John Lapinskas |
| Postdocs |
|---|
Hosted by Christian Konrad |
| PhD Students | ||
|---|---|---|
 since 2022 Supervisor: Christian Konrad |
 since 2021 Supervisor: Christian Konrad |
 since 2020 Supervisor: Christian Konrad |
| Former Members | ||
| Pavel Dvorak (Sept 2021 - April 2022), now at Tata Institute of Fundamental Research, Mumbai | ||
Publications (since 2020)
2023- Jacques Dark, Adithya Diddapur, Christian Konrad, "Interval Selection in Data Streams: Weighted Intervals and the Insertion-deletion Setting", 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023).
- Gwendolyn Farach-Colton, Martin Farach-Colton, Leslie Goldberg, Hanna Komlos, John Lapinskas, Reut Levi, Moti Medina and Miguel Mosteiro, "Graph Ranking and the Cost of Sybil Defense", 24th ACM Conference on Economics and Computation (EC'23) .
- Christian Konrad, Sanjeev Khanna, Cezar Alexandru, "Set Cover in the One-pass Edge-arrival Streaming Model", 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2023).
- Cezar Alexandru, Pavel Dvorak, Christian Konrad, Kheeran Naidu, "Improved Weighted Matching in the Sliding Window Model", 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023).
- Christian Konrad, Kheeran Naidu, Arun Steward, "Maximum Matching via Maximal Matching Queries", 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023).
- Leslie Ann Goldberg, John Lapinskas, "Instability of backoff protocols with arbitrary arrival rates", ACM-SIAM Symposium on Discrete Algorithms (SODA23).
- Oded Lachish, Felix Reidl and Chhaya Trehan, "When you come at the king you best not miss", 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022).
- Pavel Dvořák, Monika Krawczyk, Tomáš Masařík, Jana Novotná, Paweł Rzążewski, Aneta Żuk, "List Locally Surjective Homomorphisms in Hereditary Graph Classes", The 33rd International Symposium on Algorithms and Computation (ISAAC 2022).
- Raphael Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski, "The Dynamic k-Mismatch Problem", 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022).
- Christian Konrad, Victor Zamaraev, "Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs", Theoretical Computer Science (2022).
- Christian Konrad, Tigran Tonoyan, "Guessing Fractions of Online Sequences", Discrete Applied Mathematics (2022).
- Kheeran Naidu, Vihan Shah, "Space Optimal Vertex Cover in Dynamic Streams", Proceedings of the 25th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2022), to appear.
- Sanjeev Khanna, Christian Konrad, "Optimal Bounds for Dominating Set in Graph Streams", 13th Innovations in Theoretical Computer Science Conference (ITCS 2022).
- Leslie Ann Goldberg, Joost Jorritsma, Júlia Komjáthy, John Lapinskas, "Increasing efficacy of contact-tracing applications by user referrals and stricter quarantining", PLOS ONE (2021)
- Júlia Komjáthy, John Lapinskas, Johannes Lengler, "Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs", Annales de l’Institut Henri Poincaré (B) Probabilités et Statistiques (2021)
- Holger Dell, John Lapinskas, "Fine-grained reductions from approximate counting to decision", ACM Transactions on Computation Theory (2021), preliminary version in Proceedings of the 50th Annual ACM SIGACT Symptosium on Theory of Computing (STOC 2018)
- Christian Konrad, Kheeran Naidu, "On Two-pass Streaming Algorithms for Maximum Bipartite Matching", Proceedings of the 24th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2021).
- Christian Konrad, "Frequent Elements with Witnesses in Data Streams", 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2021).
- Michael Barlow, Christian Konrad, Charana Nandasena, "Streaming Set Cover in Practice", Symposium on Algorithm Engineering and Experiments (ALENEX 2021).
- Holger Dell, John Lapinskas, Kitty Meeks, "Approximately counting and sampling small witnesses using a colourful decision oracle", ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)
- Lidiya Binti Khalil, Christian Konrad, "Constructing Large Matchings via Query Access to a Maximal Matching Oracle", 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020).
- Jacques Dark, Christian Konrad, "Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams", 35th Computational Complexity Conference (CCC 2020).
- Artur Czumaj, Christian Konrad, "Detecting cliques in CONGEST networks", Distributed Computing (2020).
- Rajiv Gandhi, Magnús M. Halldórsson, Hoon Ho, Christian Konrad, Guy Kortsarz, "Radio Aggregation Scheduling", Theoretical Computer Science (2020).
- Magnús M. Halldórsson, Christian Konrad, Tigran Tonoyan, "Limitations of Current Wireless Scheduling Algorithms", Theoretical Computer Science (2020).
- Magnús M. Halldórsson, Christian Konrad, "Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees", Theoretical Computer Science (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