10 citations · 32 across the 9 of their papers we have counts for
3 papers · 1 filter
All Classical Adversary Methods are Equivalent for Total Functions
Andris Ambainis, Martins Kokainis, Krišjānis Prūsis +2
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity $\text{…
Zero-Error Affine, Unitary, and Probabilistic OBDDs
Rishat Ibrahimov, Kamil Khadiev, Krisjanis Prusis +2
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreo…
Exact Affine Counter Automata
Masaki Nakanishi, Kamil Khadiev, Krišjānis Prūsis +2
We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a la…