Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dfc/2012/Program2/Podolskii_publications.pdf Дата изменения: Tue Oct 16 11:18:50 2012 Дата индексирования: Mon Feb 4 19:43:28 2013 Кодировка: Поисковые слова: п п п п п

Publication List
Vladimir Podolskii

1. V. 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, Lecture Notes in Computer Science 4649, pp. 328-336, 2007. 2. V. V. Podolskii. A Uniform Lower Bound on Weights of Perceptrons. Proceedings of the Steklov Institute of Mathematics, 274: 252268, 2011. Preliminary version of this paper appeared in Proceedings, Third International Symposium on Computer Science in Russia, Lecture Notes in Computer Science 5010, pp. 261-272, 2008. 3. V. V. Podolskii, A. A. Sherstov. A small decrease in the degree of a p olynomial with a given sign function can exp onentially increase its weight and length. In Mathematical Notes, 2010, 87(6), 860-873. Preliminary version of this paper appeared in RUSS MATH SURV, 64 (5), 950-951, 2009. 4. Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii. Exact threshold circuits. In Proc. of 25th Annual IEEE Conference on Computational Complexity (CCC), pages 270-279, 2010. 5. 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. 6. Vladimir V. Podolskii. Exp onential Lower Bound for Bounded Depth Circuits with Few Threshold Gates. Information Processing Letters, 112(7):267-271, 2012. 7. Vladimir V. Podolskii. Lower Bound on Weights of Large Degree Threshold Functions. In Proceedings of Computability in Europe Conference (CiE), Lecture Notes in Computer Science 7318, pp. 599-608, 2012. Preliminary version of this paper can be found at http://arxiv.org/ abs/1204.2652. 8. Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev. Exp onential Lower Bounds and Separation for Query Rewriting. In Proceedings of the 39th International Col loquium on Automata, Languages and Programming (ICALP), Lecture Notes

1


in Computer Science, 7392, pp. 263-274, 2012. Preliminary version of this paper can be found at http://arxiv.org/abs/1202.4193. 9. Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Vladimir V. Podolskii, Elias P. Tsigaridas. Patience of Matrix Games. http://arxiv.org/abs/1206.1751, 2012. 10. Dima Grigoriev, Vladimir V. Podolskii. Complexity of tropical and min-plus linear prevarieties. MPIM preprint 2012-23, 2012. http://arxiv.org/abs/1204.4578.

2