
A note about claw function with a small range
In the claw detection problem we are given two functions f:D→ R and g:D→...
read it

Quantum Lower and Upper Bounds for 2DGrid and Dyck Language
We study the quantum query complexity of two problems. First, we consi...
read it

Quantum algorithms for computational geometry problems
We study quantum algorithms for problems in computational geometry, such...
read it

Quantum Lower Bounds for 2DGrid and Dyck Language
We show quantum lower bounds for two problems. First, we consider the pr...
read it

Quadratic speedup for finding marked vertices by quantum walks
A quantum walk algorithm can detect the presence of a marked vertex on a...
read it

On Block Sensitivity and Fractional Block Sensitivity
We investigate the relation between the block sensitivity bs(f) and frac...
read it

Quantum Speedups for ExponentialTime Dynamic Programming Algorithms
In this paper we study quantum algorithms for NPcomplete problems whose...
read it

Understanding Quantum Algorithms via Query Complexity
Query complexity is a model of computation in which we have to compute a...
read it

All Classical Adversary Methods are Equivalent for Total Functions
We show that all known classical adversary lower bounds on randomized qu...
read it
Andris Ambainis
is this you? claim profile