3 papers
quant-ph2026
Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
Chandrima Kayal, Sayantan Sen, Dániel Szabó
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexit…
quant-ph2024
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…
cs.DS2024
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…