RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
 
Подольский Владимир Владимирович

Публикаций: 27
Научных статей: 27
в MathSciNet: 18
в zbMATH: 15
в Web of Science: 18
в Scopus: 24
Цитированных статей: 19
Ссылок в Math-Net.Ru: 9
Ссылок в MathSciNet: 19
Ссылок в Web of Science: 48
Ссылок в Scopus: 114
Лекций и докладов: 13

Статистика просмотров:
Эта страница:2040
Страницы публикаций:1152
Полные тексты:114
Списки литературы:92
кандидат физико-математических наук
E-mail:
Сайт: http://www.mi.ras.ru/~podolskii

Основные темы научной работы

Теория сложности вычислений.


http://www.mathnet.ru/rus/person47204
http://scholar.google.com/citations?user=56S9XEsAAAAJ&hl=ru
http://zbmath.org/authors/?q=ai:podolskii.vladimir-v
http://www.ams.org/mathscinet/search/author.html?return=viewitems&mrauthid=864796
http://www.researcherid.com/rid/K-1430-2015
http://www.scopus.com/authid/detail.url?authorId=23092161300

Полный список публикаций:
| по годам | по типам | по числу цитирований | научные публикации | общий список |


1. M. Bienvenu, S. Kikot, R. Kontchakov, V. V. Podolskii, V. Ryzhikov, M. Zakharyaschev, “The complexity of ontology-based data access with OWL2QL and bounded treewidth queries”, Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Volume Part F127745, 9 May 2017 (Chicago, United States, 14 May 2017 до 19 May 2017, Код 127745), 201–216

   2016
2. M. Bienvenu, S. Kikot, R. Kontchakov, V. Podolskii, M. Zakharyaschev, “Theoretically optimal datalog rewritings for OWL 2 QL ontology-mediated queries” (Cape Town, South Africa, 22 April 2016 – 25 April 2016), CEUR Workshop Proceedings, 1577, 2016 , arXiv: 1604.05258  mathnet  elib  scopus
3. Vladimir V. Podolskii, “Bounds in Ontology-Based Data Access via Circuit Complexity”, Theory Comput. Syst., 2016, 1–30  mathnet  crossref  isi  elib  scopus

   2015
4. K. A. Hansen, V. V. Podolskii, “Polynomial threshold functions and Boolean threshold circuits”, Inform. and Comput., 240 (2015), 56–73  mathnet  crossref  mathscinet  zmath  isi  elib  scopus (cited: 1)
5. Dima Grigoriev, Vladimir V. Podolskii, “Complexity of tropical and min-plus linear prevarieties”, Comput. Complexity, 24:1 (2015), 31–64 http://www.mpim-bonn.mpg.de/preblob/5202, arXiv: 1204.4578  mathnet (цит.: 1)  crossref  mathscinet (цит.: 2)  zmath  isi (цит.: 2)  scopus
6. D. Grigoriev, V. V. Podolskii, “Tropical effective primary and dual Nullstellensätze”, 32nd International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., 30, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015, 379–391  mathnet  crossref  mathscinet (цит.: 1)  scopus (цит.: 1)
7. V. V. Podolskii, “Circuit complexity meets ontology-based data access”, 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13–17, 2015, Proceedings, Lecture Notes in Comput. Sci., 9139, 2015, 7–26 , arXiv: 1506.01296  mathnet  crossref  mathscinet  zmath  scopus (cited: 1)
8. Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii, “Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results”, 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE, 2015, 317–328  mathnet  crossref  isi (cited: 1)  scopus (cited: 9)

   2014
9. 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, 213 (2014), 42–59  mathnet  crossref  mathscinet  zmath  isi (cited: 10)  elib (cited: 13)  scopus (cited: 25)
10. Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev, “On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Bounded Chase”, Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), ACM Digital Library, 2014, 57:1–57:10 , arXiv: 1401.4420
11. M. Bienvenu, S. Kikot, V. Podolskii, “Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries”, Description Logics 2014, CEUR Workshop Proceedings, 1193, 2014, 45–57 http://ceur-ws.org/Vol-1193/paper_43.pdf  mathnet  scopus (cited: 2)

   2013
