Persons
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
 
Podolskii, Vladimir Vladimirovich

Total publications: 44 (42)
in MathSciNet: 28 (26)
in zbMATH: 21 (21)
in Web of Science: 27 (26)
in Scopus: 38 (38)
Cited articles: 27
Citations in Math-Net.Ru: 12
Citations in MathSciNet: 49
Citations in Web of Science: 140
Citations in Scopus: 261
Presentations: 36

Number of views:
This page:5470
Abstract pages:2211
Full texts:553
References:162
Candidate of physico-mathematical sciences
E-mail:
Website: http://www.mi.ras.ru/~podolskii

Subject:

Computational complexity theory.


http://www.mathnet.ru/eng/person47204
https://scholar.google.com/citations?user=56S9XEsAAAAJ&hl=en
https://zbmath.org/authors/?q=ai:podolskii.vladimir-v
https://mathscinet.ams.org/mathscinet/MRAuthorID/864796
http://www.researcherid.com/rid/K-1430-2015
https://www.scopus.com/authid/detail.url?authorId=23092161300

Full list of publications:
| scientific publications | by years | by types | by times cited in WoS | by times cited in Scopus | common list |



   2021
1. L. Babai, K. A. Hansen, V. V. Podolskii, X. Sun, Izv. RAN. Ser. Mat., 85 (2021) (to appear)  mathnet
2. V. S. Atabekyan, L. D. Beklemishev, V. M. Buchstaber, S. S. Goncharov, V. S. Guba, Yu. L. Ershov, V. V. Kozlov, I. G. Lysenok, S. P. Novikov, Yu. S. Osipov, M. R. Pentus, V. V. Podolskii, A. A. Razborov, V. A. Sadovnichii, A. L. Semenov, A. L. Talambutsa, D. V. Treschev, L. N. Shevrin, “Sergei Ivanovich Adian (obituary)”, Russian Math. Surveys, 76:1 (2021), 177–181  mathnet  crossref  crossref  mathscinet  isi

   2020
3. Fedor V. Fomin, Vladimir V. Podolskii, “CSR 2018 Special Issue on TOCS”, Theory Comput. Syst., 64 (2020), 1–2  mathnet  crossref  mathscinet  zmath  isi  scopus;
4. Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir Podolskii, Michael Zakharyaschev, “A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom”, Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, IJCAI Organization, 2020, 403–413  crossref
5. Alexander Kozachinskiy, Vladimir Podolski, “Multiparty Karchmer – Wigderson Games and Threshold Circuits”, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany, Leibniz Internat. Proc. in Inform., 169, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020, 24 , 23 pp.  mathnet  crossref  scopus;
6. Anastasiya Chistopolskaya, Vladimir V. Podolskii, “On the Decision Tree Complexity of Threshold Functions”, Computer Science - Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 - July 3, 2020, Lecture Notes in Comput. Sci., 12159, Springer, Cham, 2020, 198–210  mathnet  crossref  scopus;
7. Dima Grigoriev, Vladimir V. Podolskii, “Tropical Combinatorial Nullstellensatz and sparse polynomials”, Found. Comput. Math., 20 (2020), 753–781  mathnet  crossref  mathscinet  isi  scopus;
8. Vladimir V. Podolskii, Alexander A. Sherstov, “Inner Product and Set Disjointness: Beyond Logarithmically Many Parties”, ACM Trans. Comput. Theory, 12:4 (2020), 26 , 28 pp.  mathnet  crossref  isi  scopus;

   2019
9. Alexander S. Kulikov, Vladimir V. Podolskii, “Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates”, Theory Comput. Syst., 63:5 (2019), 956–986  mathnet  crossref  mathscinet  zmath  isi  scopus
10. A. S. Kulikov, I. Mikhailin, A. Mokhov, V. V. Podolskii, “Complexity of Linear Operators”, 30th International Symposium on Algorithms and Computation (ISAAC 2019), Shanghai University of Finance and Economics, in ShanghaiShanghai; China; 8 December 2019 – 11 December 2019, Leibniz Internat. Proc. in Inform., 149, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019, 17, 1–12  mathnet  crossref  scopus;

   2018
