9 citations · 22 across the 13 of their papers we have counts for
5 papers · 1 filter
Quantum property testing in sparse directed graphs
Simon Apers, Frédéric Magniez, Sayantan Sen +1
We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the out…
Directed st-connectivity with few paths is in quantum logspace
Simon Apers, Roman Edenhofer
We present a -procedure to count -paths on directed graphs for which we are promised that there are at most polynomially many paths starting in …
On computing approximate Lewis weights
Simon Apers, Sander Gribling, Aaron Sidford
In this note we provide and analyze a simple method that given an matrix, outputs approximate -Lewis weights, a natural measure of the importance of the rows w…
Quantum walks, the discrete wave equation and Chebyshev polynomials
Simon Apers, Laurent Miclo
A quantum walk is the quantum analogue of a random walk. While it is relatively well understood how quantum walks can speed up random walk hitting times, it is a long-standing open…
Holey graphs: very large Betti numbers are testable
Dániel Szabó, Simon Apers
We show that the graph property of having a (very) large -th Betti number for constant is testable with a constant number of queries in the dense graph model. More spe…