Christian Konrad

89 papers A* 10A 17B 3C 5Journal 44Unranked 9
YearRankTypeTitle / Venue / Authors
2026 J jnl
Fault-Tolerant Distance Oracles Below the n · f Barrier.
CoRR
Sanjeev Khanna, Christian Konrad, Aaron Putterman
2026 — conf
Semi-Robust Communication Complexity of Maximum Matching.
SOSA
Gabriel Cipriani Huete, Adithya Diddapur, Pavel Dvorák, Christian Konrad
2026 A conf
Unit Interval Selection in Random Order Streams.
STACS
Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson, Christian Konrad, Kheeran K. Naidu
2026 J jnl
Unit Interval Selection in Random Order Streams.
CoRR
Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson, Christian Konrad, Kheeran K. Naidu
2025 A conf
Constructing Long Paths in Graph Streams.
ESA
Christian Konrad, Chhaya Trehan
2025 J jnl
Constructing Long Paths in Graph Streams.
CoRR
Christian Konrad, Chhaya Trehan
2025 A conf
Graph Reconstruction via MIS Queries.
ITCS
Christian Konrad, Conor O'Sullivan, Victor Traistaru
2025 J jnl
Semi-Robust Communication Complexity of Maximum Matching.
CoRR
Gabriel Cipriani Huete, Adithya Diddapur, Pavel Dvorák, Christian Konrad
2025 A* conf
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams.
SODA
Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
2025 A* conf
Streaming Maximal Matching with Bounded Deletions.
ICALP
Sanjeev Khanna, Christian Konrad, Jacques Dark
2025 J jnl
Streaming Maximal Matching with Bounded Deletions.
CoRR
Sanjeev Khanna, Christian Konrad, Jacques Dark
2024 A* conf
An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation.
SODA
Christian Konrad, Kheeran K. Naidu
2024 J jnl
Graph Reconstruction via MIS Queries.
CoRR
Christian Konrad, Conor O'Sullivan, Victor Traistaru
2024 A conf
Interval Selection in Sliding Windows.
ESA
Cezar-Mihail Alexandru, Christian Konrad
2024 J jnl
Interval Selection in Sliding Windows.
CoRR
Cezar-Mihail Alexandru, Christian Konrad
2024 — conf
Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model.
FSTTCS
Christian Konrad, Andrew McGregor, Rik Sengupta, Cuong Than
2024 A* conf
O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set.
STOC
Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
2024 J jnl
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams.
CoRR
Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
2023 A conf
Improved Weighted Matching in the Sliding Window Model.
STACS
Cezar-Mihail Alexandru, Pavel Dvorák, Christian Konrad, Kheeran K. Naidu
2023 — conf
Interval Selection in Data Streams: Weighted Intervals and the Insertion-Deletion Setting.
FSTTCS
Jacques Dark, Adithya Diddapur, Christian Konrad
2023 A conf
Maximum Matching via Maximal Matching Queries.
STACS
Christian Konrad, Kheeran K. Naidu, Arun Steward
2023 J jnl
O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set.
CoRR
Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan
2023 A* conf
Set Cover in the One-pass Edge-arrival Streaming Model.
PODS
Sanjeev Khanna, Christian Konrad, Cezar-Mihail Alexandru
2022 J jnl
Closing the Gap between Weighted and Unweighted Matching in the Sliding Window Model.
CoRR
Cezar-Mihail Alexandru, Pavel Dvorák, Christian Konrad, Kheeran K. Naidu
2022 J jnl
Distributed minimum vertex coloring and maximum independent set in chordal graphs.
Theor. Comput. Sci.
Christian Konrad, Viktor Zamaraev
2022 J jnl
Guessing fractions of online sequences.
Discret. Appl. Math.
Christian Konrad, Tigran Tonoyan
2022 A conf
Optimal Bounds for Dominating Set in Graph Streams.
ITCS
Sanjeev Khanna, Christian Konrad
2021 A* conf
Frequent Elements with Witnesses in Data Streams.
PODS
Christian Konrad
2021 — conf
On Two-Pass Streaming Algorithms for Maximum Bipartite Matching.
APPROX-RANDOM
Christian Konrad, Kheeran K. Naidu
2021 J jnl
On Two-Pass Streaming Algorithms for Maximum Bipartite Matching.
CoRR
Christian Konrad, Kheeran K. Naidu
2021 J jnl
Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication.
CoRR
Christian Konrad, Peter Robinson, Viktor Zamaraev
2021 A conf
Streaming Set Cover in Practice.
ALENEX
Michael Barlow, Christian Konrad, Charana Nandasena
2021 J jnl
The Complexity of Symmetry Breaking in Massive Graphs.
CoRR
Christian Konrad, Sriram V. Pemmaraju, Talal Riaz, Peter Robinson
2020 — conf
Constructing Large Matchings via Query Access to a Maximal Matching Oracle.
FSTTCS
Lidiya Khalidah binti Khalil, Christian Konrad
2020 J jnl
Constructing Large Matchings via Query Access to a Maximal Matching Oracle.
CoRR
Lidiya Khalidah binti Khalil, Christian Konrad
2020 J jnl
Detecting cliques in CONGEST networks.
Distributed Comput.
Artur Czumaj, Christian Konrad
2020 J jnl
Improved distributed algorithms for coloring interval graphs with application to multicoloring trees.
Theor. Comput. Sci.
Magnús M. Halldórsson, Christian Konrad
2020 J jnl
Limitations of current wireless link scheduling algorithms.
Theor. Comput. Sci.
Magnús M. Halldórsson, Christian Konrad, Tigran Tonoyan
2020 A conf
Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams.
CCC
Jacques Dark, Christian Konrad
2020 J jnl
Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams.
CoRR
Jacques Dark, Christian Konrad
2020 J jnl
Radio aggregation scheduling.
Theor. Comput. Sci.
Rajiv Gandhi, Magnús M. Halldórsson, Christian Konrad, Guy Kortsarz, Hoon Oh
2019 B conf
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs.
MFCS
Christian Konrad, Viktor Zamaraev
2019 A* conf
Independent Sets in Vertex-Arrival Streams.
ICALP
Graham Cormode, Jacques Dark, Christian Konrad
2019 J jnl
Streaming Frequent Items with Timestamps and Detecting Large Neighborhoods in Graph Streams.
CoRR
Christian Konrad
2019 A conf
The Complexity of Symmetry Breaking in Massive Graphs.
DISC
Christian Konrad, Sriram V. Pemmaraju, Talal Riaz, Peter Robinson
2018 B conf
A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms.
MFCS
Christian Konrad
2018 C conf
Approximating the Caro-Wei Bound for Independent Sets in Graph Streams.
ISCO
Graham Cormode, Jacques Dark, Christian Konrad
2018 A* conf
Brief Announcement: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs.
PODC
Christian Konrad, Viktor Zamaraev
2018 J jnl
Computing large independent sets in a single round.
Distributed Comput.
Magnús M. Halldórsson, Christian Konrad
2018 A conf
Detecting Cliques in CONGEST Networks.
DISC
Artur Czumaj, Christian Konrad
2018 J jnl
Detecting cliques in CONGEST networks.
CoRR
Artur Czumaj, Christian Konrad
2018 J jnl
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs.
CoRR
Christian Konrad, Viktor Zamaraev
2018 A* conf
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.
PODC
Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, Ronitt Rubinfeld
2018 J jnl
Independent Sets in Vertex-Arrival Streams.
CoRR
Graham Cormode, Jacques Dark, Christian Konrad
2018 J jnl
MIS in the Congested Clique Model in O(log log Δ) Rounds.
CoRR
Christian Konrad
2018 C conf
Preemptively Guessing the Center.
ISCO
Christian Konrad, Tigran Tonoyan
2018 J jnl
The Densest k-Subhypergraph Problem.
SIAM J. Discret. Math.
Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
2018 J jnl
The triangle scheduling problem.
J. Sched.
Christoph Dürr, Zdenek Hanzálek, Christian Konrad, Yasmina Seddik, René Sitters, Óscar C. Vásquez, Gerhard J. Woeginger
2017 B conf
Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees.
SIROCCO
Magnús M. Halldórsson, Christian Konrad
2017 J jnl
Independent Set Size Approximation in Graph Streams.
CoRR
Graham Cormode, Jacques Dark, Christian Konrad
2017 J jnl
Preemptive Online Partitioning of Sequences.
CoRR
Christian Konrad, Tigran Tonoyan
2017 J jnl
SIROCCO 2017 Review.
SIGACT News
Christian Konrad
2016 J jnl
Approximating Semi-matchings in Streaming and in Two-Party Communication.
ACM Trans. Algorithms
Christian Konrad, Adi Rosén
2016 A* conf
Brief Announcement: Local Independent Set Approximation.
PODC
Marijke H. L. Bodlaender, Magnús M. Halldórsson, Christian Konrad, Fabian Kuhn
2016 A conf
On the Power of Advice and Randomization for Online Bipartite Matching.
ESA
Christoph Dürr, Christian Konrad, Marc P. Renault
2016 J jnl
On the Power of Advice and Randomization for Online Bipartite Matching.
CoRR
Christoph Dürr, Christian Konrad, Marc P. Renault
2016 A conf
Streaming Partitioning of Sequences and Trees.
ICDT
Christian Konrad
2016 — conf
The Densest k-Subhypergraph Problem.
APPROX-RANDOM
Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
2016 J jnl
The Densest k-Subhypergraph Problem.
CoRR
Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
2016 J jnl
The minimum vulnerability problem on specific graph classes.
J. Comb. Optim.
Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou
2016 J jnl
The triangle scheduling problem.
CoRR
Christoph Dürr, Zdenek Hanzálek, Christian Konrad, René Sitters, Óscar C. Vásquez, Gerhard J. Woeginger
2015 A conf
Distributed Large Independent Sets in One Round on Bounded-Independence Graphs.
DISC
Magnús M. Halldórsson, Christian Konrad
2015 C conf
Limitations of Current Wireless Scheduling Algorithms.
ALGOSENSORS
Magnús M. Halldórsson, Christian Konrad, Tigran Tonoyan
2015 A conf
Maximum Matching in Turnstile Streams.
ESA
Christian Konrad
2015 J jnl
Maximum Matching in Turnstile Streams.
CoRR
Christian Konrad
2015 C conf
Radio Aggregation Scheduling.
ALGOSENSORS
Rajiv Gandhi, Magnús M. Halldórsson, Christian Konrad, Guy Kortsarz, Hoon Oh
2014 A conf
Distributed Algorithms for Coloring Interval Graphs.
DISC
Magnús M. Halldórsson, Christian Konrad
2014 — conf
Robust set reconciliation.
SIGMOD Conference
Di Chen, Christian Konrad, Ke Yi, Wei Yu, Qin Zhang
2014 J jnl
Streaming Algorithms for Partitioning Integer Sequences.
CoRR
Christian Konrad, László Kozma
2014 C conf
The Minimum Vulnerability Problem on Graphs.
COCOA
Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou
2013 J jnl
Approximating Semi-Matchings in Streaming and in Two-Party Communication
CoRR
Christian Konrad, Adi Rosén
2013 — conf
Approximating Semi-matchings in Streaming and in Two-Party Communication.
ICALP (1)
Christian Konrad, Adi Rosén
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
2013 J jnl
Validating XML documents in the streaming model with external memory.
ACM Trans. Database Syst.
Christian Konrad, Frédéric Magniez
2012 — conf
Maximum Matching in Semi-streaming with Few Passes.
APPROX-RANDOM
Christian Konrad, Frédéric Magniez, Claire Mathieu
2012 A conf
Validating XML documents in the streaming model with external memory.
ICDT
Christian Konrad, Frédéric Magniez
2011 J jnl
Maximum Matching in Semi-Streaming with Few Passes
CoRR
Christian Konrad, Frédéric Magniez, Claire Mathieu
2011 J jnl
Two-constraint domain decomposition with Space Filling Curves.
Parallel Comput.
Christian Konrad
2010 J jnl
The Streaming Complexity of Validating XML Documents
CoRR
Christian Konrad, Frédéric Magniez