3 citations · 8 across the 12 of their papers we have counts for
4 papers · 1 filter
Orientation does not help with 3-coloring a grid in online-LOCAL
Thomas Boudier, Filippo Casagrande, Avinandan Das +4
The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know o…
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…
Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
Atsuya Hasegawa, François Le Gall, Augusto Modanese
We present relation problems whose input size is such that they can be solved with no communication for entanglement-assisted quantum communication models, but require q…
Strong and Hiding Distributed Certification of Bipartiteness
Benjamin Jauregui, Augusto Modanese, Pedro Montealegre +1
In this paper, we study the problem of certifying whether a graph is bipartite (i.e. -colorable) with a locally checkable proof (LCP) that is able to hide a -coloring from th…