
On the cut dimension of a graph
Let G = (V,w) be a weighted undirected graph with m edges. The cut dimen...
read it

Quantum algorithms for graph problems with cut queries
Let G be an nvertex graph with m edges. When asked a subset S of vertic...
read it

Discrete logarithm and DiffieHellman problems in identity blackbox groups
We investigate the computational complexity of the discrete logarithm, t...
read it

Quantum and Classical Algorithms for Approximate Submodular Function Minimization
Submodular functions are set functions mapping every subset of some grou...
read it

A composition theorem for randomized query complexity via max conflict complexity
Let R_ϵ(·) stand for the boundederror randomized query complexity with ...
read it

Strategies for quantum races
We initiate the study of quantum races, games where two or more quantum ...
read it

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 ...
read it

Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
The polynomialtime hierarchy (PH) has proven to be a powerful tool for ...
read it

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...
read it

On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz
The complexity class PPA consists of NPsearch problems which are reduci...
read it

Quadratically Tight Relations for Randomized Query Complexity
Let f:{0,1}^n →{0,1} be a Boolean function. The certificate complexity C...
read it
Miklos Santha
is this you? claim profile