Christian Konrad

I am a Senior Lecturer in the Department of Computer Science at the University of Bristol. I am the head of the Algorithms and Complexity research group.

Research Interests:
My main research interest is the design and the analysis of algorithms. I am particularly interested in algorithmic challenges that arise when processing massive data sets and the theory of distributed computing.

Publications   Google Scholar   DBLP

Professional Service:

  • Program Committees: STACS 2020, ICALP (Track A) 2020
  • Communication Chair: PODC 2019
  • Conference Organization Committee: SWAT 2016

Projects:

CV:
Before joining Bristol in April 2018, I spent 18 months as a research associate at the University of Warwick and three years as a postdoc at Reykjavik University. I obtained my PhD (2013) from the Université Paris Diderot and Université Paris-Sud under the supervision of Frédéric Magniez and my Masters degree (2008) from the Technical University of Munich.

Get my CV here

Teaching / Supervision

Postdocs:
Pavel Dvorak, 2021-2022
Chhaya Trehan, 2022-Jan 2024

PhD Students: (Please get in touch if you are interested in doing a PhD in Algorithms!)
Archie Walton, 2024 - ongoing
Conor O'Sullivan, 2024 - ongoing
Adithya Diddapur, 2022 - ongoing
Cezar Alexandru, 2021 - ongoing
Kheeran Naidu, 2020 - 2024

Teaching:
2023 / 2024: COMS10017 Object-Oriented Programming and Algorithms I (first year), teaching Algorithms I
2022 / 2023: COMS10017 Object-Oriented Programming and Algorithms I (first year), teaching Algorithms I
2021 / 2022: COMS10017 Object-Oriented Programming and Algorithms I (first year), teaching Algorithms I
2021 / 2022: COMSM0068 Advanced Topics in Theoretical Computer Science (fourth year), second half of unit, unit director
2020 / 2021: COMS10017 Object-Oriented Programming and Algorithms I (first year), teaching Algorithms I
2020 / 2021: COMSM0068 Advanced Topics in Theoretical Computer Science (fourth year), second half of unit
2019 / 2020: COMS31900 Advanced Algorithms (third year), first half of unit
2019 / 2020: COMS10007 Algorithms (first year), unit director
2018 / 2019: COMS10007 Algorithms (first year), unit director


Publications

(Bristol undergraduate students are highlighted in red, and Bristol PhD students are highlighted in green)

Recent Manuscripts    Conference Publications    Journal Publications    Posters    Conference Reports    Theses

Recent Manuscripts

  1. Christian Konrad, Conor O'Sullivan, Victor Traistaru
    Graph Reconstruction via MIS Queries