11. Dima Grigoriev, Vladimir V. Podolskii, “Tropical effective primary and dual nullstellensätze”, Discrete Comput. Geom., 59:3 (2018), 507–552  mathnet  crossref  mathscinet  isi (cited: 3)  scopus (cited: 3)
12. Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev, “Ontology-mediated queries: Combined complexity and succinctness of rewritings via circuit complexity”, Journal of the ACM, 65:5 (2018), 28 , 51 pp.  mathnet  crossref  mathscinet  zmath  isi (cited: 8)  scopus (cited: 16)
13. Fedor V. Fomin, Vladimir V. Podolskii (eds.), Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings, Lecture Notes in Computer Science 10846, Springer, 2018 https://link.springer.com/book/10.1007  mathscinet

   2017
14. Vladimir V. Podolskii, “Bounds in Ontology-Based Data Access via Circuit Complexity”, Theory Comput. Syst., 61:2 (2017), 464–493  mathnet  crossref  mathscinet  isi (cited: 1)  elib  scopus (cited: 1)
15. 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 do 19 May 2017, Kod 127745), 2017, 201–216  crossref  mathscinet  isi (cited: 4)  scopus (cited: 14)
16. O. A. Gerasimova, S. P. Kikot, V. V. Podolskii, M. Zakharyaschev, “More on the Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom”, International Conference on Knowledge Engineering and the Semantic Web KESW 2017: Knowledge Engineering and Semantic Web, Commun. Comput. Inf. Sci., 786, Springer, 2017, 143–158  mathnet  crossref  mathscinet  elib  scopus (cited: 1)
17. A. S. Kulikov, V. V. Podolskii, “Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates”, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Leibniz Internat. Proc. in Inform., 66, no. 49, 2017, 1–14  mathnet  crossref  isi (cited: 4)  scopus (cited: 3)
18. D. Yu. Grigor'ev, V. V. Podolskii, “Tropical Combinatorial Nullstellensatz and Fewnomials Testing”, International Symposium on Fundamentals of Computation Theory FCT 2017: Fundamentals of Computation Theory, Lecture Notes in Comput. Sci., 10472, Springer, 2017, 284–297  mathnet  crossref  mathscinet  scopus (cited: 2)
19. O. Gerasimova, S. Kikot, V. Podolskii, M. Zakharyaschev, “On the data complexity of ontology-mediated queries with a covering axiom”, Proceedings of the 30th International Workshop on Description Logics (Montpellier, France, 18 July 2017 - 21 July 2017), CEUR Workshop Proceedings, 1879, CEUR-WS, 2017, 39 , 12 pp.  mathnet  scopus (cited: 2)

   2016
20. 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

   2015
21. 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 (cited: 6)  elib  scopus (cited: 2)
22. 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 (cited: 1)  crossref  mathscinet  zmath  isi (cited: 8)  scopus (cited: 11)
23. 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  zmath  scopus (cited: 5)
24. 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: 2)
25. 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: 3)  scopus (cited: 11)

   2014
26. 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: 34)  elib (cited: 13)  scopus (cited: 59)
27. 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  zmath
28. 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
29. 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  zmath  isi (cited: 1)  elib  scopus (cited: 3)
30. 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  zmath  isi (cited: 2)  scopus (cited: 4)
31. 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: 4)
32. K. A. Hansen, R. Ibsen-Jensen, V. V. Podolskii, E. Tsigaridas, “Patience of matrix games”, Discrete Appl. Math., 161:16 (2013), 2440–2459  mathnet  crossref  mathscinet  zmath  isi  elib  scopus

   2012
33. 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 (cited: 5)  elib (cited: 1)  scopus (cited: 5)
34. 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
35. K. A. Hansen, R. Ibsen-Jensen, V. V. Podolskii, E. P. Tsigaridas, Patience of matrix games, 2012 , 32 pp., arXiv: 1206.1751
36. 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: 14)  elib (cited: 11)  scopus (cited: 29)

   2011