12. V. V. Podolskii, “Lower bound on weights of large degree threshold functions”, Log. Methods Comput. Sci., 9:2 (2013), 13 , 17 pp.  mathnet  crossref  mathscinet (cited: 1)  zmath  isi  elib  scopus (cited: 1)
13. K. A. Hansen, V. V. Podolskii, “Polynomial threshold functions and Boolean threshold circuits”, Mathematical Foundations of Computer Science 2013, 38th International Symposium, MFCS 2013 (Klosterneuburg, Austria, August 26–30, 2013), Proceedings, Lecture Notes in Computer Science, 8087, Springer, Berlin–Heidelberg, 2013, 516–527 http://eccc.hpi-web.de/report/2013/021/  mathnet  crossref  mathscinet (cited: 1)  zmath  isi (cited: 2)  scopus (cited: 4)
14. 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  mathnet  crossref  mathscinet  zmath  isi  elib  scopus
15. S. Kikot, R. Kontchakov, V. Podolskii, M. Zakharyaschev, “Query Rewriting over Shallow Ontologies”, Description Logics 2013, Informal Proceedings of the 26th International Workshop on Description Logics (Ulm, Germany, July 23–26, 2013), CEUR Workshop Proceedings, 1014, 2013, 316–327  mathnet  scopus (cited: 3)

   2012
16. V. V. Podolskii, “Exponential lower bound for bounded depth circuits with few threshold gates”, Inform. Process. Lett., 112:7 (2012), 267–271  mathnet  crossref  mathscinet  zmath  isi  elib (cited: 1)  scopus (cited: 2)
17. V. V. Podolskii, “Lower bound on weights of large degree threshold functions”, How the World Computes, Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012 (Cambridge, UK, June 18–23, 2012), Proceedings, Lecture Notes in Comput. Sci., 7318, Springer–Berlin–Heidelberg, 2012, 599–608 , arXiv: 1204.2652  mathnet  crossref  mathscinet  zmath  scopus
18. K. A. Hansen, R. Ibsen-Jensen, V. V. Podolskii, E. P. Tsigaridas, Patience of matrix games, 2012 , 32 pp., arXiv: 1206.1751
19. S. Kikot, R. Kontchakov, V. V. Podolskii, M. Zakharyaschev, “Exponential lower bounds and separation for query rewriting”, Automata, Languages, and Programming, 39th International Colloquium, ICALP 2012 (Warwick, UK, July 9–13, 2012), Proceedings, Part II, Lecture Notes in Comput. Sci., 7392, Springer Berlin Heidelberg, 2012, 263–274 , arXiv: 1202.4193  mathnet  crossref  mathscinet  zmath  isi (cited: 10)  elib (cited: 11)  scopus (cited: 26)

   2011
20. В. В. Подольский, “Однородная по степени нижняя оценка на веса многочленов с заданной знаковой функцией”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК, М., 2011, 252–268  mathnet (цит.: 1)  mathscinet (цит.: 2)  elib; Vladimir V. Podolskii, “Degree-uniform lower bound on the weights of polynomials with given sign function”, Proc. Steklov Inst. Math., 274 (2011), 231–246  crossref  mathscinet  isi (cited: 1)  scopus (cited: 1)

   2010
21. В. В. Подольский, А. А. Шерстов, “Небольшое уменьшение степени многочлена с заданной знаковой функцией может экспоненциально увеличить его вес и длину”, Матем. заметки, 87:6 (2010), 885–899  mathnet (цит.: 1)  crossref  mathscinet (цит.: 2)  elib; V. V. Podolskii, A. A. Sherstov, “A Small Decrease in the Degree of a Polynomial with a Given Sign Function Can Exponentially Increase Its Weight and Length”, Math. Notes, 87:6 (2010), 860–873  crossref  mathscinet  isi (cited: 1)  elib (cited: 2)  scopus (cited: 2)
22. K. A. Hansen, V. V. Podolskii, “Exact threshold circuits”, Proc. of 25th Annual IEEE Conference on Computational Complexity (CCC), IEEE Computer Soc., Los Alamitos, CA, 2010, 270–279  crossref  mathscinet (cited: 1)  isi (cited: 4)  scopus (cited: 9)
23. L. Babai, K. A. Hansen, V. Podolskii, Sun Xiaoming, “Weights of exact threshold functions”, Mathematical foundations of computer science 2010, Proc. of 35th International Symposium on Mathematical Foundations of Computer Science (MFCS) (Brno, Czech Republic, 2010), Lecture Notes in Comput. Sci., 6281, Springer, Berlin, 2010, 66–77  crossref  mathscinet (cited: 3)  zmath  isi (cited: 2)  scopus (cited: 4)

   2009
