10 citations · 13 across the 4 of their papers we have counts for
6 papers
Three lines proof of the lower bound for the matrix rigidity
Gatis Midrijanis
The rigidity of a matrix describes the minimal number of entries one has to change to reduce matrix's rank to r. We give very simple combinatorial proof of the lower bound for the…
On Randomized and Quantum Query Complexities
Gatis Midrijanis
We study randomized and quantum query (a.k.a. decision tree) complexity for all total Boolean functions, with emphasis to derandomization and dequantization (removing quantumness f…
Exact quantum query complexity for total Boolean functions
Gatis Midrijanis
We will show that if there exists a quantum query algorithm that exactly computes some total Boolean function f by making T queries, then there is a classical deterministic algorit…
A polynomial quantum query lower bound for the set equality problem
Gatis Midrijanis
The set equality problem is to tell whether two sets and are equal or disjoint under the promise that one of these is the case. This problem is related to the Graph Isomorp…
The Complexity of Probabilistic versus Quantum Finite Automata
Gatis Midrijanis
We present a language which is recognizable by a probabilistic finite automaton (PFA) with probability for all with states, with a deterministic fi…
Quantum lower bounds for the set equality problems
Gatis Midrijanis
The set equality problem is to decide whether two sets and are equal or disjoint, under the promise that one of these is the case. Some other problems, like the Graph Isomo…