
On the query complexity of connectivity with global queries
We study the query complexity of determining if a graph is connected wit...
read it

Quantum query complexity of edge connectivity
The edge connectivity of a simple graph is the least number of edges who...
read it

On the cut dimension of a graph
Let G = (V,w) be a weighted undirected graph with m edges. The cut dimen...
read it

Quantum algorithms for graph problems with cut queries
Let G be an nvertex graph with m edges. When asked a subset S of vertic...
read it

The quantum query complexity of composition with a relation
The negative weight adversary method, ADV^±(g), is known to characterize...
read it

A composition theorem for randomized query complexity via max conflict complexity
Let R_ϵ(·) stand for the boundederror randomized query complexity with ...
read it

Two new results about quantum exact learning
We present two new results about exact learning by quantum computers. Fi...
read it

Strategies for quantum races
We initiate the study of quantum races, games where two or more quantum ...
read it

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...
read it

Quadratically Tight Relations for Randomized Query Complexity
Let f:{0,1}^n →{0,1} be a Boolean function. The certificate complexity C...
read it
Troy Lee
is this you? claim profile