research
∙
08/04/2023
Randomized and quantum query complexities of finding a king in a tournament
A tournament is a complete directed graph. It is well known that every t...
share
research
∙
05/08/2023
Tight Bounds for Quantum Phase Estimation and Related Problems
Phase estimation, due to Kitaev [arXiv'95], is one of the most fundament...
research
∙
11/30/2022
Lifting to Parity Decision Trees Via Stifling
We show that the deterministic decision tree complexity of a (partial) f...
research
∙
03/06/2022
Improved Quantum Query Upper Bounds Based on Classical Decision Trees
Given a classical query algorithm as a decision tree, when does there ex...
research
∙
12/29/2021
Exact quantum query complexity of computing Hamming weight modulo powers of two and three
We study the problem of computing the Hamming weight of an n-bit string ...
research
∙
07/25/2021
Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error
We investigate the randomized and quantum communication complexities of ...
research
∙
05/05/2021
One-way communication complexity and non-adaptive decision trees
We study the relationship between various one-way communication complexi...
research
∙
12/09/2020
Symmetry and Quantum Query-to-Communication Simulation
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean fun...
research
∙
12/03/2020
Tight Chang's-lemma-type bounds for Boolean functions
Chang's lemma (Duke Mathematical Journal, 2002) is a classical result wi...
research
∙
08/01/2020
On parity decision trees for Fourier-sparse Boolean functions
We study parity decision trees for Boolean functions. The motivation of ...
research
∙
02/19/2020
Improved Approximate Degree Bounds For k-distinctness
An open problem that is widely regarded as one of the most important in ...
research
∙
09/23/2019
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean f...
research
∙
06/02/2019
Approximate degree, secret sharing, and concentration phenomena
The ϵ-approximate degree deg_ϵ(f) of a Boolean function f is the least d...
research
∙
03/01/2019