10 citations · 13 across the 4 of their papers we have counts for
Showing 2005Show all
2 papers · 1 filter
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-ph2005
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…