research
∙
08/16/2023
Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits
We explore the power of the unbounded Fan-Out gate and the Global Tunabl...
share
research
∙
11/13/2021
Classical and quantum dynamic programming for Subset-Sum and variants
Subset-Sum is an NP-complete problem where one must decide if a multiset...
research
∙
11/10/2020
On the cut dimension of a graph
Let G = (V,w) be a weighted undirected graph with m edges. The cut dimen...
research
∙
07/16/2020
Quantum algorithms for graph problems with cut queries
Let G be an n-vertex graph with m edges. When asked a subset S of vertic...
research
∙
11/05/2019
Discrete logarithm and Diffie-Hellman problems in identity black-box groups
We investigate the computational complexity of the discrete logarithm, t...
research
∙
07/11/2019
Quantum and Classical Algorithms for Approximate Submodular Function Minimization
Submodular functions are set functions mapping every subset of some grou...
research
∙
11/27/2018
A composition theorem for randomized query complexity via max conflict complexity
Let R_ϵ(·) stand for the bounded-error randomized query complexity with ...
research
∙
09/11/2018
Strategies for quantum races
We initiate the study of quantum races, games where two or more quantum ...
research
∙
06/25/2018
On learning linear functions from subset and its applications in quantum computing
Let F_q be the finite field of size q and let ℓ: F_q^n →F_q be a linear ...
research
∙
05/28/2018
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
The polynomial-time hierarchy (PH) has proven to be a powerful tool for ...
research
∙
01/07/2018
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...
research
∙
10/24/2017
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz
The complexity class PPA consists of NP-search problems which are reduci...
research
∙
08/02/2017