research
∙
01/14/2022
Cut query algorithms with star contraction
We study the complexity of determining the edge connectivity of a simple...
share
research
∙
11/02/2021
Finding the KT partition of a weighted graph in near-linear time
In a breakthrough work, Kawarabayashi and Thorup (J. ACM'19) gave a near...
research
∙
10/29/2021
A sublinear time quantum algorithm for s-t minimum cut on dense simple graphs
An s-t minimum cut in a graph corresponds to a minimum weight subset of ...
research
∙
09/05/2021
On the query complexity of connectivity with global queries
We study the query complexity of determining if a graph is connected wit...
research
∙
11/19/2020
Quantum query complexity of edge connectivity
The edge connectivity of a simple graph is the least number of edges who...
research
∙
11/10/2020
On the cut dimension of a graph
Let G = (V,w) be a weighted undirected graph with m edges. The cut dimen...
research
∙
07/16/2020
Quantum algorithms for graph problems with cut queries
Let G be an n-vertex graph with m edges. When asked a subset S of vertic...
research
∙
04/14/2020
The quantum query complexity of composition with a relation
The negative weight adversary method, ADV^±(g), is known to characterize...
research
∙
11/27/2018
A composition theorem for randomized query complexity via max conflict complexity
Let R_ϵ(·) stand for the bounded-error randomized query complexity with ...
research
∙
09/30/2018
Two new results about quantum exact learning
We present two new results about exact learning by quantum computers. Fi...
research
∙
09/11/2018
Strategies for quantum races
We initiate the study of quantum races, games where two or more quantum ...
research
∙
01/07/2018
On the randomised query complexity of composition
Let f⊆{0,1}^n×Ξ be a relation and g:{0,1}^m→{0,1,*} be a promise functio...
research
∙
08/02/2017