37. Vladimir V. Podolskii, “Degree-uniform lower bound on the weights of polynomials with given sign function”, Proc. Steklov Inst. Math., 274 (2011), 231–246  mathnet  crossref  mathscinet  zmath  isi (cited: 1)  elib  elib  scopus (cited: 1)

   2010
38. 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  mathnet  crossref  crossref  mathscinet  isi (cited: 1)  elib (cited: 2)  elib (cited: 2)  scopus (cited: 2)
39. 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  isi (cited: 12)  scopus (cited: 36)
40. 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  zmath  isi (cited: 6)  scopus (cited: 10)

   2009
41. V. V. Podolskii, “Perceptrons of large weight”, Problems Inform. Transmission, 45:1 (2009), 46–53  mathnet  crossref  mathscinet  zmath  isi (cited: 13)  elib (cited: 13)  scopus (cited: 17)
42. 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  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib  scopus

   2008
43. 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  zmath  isi (cited: 9)  scopus (cited: 10)

   2007
44. 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: 5)  scopus (cited: 6)

Presentations in Math-Net.Ru
1. Lecture 7. Introduction to computational complexity theory
V. V. Podolskii
Introduction to computational complexity theory
October 18, 2021 10:00   
2. Lecture 6. Introduction to computational complexity theory
V. V. Podolskii
Introduction to computational complexity theory
October 11, 2021 10:00   
3. Lecture 5. Introduction to computational complexity theory
V. V. Podolskii
Introduction to computational complexity theory
October 4, 2021 10:00   
4. Lecture 4. Introduction to computational complexity theory
V. V. Podolskii
Introduction to computational complexity theory
September 27, 2021 10:00   
5. Lecture 3. Introduction to computational complexity theory
V. V. Podolskii
Introduction to computational complexity theory
September 20, 2021 10:00   
6. Lecture 2. Introduction to computational complexity theory
V. V. Podolskii
Introduction to computational complexity theory
September 13, 2021 10:00   
7. Lecture 1. Introduction to computational complexity theory
V. V. Podolskii
Introduction to computational complexity theory
September 6, 2021 10:00   
8. Макс-плюс многочлены и их корни
V. V. Podolskii

