Dennis Olivetti
- Lower bounds for maximal matchings and maximal independent sets
2019/01/08 by Alkida Balliu, Balliu, Alkida, Sebastian Brandt +9 · 5 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Distributed #FOS: Computer and information sciences #Parallel #Privacy-Preserving Technologies in Data #and Cluster Computing (cs.DC)
- The distributed complexity of locally checkable problems on paths is\n decidable
2018/11/05 by Alkida Balliu, Sebastian Brandt, Balliu, Alkida +9 · 4 citations
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
- Distributed Δ-Coloring Plays Hide-and-Seek
2021/10/01 by Alkida Balliu, Balliu, Alkida, Sebastian Brandt +5 · 5 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
- Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
2022/11/03 by Alkida Balliu, Balliu, Alkida, Sebastian Brandt +5 · 5 citations
Computer Science · Economics, Econometrics and Finance · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Game Theory and Voting Systems #Parallel #and Cluster Computing (cs.DC)
- Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
2020/02/19 by Sebastian Brandt, Dennis Olivetti, Brandt, Sebastian +1 · 3 citations
Computer Science · #Machine Learning and Algorithms
- Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree\n Dominating Sets in Trees
2021/06/04 by Alkida Balliu, Sebastian Brandt, Balliu, Alkida +5 · 3 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
- Locally Checkable Problems in Rooted Trees
2021/02/18 by Alkida Balliu, Sebastian Brandt, Balliu, Alkida +11 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
- Distributed Quantum Advantage for Local Problems
2024/11/05 by Alkida Balliu, Balliu, Alkida, Sebastian Brandt +23 · 1 voice · 5 citations
#cs.DC #cs.CC #quant-ph
- Tight Lower Bounds in the Supported LOCAL Model
2024/05/01 by Alkida Balliu, Balliu, Alkida, Thomas Boudier +5 · 2 citations
Engineering · #Distributed #FOS: Computer and information sciences #Fault Detection and Control Systems #Medical Imaging and Analysis #Parallel #and Cluster Computing (cs.DC)
- Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
2024/10/27 by Alkida Balliu, Balliu, Alkida, Pierre Fraigniaud +5 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Neural Networks and Applications #Parallel #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
- New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
2025/06/09 by Alkida Balliu, Corinna Coupette, Balliu, Alkida +15 · 1 voice · 2 citations
#cs.DC #cs.CC
- Distributed Edge Coloring in Time Polylogarithmic in \(Δ \)
2026/07/23 by Alkida Balliu, Sebastian Brandt, Fabian Kuhn +2
Computer Science · #Complexity and Algorithms in Graphs #Distributed systems and fault tolerance #Advanced Graph Theory Research