Gatis Midrijanis

activity

20032005

most citedThree lines proof of the lower bound for the matrix rigidity

10 citations · 13 across the 4 of their papers we have counts for

collaborators

Showing 2003 · quant-phShow all

2 papers · 2 filters

quant-ph2003

The Complexity of Probabilistic versus Quantum Finite Automata

Gatis Midrijanis

We present a language $L_{n}$ which is recognizable by a probabilistic finite automaton (PFA) with probability $1 - ε$ for all $ε > 0$ with $O (l o g^{2} n)$ states, with a deterministic fi…

quant-ph2003

Quantum lower bounds for the set equality problems

Gatis Midrijanis

The set equality problem is to decide whether two sets $A$ and $B$ are equal or disjoint, under the promise that one of these is the case. Some other problems, like the Graph Isomo…