research
∙
07/22/2022
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture
Classically, for many computational problems one can conclude time lower...
share
research
∙
03/30/2021
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→...
research
∙
07/06/2020
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
We study the quantum query complexity of two problems. First, we consi...
research
∙
04/19/2020
Quantum algorithms for computational geometry problems
We study quantum algorithms for problems in computational geometry, such...
research
∙
11/28/2019
Quantum Lower Bounds for 2D-Grid and Dyck Language
We show quantum lower bounds for two problems. First, we consider the pr...
research
∙
03/18/2019
Quadratic speedup for finding marked vertices by quantum walks
A quantum walk algorithm can detect the presence of a marked vertex on a...
research
∙
10/04/2018
On Block Sensitivity and Fractional Block Sensitivity
We investigate the relation between the block sensitivity bs(f) and frac...
research
∙
07/13/2018
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
In this paper we study quantum algorithms for NP-complete problems whose...
research
∙
12/18/2017
Understanding Quantum Algorithms via Query Complexity
Query complexity is a model of computation in which we have to compute a...
research
∙
09/26/2017