Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries
To appear in Description Logics (DL) 2014
The price of query rewriting in ontology-based data access
Artificial Intelligence, Volume 213, August 2014, Pages 42–59
On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Bounded Chase
To appear in Logic in Computer Science (LICS) 2014
Polynomial threshold functions and Boolean threshold circuits
Mathematical Foundations of Computer Science (MFCS) 2013
Patience of matrix games
Discrete Appl. Math., 161:16-17 (2013), 2440–2459
Complexity of tropical and min-plus linear prevarieties
To appear in Computational Complexity, 2013, published online.
Exponential Lower Bounds and Separation for Query Rewriting
International Colloquium on Automata, Languages and Programming (ICALP), 2012.
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.
Exponential Lower Bound for Bounded Depth Circuits with Few Threshold Gates
Information Processing Letters, 112(7):267-271, 2012.
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.
Exact Threshold Circuits
In Proc. of 25th Annual IEEE Conference on Computational Complexity (CCC), pages 270-279, 2010.
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.
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.
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.