Conference Publications

  1. Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran Naidu, Janani Sundaresan
    Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
    Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA 2025).
  2. Christian Konrad, Andrew McGregor, Rik Sengupta and Cuong Than
    Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model
    44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024).
  3. Cezar-Mihail Alexandru, Christian Konrad
    Interval Selection in Sliding Windows
    Proceedings of the 32nd European Symposium on Algorithms (ESA 2024).
  4. Sepehr Assadi, Christian Konrad, Kheeran Naidu, Janani Sundaresan
    O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set
    56th ACM Symposium on Theory of Computing (STOC 2024).
    Invited to SICOMP special issue
  5. Christian Konrad, Kheeran Naidu
    An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation
    Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA 2024).
  6. 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).
  7. Sanjeev Khanna, Christian Konrad, Cezar-Mihail Alexandru
    Set Cover in the One-pass Edge-arrival Streaming Model
    42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2023).
  8. 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).
  9. Christian Konrad, Kheeran Naidu, Arun Steward
    Maximum Matching via Maximal Matching Queries
    40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023).
  10. Sanjeev Khanna, Christian Konrad
    Optimal Bounds for Dominating Set in Graph Streams
    13th Innovations in Theoretical Computer Science Conference (ITCS 2022).
  11. 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).
  12. Christian Konrad
    Frequent Elements with Witnesses in Data Streams
    40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2021).
  13. Michael Barlow, Christian Konrad, Charana Nandasena
    Streaming Set Cover in Practice
    Symposium on Algorithm Engineering and Experiments (ALENEX 2021).
  14. Lidiya Binti Khalil, Christian Konrad
    Constructing Large Matchings via Query Access to a Maximal Matching Oracle (conference talk)
    40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020).
  15. Jacques Dark, Christian Konrad
    Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams
    35th Computational Complexity Conference (CCC 2020).
  16. Christian Konrad, Sriram Pemmaraju, Talal Riaz, Peter Robinson
    The Complexity of Symmetry Breaking in Massive Graphs
    Proceedings of the 33rd International Conference on Distributed Computing (DISC 2019).
  17. Christian Konrad, Victor Zamaraev
    Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs (conference talk)
    44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019).
  18. Graham Cormode, Jacques Dark, Christian Konrad
    Independent Sets in Vertex-Arrival Streams
    Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP 2019).
  19. Artur Czumaj, Christian Konrad
    Detecting cliques in CONGEST networks (conference talk)
    Proceedings of the 32nd International Conference on Distributed Computing (DISC 2018).
  20. Christian Konrad
    A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms (conference talk)
    43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).
  21. Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, Ronnit Rubinfeld
    Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
    Symposium on Principles of Distributed Computing (PODC 2018).
  22. Christian Konrad, Victor Zamaraev
    Brief Announcement: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs (conference talk)
    Symposium on Principles of Distributed Computing (PODC 2018).
  23. Graham Cormode, Jacques Dark, Christian Konrad
    Approximating the Caro-Wei Bound for Independent Sets in Graph Streams
    5th International Symposium on Combinatorial Optimization (ISCO 2018).
  24. Christian Konrad, Tigran Tonoyan
    Preemptively Guessing the Center (conference talk)
    5th International Symposium on Combinatorial Optimization (ISCO 2018).
  25. Magnús M. Halldórsson, Christian Konrad
    Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees (conference talk)
    24th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2017).
    Invited to TCS special issue
  26. Eden Chlamtàč, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
    The Densest k-Subhypergraph Problem
    Proceedings of the 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2016).
  27. Christoph Dürr, Christian Konrad, Marc Renault
    On the Power of Advice and Randomization for Online Bipartite Matching (conference talk)
    Proceedings of the 24th European Symposium on Algorithms (ESA 2016).
  28. Marijke H.L. Bodlaender, Magnús M. Halldórsson, Christian Konrad, Fabian Kuhn
    Brief Announcement: Local Independent Set Approximation
    Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC 2016).
  29. Christian Konrad
    Streaming Partitioning of Sequences and Trees (conference talk)
    Proceedings of the 19th International Conference on Database Theory (ICDT 2016).
  30. Magnús M. Halldórsson, Christian Konrad
    Distributed Large Independent Sets in One Round On Bounded-independence Graphs (conference talk)
    Proceedings of the 29th International Conference on Distributed Computing (DISC 2015).
  31. Rajiv Gandhi, Magnús M. Halldórsson, Hoon Ho, Christian Konrad, Guy Kortsarz
    Radio Aggregation Scheduling (conference talk)
    Proceedings of the 11th International Symposium on Algorithms and Experiements for Wireless Sensor Networks (ALGOSENSORS 2015).
    Invited to TCS special issue
  32. Magnús M. Halldórsson, Christian Konrad, Tigran Tonoyan
    Limitations of Current Wireless Scheduling Algorithms
    Proceedings of the 11th International Symposium on Algorithms and Experiements for Wireless Sensor Networks (ALGOSENSORS 2015).
    Invited to TCS special issue
  33. Christian Konrad
    Maximum Matching in Turnstile Streams (conference talk)
    Proceedings of the 23rd European Symposium on Algorithms (ESA 2015).
  34. Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou
    The Minimum Vulnerability Problem on Graphs
    Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2014).
    Invited to JOCO special issue
  35. Magnús M. Halldórsson, Christian Konrad
    Distributed Algorithms for Coloring Interval Graphs (conference talk)
    Proceedings of the 28th International Conference on Distributed Computing (DISC 2014).
  36. Di Chen, Christian Konrad, Ke Yi, Wei Yu, Qin Zhang
    Robust Set Reconciliation (conference talk)
    Proceedings of the ACM International Conference on Management of Data (SIGMOD 2014).
  37. Christian Konrad, Adi Rosén
    Approximating Semi-Matchings in Streaming and in Two-Party Communication (conference talk)
    Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013).
  38. Christian Konrad, Frédéric Magniez, Claire Mathieu
    Maximum Matching in Semi-Streaming with Few Passes (conference talk)
    Proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2012).
  39. Christian Konrad, Frédéric Magniez
    Validating XML Documents in the Streaming Model with External Memory (conference talk)
    Proceedings of the 15th International Conference on Database Theory (ICDT 2012).
    Best Newcomer Paper Award, invited to TODS special issue

