Christian Konrad

I am an Assistant Professor (UK: lecturer) in the Department of Computer Science at the University of Bristol.

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

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

Students:
Interested in algorithms and their analysis? Get in touch (christian.konrad at bristol.ac.uk) if you are interested in doing your PhD under my supervision.

Courses:
2018 / 2019: University of Bristol
I will be the unit director of the first year Algorithms course COMS10007 taught in TB2.

2014 / 2015: Reykjavik University
Introduction to Graph Theory.


Publications

Recent Manuscripts    Conference Publications    Journal Publications    Posters    Conference Reports    Theses

Recent Manuscripts

  1. Artur Czumaj, Christian Konrad
    Detecting cliques in CONGEST networks

Conference Publications

  1. Christian Konrad
    A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms
    43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).
  2. 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).
  3. Christian Konrad, Victor Zamaraev
    Brief Announcement: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
    Symposium on Principles of Distributed Computing (PODC 2018).
  4. 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).
  5. Christian Konrad, Tigran Tonoyan
    Preemptively Guessing the Center (conference talk)
    5th International Symposium on Combinatorial Optimization (ISCO 2018).
  6. 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
  7. 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).
  8. 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).
  9. 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).
  10. Christian Konrad
    Streaming Partitioning of Sequences and Trees (conference talk)
    Proceedings of the 19th International Conference on Database Theory (ICDT 2016).
  11. 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).
  12. 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
  13. 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
  14. Christian Konrad
    Maximum Matching in Turnstile Streams (conference talk)
    Proceedings of the 23rd European Symposium on Algorithms (ESA 2015).
  15. 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
  16. 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).
  17. 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).
  18. 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).
  19. 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).
  20. 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).
    Best Newcomer Paper Award, invited to TODS special issue

Journal Publications

  1. Eden Chlamtàč, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
    The Densest k-Subhypergraph Problem
    SIAM Journal of Discrete Mathematics (SIDMA, to appear).
  2. 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).
  3. Magnús M. Halldórsson, Christian Konrad
    Computing Large Independent Sets in a Single Round
    Distributed Computing (2018).
  4. Christian Konrad, Adi Rosén
    Approximating Semi-Matchings in Streaming and in Two-Party Communication
    ACM Transactions on Algorithms (TALG 2016).
  5. 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).
  6. 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)
  7. 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:
christian.konrad AT bristol.ac.uk

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