Christian Konrad

According to our database, Christian Konrad authored at least 57 papers between 2010 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams.

Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

2024

Graph Reconstruction via MIS Queries.

Christian Konrad, Conor O'Sullivan, Victor Traistaru

CoRR, 2024

O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set.

Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation.

Christian Konrad, Kheeran K. Naidu

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model.

Christian Konrad, Andrew McGregor, Rik Sengupta, Cuong Than

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

Interval Selection in Sliding Windows.

Cezar-Mihail Alexandru, Christian Konrad

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Improved Weighted Matching in the Sliding Window Model.

Cezar-Mihail Alexandru, Pavel Dvorák, Christian Konrad, Kheeran K. Naidu

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Maximum Matching via Maximal Matching Queries.

Christian Konrad, Kheeran K. Naidu, Arun Steward

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Set Cover in the One-pass Edge-arrival Streaming Model.

Sanjeev Khanna, Christian Konrad, Cezar-Mihail Alexandru

Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023

Interval Selection in Data Streams: Weighted Intervals and the Insertion-Deletion Setting.

Jacques Dark, Adithya Diddapur, Christian Konrad

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

2022

Distributed minimum vertex coloring and maximum independent set in chordal graphs.

Christian Konrad, Viktor Zamaraev

Theor. Comput. Sci., 2022

Guessing fractions of online sequences.

Christian Konrad, Tigran Tonoyan

Discret. Appl. Math., 2022

Closing the Gap between Weighted and Unweighted Matching in the Sliding Window Model.

Cezar-Mihail Alexandru, Pavel Dvorák, Christian Konrad, Kheeran K. Naidu

CoRR, 2022

Optimal Bounds for Dominating Set in Graph Streams.

Sanjeev Khanna, Christian Konrad

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication.

Christian Konrad, Peter Robinson, Viktor Zamaraev

CoRR, 2021

Frequent Elements with Witnesses in Data Streams.

Christian Konrad

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

On Two-Pass Streaming Algorithms for Maximum Bipartite Matching.

Christian Konrad, Kheeran K. Naidu

Proceedings of the Approximation, 2021

Streaming Set Cover in Practice.

Michael Barlow, Christian Konrad, Charana Nandasena

Proceedings of the Symposium on Algorithm Engineering and Experiments, 2021

2020

Limitations of current wireless link scheduling algorithms.

Magnús M. Halldórsson, Christian Konrad, Tigran Tonoyan

Theor. Comput. Sci., 2020

Improved distributed algorithms for coloring interval graphs with application to multicoloring trees.

Magnús M. Halldórsson, Christian Konrad

Theor. Comput. Sci., 2020

Radio aggregation scheduling.

Rajiv Gandhi, Magnús M. Halldórsson, Christian Konrad, Guy Kortsarz, Hoon Oh

Theor. Comput. Sci., 2020

Detecting cliques in CONGEST networks.

Artur Czumaj, Christian Konrad

Distributed Comput., 2020

Constructing Large Matchings via Query Access to a Maximal Matching Oracle.

Lidiya Khalidah binti Khalil, Christian Konrad

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams.

Jacques Dark, Christian Konrad

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Streaming Frequent Items with Timestamps and Detecting Large Neighborhoods in Graph Streams.

Christian Konrad

CoRR, 2019

The Complexity of Symmetry Breaking in Massive Graphs.

Christian Konrad, Sriram V. Pemmaraju, Talal Riaz, Peter Robinson

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Independent Sets in Vertex-Arrival Streams.

Graham Cormode, Jacques Dark, Christian Konrad

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

The Densest k-Subhypergraph Problem.

Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca

SIAM J. Discret. Math., 2018

The triangle scheduling problem.

Christoph Dürr, Zdenek Hanzálek, Christian Konrad, Yasmina Seddik, René Sitters, Óscar C. Vásquez, Gerhard J. Woeginger

J. Sched., 2018

