10 citations · 14 across the 5 of their papers we have counts for
7 papers
On parallel composition of zero-knowledge proofs with black-box quantum simulators
Rahul Jain, Alexandra Kolla, Gatis Midrijanis +1
Let L be a language decided by a constant-round quantum Arthur-Merlin (QAM) protocol with negligible soundness error and all but possibly the last message being classical. We prove…
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…