22 citations · 66 across the 20 of their papers we have counts for
25 papers
One-Way Communication Complexity of Partial XOR Functions
Vladimir V. Podolskii, Dmitrii Sluch
Boolean function for is an XOR function if for some function on input bits, where is a bit-wise XOR. XOR functio…
Constant-Depth Sorting Networks
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii
In this paper, we address sorting networks that are constructed from comparators of arity . That is, in our setting the arity of the comparators -- or, in other words, the n…
Polynomial Threshold Functions for Decision Lists
Vladimir Podolskii, Nikolay V. Proskurin
For a Boolean function is a polynomial threshold function (PTF) of degree and weight if there is a polynomial with int…
Deciding boundedness of monadic sirups
Stanislav Kikot, Agi Kurucz, Vladimir Podolskii +1
We show that deciding boundedness (aka FO-rewritability) of monadic single rule datalog programs (sirups) is 2Exp-hard, which matches the upper bound known since 1988 and finally s…
A tetrachotomy of ontology-mediated queries with a covering axiom
Olga Gerasimova, Stanislav Kikot, Agi Kurucz +2
Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description logic ontologies and constructing their optimal rewritings to…
Multiparty Karchmer-Wigderson Games and Threshold Circuits
Alexander Kozachinskiy, Vladimir Podolskii
We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of thre…