Computing large independent sets in a single round.

Magnús M. Halldórsson, Christian Konrad

Distributed Comput., 2018

MIS in the Congested Clique Model in O(log log Δ) Rounds.

Christian Konrad

CoRR, 2018

Brief Announcement: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs.

Christian Konrad, Viktor Zamaraev

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.

Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, Ronitt Rubinfeld

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms.

Christian Konrad

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Preemptively Guessing the Center.

Christian Konrad, Tigran Tonoyan

Proceedings of the Combinatorial Optimization - 5th International Symposium, 2018

Approximating the Caro-Wei Bound for Independent Sets in Graph Streams.

Graham Cormode, Jacques Dark, Christian Konrad

Proceedings of the Combinatorial Optimization - 5th International Symposium, 2018

2017

SIROCCO 2017 Review.

Christian Konrad

SIGACT News, 2017

Preemptive Online Partitioning of Sequences.

Christian Konrad, Tigran Tonoyan

CoRR, 2017

Independent Set Size Approximation in Graph Streams.

Graham Cormode, Jacques Dark, Christian Konrad

CoRR, 2017

2016

Approximating Semi-matchings in Streaming and in Two-Party Communication.

Christian Konrad, Adi Rosén

ACM Trans. Algorithms, 2016

The minimum vulnerability problem on specific graph classes.

Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou

J. Comb. Optim., 2016

The triangle scheduling problem.

Christoph Dürr, Zdenek Hanzálek, Christian Konrad, René Sitters, Óscar C. Vásquez, Gerhard J. Woeginger

CoRR, 2016

Brief Announcement: Local Independent Set Approximation.

Marijke H. L. Bodlaender, Magnús M. Halldórsson, Christian Konrad, Fabian Kuhn

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Streaming Partitioning of Sequences and Trees.

Christian Konrad

Proceedings of the 19th International Conference on Database Theory, 2016

On the Power of Advice and Randomization for Online Bipartite Matching.

Christoph Dürr, Christian Konrad, Marc P. Renault

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Distributed Large Independent Sets in One Round on Bounded-Independence Graphs.

Magnús M. Halldórsson, Christian Konrad

Proceedings of the Distributed Computing - 29th International Symposium, 2015

Maximum Matching in Turnstile Streams.

Christian Konrad

Proceedings of the Algorithms - ESA 2015, 2015

Limitations of Current Wireless Scheduling Algorithms.

Magnús M. Halldórsson, Christian Konrad, Tigran Tonoyan

Proceedings of the Algorithms for Sensor Systems, 2015

2014

Streaming Algorithms for Partitioning Integer Sequences.

Christian Konrad, László Kozma

CoRR, 2014

Distributed Algorithms for Coloring Interval Graphs.

Magnús M. Halldórsson, Christian Konrad

Proceedings of the Distributed Computing - 28th International Symposium, 2014

Robust set reconciliation.

Di Chen, Christian Konrad, Ke Yi, Wei Yu, Qin Zhang

Proceedings of the International Conference on Management of Data, 2014

The Minimum Vulnerability Problem on Graphs.

Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou

Proceedings of the Combinatorial Optimization and Applications, 2014

2013

Computations on Massive Data Sets : Streaming Algorithms and Two-party Communication. (Calculs sur des grosses données : algorithmes de streaming et communication entre deux joueurs).

Christian Konrad

PhD thesis, 2013

Validating XML documents in the streaming model with external memory.

Christian Konrad, Frédéric Magniez

ACM Trans. Database Syst., 2013

2012

Maximum Matching in Semi-streaming with Few Passes.

Christian Konrad, Frédéric Magniez, Claire Mathieu

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Two-constraint domain decomposition with Space Filling Curves.

Christian Konrad

Parallel Comput., 2011

2010

The Streaming Complexity of Validating XML Documents

Christian Konrad, Frédéric Magniez

CoRR, 2010