Journal Publications

  1. Christian Konrad, Victor Zamaraev
    Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
    Theoretical Computer Science (2022).
  2. Christian Konrad, Tigran Tonoyan
    Guessing Fractions of Online Sequences
    Discrete Applied Mathematics (2022).
  3. Artur Czumaj, Christian Konrad
    Detecting cliques in CONGEST networks
    Distributed Computing (2020).
  4. Rajiv Gandhi, Magnús M. Halldórsson, Hoon Ho, Christian Konrad, Guy Kortsarz
    Radio Aggregation Scheduling
    Theoretical Computer Science (2020).
  5. Magnús M. Halldórsson, Christian Konrad, Tigran Tonoyan
    Limitations of Current Wireless Scheduling Algorithms
    Theoretical Computer Science (2020).
  6. Magnús M. Halldórsson, Christian Konrad
    Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees
    Theoretical Computer Science (2020).
  7. Eden Chlamtàč, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
    The Densest k-Subhypergraph Problem
    SIAM Journal of Discrete Mathematics (SIDMA 2018).
  8. Christoph Dúrr, Zdeněk Hanzálek, Christian Konrad, Yasmina Seddik, René Sitters, Óscar C. Vásquez, Gerhard Woeginger
    The triangle scheduling problem
    Journal of Scheduling (2018).
  9. Magnús M. Halldórsson, Christian Konrad
    Computing Large Independent Sets in a Single Round
    Distributed Computing (2018).
  10. Christian Konrad, Adi Rosén
    Approximating Semi-Matchings in Streaming and in Two-Party Communication
    ACM Transactions on Algorithms (TALG 2016).
  11. Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou
    The Minimum Vulnerability Problem on Specific Graph Classes
    Journal of Combinatorial Optimization (JOCO 2014).
  12. Christian Konrad, Frédéric Magniez
    Validating XML Documents in the Streaming Model with External Memory
    ACM Transactions on Database Systems (TODS 2013). (invited papers issue)
  13. Christian Konrad
    Two-constraint domain decomposition with Space Filling Curves
    Parallel Computing (2011).

Poster Presentations

  1. Marijke H.L. Bodlaender, Magnús M. Halldórsson, Christian Konrad
    Distributed Maximum Independent Set and Minimum Vertex Coloring
    29th International Conference on Distributed Computing (DISC 2015).

Conference Reports

  1. Christian Konrad
    Report on SIROCCO 2017
    ACM SIGACT News (Volume 48, 2017).

Theses

  1. Christian Konrad
    Computations on Massive Data Sets: Streaming Algorithms and Two-Party Communication
    PhD thesis (2013).
  2. Christian Konrad
    Aspects of parallelization for the resolution of the coupled Maxwell/Vlasov equations
    Diploma thesis (2008).




Christian

Contact

Email:
FIRSTNAME DOT LASTNAME AT bristol.ac.uk

Address:
Department of Computer Science
University of Bristol
Merchant Venturers Building (Room 306)
Woodland Road
BRISTOL BS8 1UB
United Kingdom