10 citations · 13 across the 2 of their papers we have counts for
2 papers
cs.CC2005★ 10 cited
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…
quant-ph2004★ 3 cited
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…