13 citations · 25 across the 18 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2019★ 1 cited
Information-theoretic lower bounds for quantum sorting
Jean Cardinal, Gwenaël Joret, Jérémie Roland
We analyze the quantum query complexity of sorting under partial information. In this problem, we are given a partially ordered set and are asked to identify a linear extension…
cs.CC2018
Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect
Jean Cardinal, Erik D. Demaine, David Eppstein +2
We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform…