Персоналии: Подольский Владимир Владимирович, Список публикаций

RUS ENG

Полная версия

ПЕРСОНАЛИИ

Подольский Владимир Владимирович

Публикации

по годам




2024
1.	Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii, “Logical Languages Accepted by Transformer Encoders with Hard Attention”, The Twelfth International Conference on Learning Representations, {ICLR} 2024, Vienna, Austria, May 7-11, 2024, OpenReview.net, 2024, 1-11 https://openreview.net/forum?id=gbrHZq07mq
2.	Vladimir V. Podolskii and Dmitrii Sluch, “One-Way Communication Complexity of Partial XOR Functions”, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, LIPIcs, 2024, 116, 16 pp.
3.	Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii, “Towards Simpler Sorting Networks and Monotone Circuits for Majority”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, UK, LIPIcs, 2024, 50, 18 pp.
4.	Vladimir Podolskii, Victor Selivanov, “Complexity Aspects of the Extension of Wagner's Hierarchy to k-Partitions”, Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications, Electronic Proceedings in Theoretical Computer Science, 407, Open Publishing Association, 2024, 186–197

2023
5.	Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii, “Constant-Depth Sorting Networks”, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Leibniz Internat. Proc. in Inform., 251, 2023, 43, 19 pp.

2022
6.	Anastasiya Chistopolskaya, Vladimir V. Podolskii, “On the Decision Tree Complexity of Threshold Functions”, Theory Comput. Syst., 66 (2022), 1074–1098	2 ^[x]
7.	Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir Podolskii, Michael Zakharyaschev, “A tetrachotomy of ontology-mediated queries with a covering axiom”, Artif. Intell., 309 (2022), 103738, 46 pp.	1 ^[x]
8.	Vladimir Podolskii, Nikolay V. Proskurin, “Polynomial threshold functions for decision lists”, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz Internat. Proc. in Inform., 248, 2022, 52:1–52:12
9.	Alexander Kozachinskiy, Vladimir Podolskii, “Multiparty Karchmer–Wigderson games and threshold circuits”, Theory Comput., 18 (2022), 15, 33 pp.

2021
10.	Л. Бабаи, К. А. Хансен, В. В. Подольский, Сяомин Сюн, “Веса точных пороговых функций”, Изв. РАН. Сер. матем., 85:6 (2021), 5–26 ; L. Babai, K. A. Hansen, V. V. Podolskii, Xiaoming Sun, “Weights of exact threshold functions”, Izv. Math., 85:6 (2021), 1039–1059
11.	В. С. Атабекян, Л. Д. Беклемишев, В. М. Бухштабер, С. С. Гончаров, В. С. Губа, Ю. Л. Ершов, В. В. Козлов, И. Г. Лысёнок, С. П. Новиков, Ю. С. Осипов, М. Р. Пентус, В. В. Подольский, А. А. Разборов, В. А. Садовничий, А. Л. Семенов, А. Л. Таламбуца, Д. В. Трещев, Л. Н. Шеврин, “Сергей Иванович Адян (некролог)”, УМН, 76:1(457) (2021), 191–194 ; 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
12.	М. Н. Вялый, В. В. Подольский, А. А. Рубцов, Д. А. Шварц, А. Шень, Лекции по дискретной математике, Издательский дом Высшей Школы Экономики, 2021, 496 с. https://id.hse.ru/books/429927775.html	1 ^[x]

2020
13.	Fedor V. Fomin, Vladimir V. Podolskii, “CSR 2018 Special Issue on TOCS”, Theory Comput. Syst., 64 (2020), 1–2
14.	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	1 ^[x]
15.	Alexander Kozachinskiy, Vladimir Podolski, “Multiparty Karchmer – Wigderson Games and Threshold Circuits”, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany, Leibniz Internat. Proc. in Inform., 169, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020, 24, 23 pp.
16.	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
17.	Dima Grigoriev, Vladimir V. Podolskii, “Tropical Combinatorial Nullstellensatz and sparse polynomials”, Found. Comput. Math., 20 (2020), 753–781	5 ^[x]
18.	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.

2019
19.	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	2 ^[x]
20.	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

2018
21.	Dima Grigoriev, Vladimir V. Podolskii, “Tropical effective primary and dual nullstellensätze”, Discrete Comput. Geom., 59:3 (2018), 507–552	12 ^[x]
22.	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.	15 ^[x]
23.	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

2017
24.	Vladimir V. Podolskii, “Bounds in Ontology-Based Data Access via Circuit Complexity”, Theory Comput. Syst., 61:2 (2017), 464–493	1 ^[x]
25.	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), 2017, 201–216	5 ^[x]
26.	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	3 ^[x]
27.	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
28.	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	1 ^[x]
29.	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.

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

2015
31.	K. A. Hansen, V. V. Podolskii, “Polynomial threshold functions and Boolean threshold circuits”, Inform. and Comput., 240 (2015), 56–73	12 ^[x]
32.	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	17 ^[x]
33.	D. Grigoriev, V. V. Podolskii, “Tropical effective primary and dual Nullstellensä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
34.	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	2 ^[x]
35.	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	7 ^[x]

2014
36.	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	44 ^[x]
37.	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
38.	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

2013
39.	V. V. Podolskii, “Lower bound on weights of large degree threshold functions”, Log. Methods Comput. Sci., 9:2 (2013), 13, 17 pp.	2 ^[x]
40.	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/	4 ^[x]
41.	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
42.	K. A. Hansen, R. Ibsen-Jensen, V. V. Podolskii, E. Tsigaridas, “Patience of matrix games”, Discrete Appl. Math., 161:16 (2013), 2440–2459

2012
43.	V. V. Podolskii, “Exponential lower bound for bounded depth circuits with few threshold gates”, Inform. Process. Lett., 112:7 (2012), 267–271	3 ^[x]
44.	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	1 ^[x]
45.	K. A. Hansen, R. Ibsen-Jensen, V. V. Podolskii, E. P. Tsigaridas, Patience of matrix games, 2012, 32 pp., arXiv: 1206.1751
46.	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	20 ^[x]

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

2010
48.	В. В. Подольский, А. А. Шерстов, “Небольшое уменьшение степени многочлена с заданной знаковой функцией может экспоненциально увеличить его вес и длину”, Матем. заметки, 87:6 (2010), 885–899 ; 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	2 ^[x]
49.	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	16 ^[x]
50.	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	12 ^[x]

2009
51.	В. В. Подольский, “Перцептроны с большим весом”, Пробл. передачи информ., 45:1 (2009), 51–59 ; V. V. Podolskii, “Perceptrons of large weight”, Problems Inform. Transmission, 45:1 (2009), 46–53	18 ^[x]
52.	В. В. Подольский, А. А. Шерстов, “Уменьшение на единицу степени многочлена с заданной знаковой функцией может экспоненциально увеличить его вес и длину”, УМН, 64:5(389) (2009), 179–180 ; 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

2008
53.	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	10 ^[x]

2007
54.	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	2 ^[x]