research
∙
06/26/2020
Quantum Communication Complexity of Distribution Testing
The classical communication complexity of testing closeness of discrete ...
share
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
∙
08/07/2019
Testing convexity of functions over finite domains
We establish new upper and lower bounds on the number of queries require...
research
∙
01/26/2018
Adaptive Lower Bound for Testing Monotonicity on the Line
In the property testing model, the task is to distinguish objects posses...
research
∙
12/29/2017
Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
In this paper, we study quantum query complexity of the following rather...
research
∙
12/29/2017
Quantum Lower Bound for a Tripartite Version of the Hidden Shift Problem
In this paper, we prove a polynomial lower bound of Ω(n^1/3) on the quan...
research
∙
10/24/2017