Christian Konrad

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:

• EPSRC New Investigator Award, Principal Investigator, "StreamDG: Streaming Processing of Massive Dynamic Graphs", 09/2021-08/2024, ~£250.000
• General Research Fund (Hong Kong), Co-investigator, "Algorithmic Foundations of Distributed Large-Scale Graph Processing", 01/2021 - 12/2023, ~£80.000

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

Recent Manuscripts

Conference Publications

1. Christian Konrad, Conor O'Sullivan, Victor Traistaru
   Graph Reconstruction via MIS Queries
   16th Innovations in Theoretical Computer Science Conference (ITCS 2025).
2. 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).
3. 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).
4. Cezar-Mihail Alexandru, Christian Konrad
   Interval Selection in Sliding Windows
   Proceedings of the 32nd European Symposium on Algorithms (ESA 2024).
5. 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
6. 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).
7. 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).
8. 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).
9. 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).
10. Christian Konrad, Kheeran Naidu, Arun Steward
    Maximum Matching via Maximal Matching Queries
    40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023).
11. Sanjeev Khanna, Christian Konrad
    Optimal Bounds for Dominating Set in Graph Streams
    13th Innovations in Theoretical Computer Science Conference (ITCS 2022).
12. 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).
13. Christian Konrad
    Frequent Elements with Witnesses in Data Streams
    40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2021).
14. Michael Barlow, Christian Konrad, Charana Nandasena
    Streaming Set Cover in Practice
    Symposium on Algorithm Engineering and Experiments (ALENEX 2021).
15. 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).
16. Jacques Dark, Christian Konrad
    Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams
    35th Computational Complexity Conference (CCC 2020).
17. 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).
18. 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).
19. 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).
20. Artur Czumaj, Christian Konrad
    Detecting cliques in CONGEST networks (conference talk)
    Proceedings of the 32nd International Conference on Distributed Computing (DISC 2018).
21. 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).
22. 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).
23. 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).
24. 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).
25. Christian Konrad, Tigran Tonoyan
    Preemptively Guessing the Center (conference talk)
    5th International Symposium on Combinatorial Optimization (ISCO 2018).
26. 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
27. 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).
28. 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).
29. 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).
30. Christian Konrad
    Streaming Partitioning of Sequences and Trees (conference talk)
    Proceedings of the 19th International Conference on Database Theory (ICDT 2016).
31. 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).
32. 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
33. 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
34. Christian Konrad
    Maximum Matching in Turnstile Streams (conference talk)
    Proceedings of the 23rd European Symposium on Algorithms (ESA 2015).
35. 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
36. 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).
37. 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).
38. 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).
39. 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).
40. 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).