48 citations · 88 across the 7 of their papers we have counts for
3 papers · 1 filter
New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
Alkida Balliu, Corinna Coupette, Antonio Cruciani +6
In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing. First, we show that there is no d…
Model-Agnostic Approximation of Constrained Forest Problems
Corinna Coupette, Alipasha Montaseri, Christoph Lenzen
Constrained Forest Problems (CFPs) as introduced by Goemans and Williamson in 1995 capture a wide range of network design problems with edge subsets as solutions, such as Minimum S…
A Breezing Proof of the KMW Bound
Corinna Coupette, Christoph Lenzen
In their seminal paper from 2004, Kuhn, Moscibroda, and Wattenhofer (KMW) proved a hardness result for several fundamental graph problems in the LOCAL model: For any (randomized) a…