Papers
Meghyn Bienvenu, Stanislav Kikot and Vladimir Podolskii,
Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries
To appear in Description Logics (DL) 2014
arxiv, full version

Georg Gottlob, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Thomas Schwentick, Michael Zakharyaschev,
The price of query rewriting in ontology-based data access
Artificial Intelligence, Volume 213, August 2014, Pages 42–59
link

Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii and Michael Zakharyaschev,
On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Bounded Chase
To appear in Logic in Computer Science (LICS) 2014
arxiv

K. A. Hansen, V. V. Podolskii,
Polynomial threshold functions and Boolean threshold circuits
Mathematical Foundations of Computer Science (MFCS) 2013
full version

K. A. Hansen, R. I. Jensen, V. V. Podolskii, E. P. Tsigaridas,
Patience of matrix games
Discrete Appl. Math., 161:16-17 (2013), 2440–2459
link

Dima Grigoriev and Vladimir Podolskii,
Complexity of tropical and min-plus linear prevarieties
To appear in Computational Complexity, 2013, published online.
link

Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii and Michael Zakharyaschev,
Exponential Lower Bounds and Separation for Query Rewriting
International Colloquium on Automata, Languages and Programming (ICALP), 2012.
arxiv

Vladimir Podolskii,
Lower Bound on Weights of Large Degree Threshold Functions
Log. Methods Comput. Sci., 9:2 (2013), 13, 17 pp. Preliminary version appeared at Computability in Europe Conference (CiE), 2012.
link

Vladimir Podolskii,
Exponential Lower Bound for Bounded Depth Circuits with Few Threshold Gates
Information Processing Letters, 112(7):267-271, 2012.
link

Laszlo Babai, Kristoffer Arnsfelt Hansen, Vladimir Podolskii and Xiaoming Sun,
Weights of Exact Threshold Functions
In Proc. of 35th International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science, 2010, Volume 6281/2010, 66-77.
Extended version

Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii,
Exact Threshold Circuits
In Proc. of 25th Annual IEEE Conference on Computational Complexity (CCC), pages 270-279, 2010.

Vladimir V. Podolskii and Alexander A. Sherstov,
A Small Decrease in the Degree of a Polynomial with a Given Sign Function Can Exponentially Increase Its Weight and Length
Mathematical Notes, Volume 87, Numbers 5-6, 860-873, 2010. Preliminary version appeared in RUSS MATH SURV, 2009, 64 (5), 950–951.
link(English), link(Russian)

Vladimir V. Podolskii,
Degree-uniform lower bound on the weights of polynomials with given sign function
Proceedings of the Steklov Institute of Mathematics, Volume 274, Number 1, 231-246, 2011. Preliminary version appeared in Proceedings, Third International Symposium on Computer Science in Russia (CSR), Lecture Notes in Computer Science 5010, pp. 261-272, 2008.
link(English), link(Russian)

Vladimir V. Podolskii,
Perceptrons of large weight
Problems of Information Transmission, v. 45(1), pp. 46-53, 2009. Preliminary version of this paper appeared in Proceedings of the Second International Symposium on Computer Science in Russia (CSR), Lecture Notes in Computer Science 4649, pp. 328-336, 2007.
link
Home