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)
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 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
Publications (since 2020)
2022
- Sanjeev Khanna, Christian Konrad, "Optimal Bounds for Dominating Set in Graph Streams", 13th Innovations in Theoretical Computer Science Conference (ITCS 2022).
2021
- 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).
2020
- 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).
Group contact email:
christian.konrad@bristol.ac.uk