24. В. В. Подольский, “Перцептроны с большим весом”, Пробл. передачи информ., 45:1 (2009), 51–59  mathnet (цит.: 6)  mathscinet (цит.: 2)  zmath; V. V. Podolskii, “Perceptrons of large weight”, Problems Inform. Transmission, 45:1 (2009), 46–53  crossref  mathscinet  zmath  isi (cited: 8)  elib (cited: 13)  scopus (cited: 12)
25. В. В. Подольский, А. А. Шерстов, “Уменьшение на единицу степени многочлена с заданной знаковой функцией может экспоненциально увеличить его вес и длину”, УМН, 64:5(389) (2009), 179–180  mathnet  crossref  mathscinet  zmath  adsnasa  elib; V. V. Podolskii, A. A. Sherstov, “Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length”, Russian Math. Surveys, 64:5 (2009), 950–951  crossref  mathscinet  zmath  adsnasa  isi  elib  scopus

   2008
26. V. V. Podolskii, “A uniform lower bound on weights of perceptrons”, Computer science—theory and applications, Lecture Notes in Comput. Sci., 5010, Springer, Berlin, 2008, 261–272  crossref  mathscinet (cited: 4)  zmath  isi (cited: 5)  scopus (cited: 7)

   2007
27. V. V. Podolskii, “Perceptrons of large weight”, Computer science — theory and applications, Proceedings of the Second International Symposium on Computer Science in Russia, CSR 2007 (Ekaterinburg, Russia, 2007), Lecture Notes in Comput. Sci., 4649, 2007, 328–336  crossref  zmath  isi (cited: 1)  scopus (cited: 4)

Доклады и лекции в базе данных Math-Net.Ru
1. Ontology-based data access meets circuit complexity
V. V. Podolskii
Applied Mathematics Day
22 сентября 2017 г. 17:00
2. Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
В. В. Подольский
Межкафедральный семинар МФТИ по дискретной математике
23 марта 2017 г. 18:30
3. Polynomials in min-plus algebra and related algorithmic problems
В. В. Подольский
Математическая логика, алгебра и вычислимость: двухдневная конференция, посвященная 85-летию С. И. Адяна
19 июля 2016 г. 15:50   
4. Оценки длин преобразований запросов к снабженным логической теорией базам данных
В. В. Подольский
Семинар отдела математической логики «Алгоритмические вопросы алгебры и логики»
1 декабря 2015 г. 18:30
5. Оценки длин переформулировок запросов к снабженным логической теорией базам данных
В. В. Подольский
Научная сессия МИАН, посвященная подведению итогов 2015 года
11 ноября 2015 г. 11:45   
6. Мин-плюс многочлены и циклические игры
В. В. Подольский
Коллоквиум Факультета компьютерных наук НИУ ВШЭ
30 апреля 2015 г. 16:40   
7. Приближение булевых функций многочленами
В. В. Подольский
Общеинститутский семинар «Коллоквиум МИАН»
2 апреля 2015 г. 16:00   
8. Об одном аналоге известной теоремы Гильберта о нулях для многочленов в алгебраической системе $(\mathbb{R}, \min, +)$
В. В. Подольский
Семинар отдела математической логики «Алгоритмические вопросы алгебры и логики»
11 ноября 2014 г. 18:30
9. Пороговые элементы на множестве $\{1,2\}$ и пороговые схемы
В. В. Подольский
Колмогоровский семинар по сложности вычислений и сложности определений
1 апреля 2013 г. 16:45
10. Об аналоге теоремы Гильберта о нулях в алгебраической системе $(\mathbb{R}, \min, +)$.
В. В. Подольский
Семинар отдела математической логики «Алгоритмические вопросы алгебры и логики»
26 марта 2013 г. 18:30
11. О реализации булевых функций знаковыми функциями целочисленных многочленов
В. В. Подольский
Семинар отдела математической логики «Алгоритмические вопросы алгебры и логики»
4 декабря 2012 г. 18:30
12. Об уравнениях в алгебраической системе $(\mathbb Z,\min, +)$
В. В. Подольский
Семинар отдела математической логики «Алгоритмические вопросы алгебры и логики»
15 мая 2012 г. 18:30
13. О некоторых классах пороговых булевых схем ограниченной глубины
В. В. Подольский
Традиционная новогодняя сессия МИАН-ПОМИ, 2009 «Логика и теоретическая информатика»
18 декабря 2009 г. 16:00   

Организации
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017