August 10, 2021 11:00
9. Max-plus polynomials and their roots
V. V. Podolskii
Steklov Mathematical Institute Seminar
January 21, 2021 16:00   
10. Max-plus polynomials and their roots
V. V. Podolskii
Scientific session of the Steklov Mathematical Institute of RAS dedicated to the results of 2020
November 25, 2020 11:00   
11. Занятие 7. NP-полнота следующих задач: NAE-3-SAT, 3-COL, SUBSET-SUM, CLIQUE, VERTEX-COVER
V. V. Podolskii
Introduction to computational complexity theory
November 3, 2020 16:15
12. Занятие 6. Соотношение между классами P и P/poly. Задача CIRCUIT-SAT, ее NP-полнота. Задача 3-SAT, ее NP-полнота. Задача IND-SET, ее NP-полнота
V. V. Podolskii
Introduction to computational complexity theory
October 27, 2020 16:15
13. Занятие 5. Булевых схемы. Примеры: сложение, умножение, связность. Верхняя и нижняя оценки сложности вычисления булевых функций булевыми схемами
V. V. Podolskii
Introduction to computational complexity theory
October 20, 2020 16:15   
14. Занятие 4. Класс NP, примеры. Соотношение с классами P и PSPACE. Недетерминированные машины Тьюринга, второе определение класса NP, эквивалентность определений. Полиномиальные сводимости, их основные свойства. NP-трудность и NP-полнота, их основные свойства
V. V. Podolskii
Introduction to computational complexity theory
October 13, 2020 16:15   
15. Занятие 3. Теоремы об иерархии по времени и по памяти
V. V. Podolskii
Introduction to computational complexity theory
October 6, 2020 16:15
16. Занятие 2. Связь одноленточных и многоленточных машин Тьюринга. Универсальная машина Тьюринга. Вычисления с ограничением на время и память. Классы P, PSPACE, EXP. Примеры полиномиально вычислимых функций и полиномиально разрешимых языков
V. V. Podolskii
Introduction to computational complexity theory
September 29, 2020 16:15   
17. Занятие 1. Машины Тьюринга, вычисление функций на машинах Тьюринга, лемма об очистке мусора, многоленточные машины Тьюринга
V. V. Podolskii
Introduction to computational complexity theory
September 22, 2020 16:15   
18. Занятие 0. Устройство курса правила оценивания. Краткий обзор основ сложности вычислений. Классы с ограничением на память. Класс PSPACE, его свойства. Задача TQBF является PSPACE-полной. PSPACE=NPSPACE
V. V. Podolskii
Introduction to computational complexity theory
September 15, 2020 16:15   
19. Макс-плюс многочлены и их корни
V. V. Podolskii
Knots and Representation Theory
February 25, 2020 18:30
20. Сложность вычисления некоторых функций коммуникационными протоколами с большим числом участников
V. V. Podolskii
Traditional winter session MIAN–POMI devoted to the topic "Mathematical logic"
December 24, 2018 17:30   
21. Lower bounds for databases augmented with logical theories
V. V. Podolskii
Conference «Contemporary Mathematics and its applications» dedicated to the results of research supported by the Russian Science Foundation grant 14-50-00005
November 19, 2018 15:10   
22. Сложность вычисления некоторых функций коммуникационными протоколамис большим числом участников
V. V. Podolskii
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
March 6, 2018 18:30
23. О корнях многочленов в мин-плюс алгебре
V. V. Podolskii
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
November 21, 2017 18:30
24. Ontology-based data access meets circuit complexity
V. V. Podolskii
Applied Mathematics Day
September 22, 2017 17:00   
25. Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
V. V. Podolskii
MIPT Interdepartmental Seminar on Discrete Mathematics
March 23, 2017 18:30
26. Polynomials in min-plus algebra and related algorithmic problems
V. V. Podolskii
Mathematical Logic, Algebra and Computation: A two-day conference dedicated to 85-th anniversary of S. I. Adian
July 19, 2016 15:50   
27. Оценки длин преобразований запросов к снабженным логической теорией базам данных
V. V. Podolskii
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
December 1, 2015 18:30
28. Bounds on the size of query rewritings in ontology based data access
V. V. Podolskii
Scientific session of the Steklov Mathematical Institute of RAS dedicated to the results of 2015
November 11, 2015 11:45   
29. Min-Plus polynomials and mean payoff games
V. V. Podolskii
Colloquium of the Faculty of Computer Science
April 30, 2015 16:40
30. Approximation of Boolean functions by polynomials
V. V. Podolskii
Colloquium of Steklov Mathematical Institute of Russian Academy of Sciences
April 2, 2015 16:00   
31. On the analog of Hilbert's Nullstellensatz for polynomials in algebraic system $(\mathbb{R}, \min, +)$
V. V. Podolskii
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
November 11, 2014 18:30
32. Threshold gates on the set $\{1,2\}$ and threshold circuits
V. V. Podolskii
Kolmogorov seminar on computational complexity and descriptive complexity
April 1, 2013 16:45
33. On the analog of Hilbert's Nullstellensatz theorem in the algebraic system $(\mathbb{R}, \min, +)$
V. V. Podolskii
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
March 26, 2013 18:30
34. On the representation of Boolean functions by sign functions of integer polynomials
V. V. Podolskii
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
December 4, 2012 18:30
35. On equations in $(\mathbb{Z}, \min, +)$ algebraic system
V. V. Podolskii
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
May 15, 2012 18:30
36. On some classes of Boolean schemes of bounded depth
V. V. Podolskii
Traditional Christmas session MIAN-POMI, 2009 "Logic and Theoretical Computer Science"
December 18, 2009 16:00   

Organisations
 
Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021