Edit Profile (opens in new tab) Podol’skiĭ, Vladimir Vladimirovich Compute Distance To: Compute Author ID: podolskii.vladimir-v Published as: Podolskii, Vladimir V.; Podolskii, Vladimir; Podolskii, V. V.; Podol’skii, V. V. more...less Homepage: http://www.mi.ras.ru/~podolskii External Links: MGP · Math-Net.Ru Documents Indexed: 35 Publications since 2007 2 Contributions as Editor Co-Authors: 35 Co-Authors with 26 Joint Publications 2,022 Co-Co-Authors all top 5 Co-Authors 9 single-authored 6 Kikot, Stanislav 5 Grigor’ev, Dmitriĭ Yur’evich 5 Hansen, Kristoffer Arnsfelt 5 Zakharyaschev, Michael Viktorovich 4 Kontchakov, Roman 3 Sherstov, Alexander A. 2 Babai, László 2 Bienvenu, Meghyn 2 Chistopolskaya, Anastasiya 2 Fomin, Fedor V. 2 Kozachinskiy, Alexander 2 Kulikov, Alexander S. 2 Sun, Xiaoming 1 Atabekyan, Varuzhan S. 1 Beklemishev, Lev D. 1 Bukhshtaber, Viktor Matveevich 1 Ershov, Yuriĭ Leonidovich 1 Gerasimova, Olga 1 Goncharov, Sergeĭ Savost’yanovich 1 Gottlob, Georg 1 Guba, Victor S. 1 Ibsen-Jensen, Rasmus 1 Kozlov, Valeriĭ Vasil’evich 1 Kurucz, Agi 1 Lysenok, Igor’ Geront’evich 1 Novikov, Sergeĭ Petrovich 1 Osipov, Yuriĭ Sergeevich 1 Pentus, Mati 1 Razborov, Aleksandr Aleksandrovich 1 Sadovnichiĭ, Viktor Antonovich 1 Schwentick, Thomas 1 Semënov, Alekseĭ L’vovich 1 Shevrin, Lev Naumovich 1 Talambutsa, Alexey L. 1 Treshchev, Dmitriĭ Valer’evich 1 Tsigaridas, Elias P. all top 5 Serials 4 Theory of Computing Systems 2 Artificial Intelligence 2 Russian Mathematical Surveys 1 Discrete Applied Mathematics 1 Information Processing Letters 1 Mathematical Notes 1 Problems of Information Transmission 1 Discrete & Computational Geometry 1 Information and Computation 1 Computational Complexity 1 Izvestiya: Mathematics 1 Journal of the ACM 1 Foundations of Computational Mathematics 1 Lecture Notes in Computer Science 1 Proceedings of the Steklov Institute of Mathematics 1 Logical Methods in Computer Science 1 Theory of Computing 1 ACM Transactions on Computation Theory all top 5 Fields 32 Computer science (68-XX) 15 Information and communication theory, circuits (94-XX) 4 Algebraic geometry (14-XX) 2 General and overarching topics; collections (00-XX) 2 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 History and biography (01-XX) 1 Combinatorics (05-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Field theory and polynomials (12-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 20 Publications have been cited 84 times in 62 Documents Cited by ▼ Year ▼ The price of query rewriting in ontology-based data access. Zbl 1390.68246Gottlob, Georg; Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir; Schwentick, Thomas; Zakharyaschev, Michael 10 2014 Complexity of tropical and MIN-plus linear prevarieties. Zbl 1326.15039Grigoriev, Dima; Podolskii, Vladimir V. 10 2015 Perceptrons of large weight. Zbl 1171.68585Podolskii, V. V. 9 2009 Polynomial threshold functions and Boolean threshold circuits. Zbl 1312.68089Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V. 9 2015 Weights of exact threshold functions. Zbl 1287.94129Babai, László; Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V.; Sun, Xiaoming 5 2010 A uniform lower bound on weights of perceptrons. Zbl 1142.94400Podolskii, Vladimir V. 5 2008 Tropical effective primary and dual Nullstellensätze. Zbl 1356.14058Grigoriev, Dima; Podolskii, Vladimir V. 5 2015 Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity. Zbl 1426.68075Bienvenu, Meghyn; Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir V.; Zakharyaschev, Michael 4 2018 Computing majority by constant depth majority circuits with low fan-in gates. Zbl 1402.68100Kulikov, Alexander S.; Podolskii, Vladimir V. 4 2017 Exponential lower bounds and separation for query rewriting. Zbl 1367.68089Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir; Zakharyaschev, Michael 4 2012 On the succinctness of query rewriting over shallow ontologies. Zbl 1401.68316Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir V.; Zakharyaschev, Michael 3 2014 Tropical effective primary and dual Nullstellensätze. Zbl 1420.14140Grigoriev, Dima; Podolskii, Vladimir V. 3 2018 Tree-like queries in OWL 2 QL: succinctness and complexity results. Zbl 1401.68058Bienvenu, Meghyn; Kikot, Stanislav; Podolskii, Vladimir 2 2015 Tropical combinatorial Nullstellensatz and fewnomials testing. Zbl 06810961Grigoriev, Dima; Podolskii, Vladimir V. 2 2017 Exponential lower bound for bounded depth circuits with few threshold gates. Zbl 1237.68091Podolskii, Vladimir V. 2 2012 Polynomial threshold functions and Boolean threshold circuits. Zbl 1312.68088Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V. 2 2013 Circuit complexity meets ontology-based data access. Zbl 1464.68096Podolskii, Vladimir V. 2 2015 Tropical combinatorial Nullstellensatz and sparse polynomials. Zbl 1455.14126Grigoriev, Dima; Podolskii, Vladimir V. 1 2020 Lower bound on weights of large degree threshold functions. Zbl 1297.68086Podolskii, Vladimir V. 1 2013 Perceptrons of large weight. Zbl 1188.94053Podolskii, Vladimir V. 1 2007 Tropical combinatorial Nullstellensatz and sparse polynomials. Zbl 1455.14126Grigoriev, Dima; Podolskii, Vladimir V. 1 2020 Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity. Zbl 1426.68075Bienvenu, Meghyn; Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir V.; Zakharyaschev, Michael 4 2018 Tropical effective primary and dual Nullstellensätze. Zbl 1420.14140Grigoriev, Dima; Podolskii, Vladimir V. 3 2018 Computing majority by constant depth majority circuits with low fan-in gates. Zbl 1402.68100Kulikov, Alexander S.; Podolskii, Vladimir V. 4 2017 Tropical combinatorial Nullstellensatz and fewnomials testing. Zbl 06810961Grigoriev, Dima; Podolskii, Vladimir V. 2 2017 Complexity of tropical and MIN-plus linear prevarieties. Zbl 1326.15039Grigoriev, Dima; Podolskii, Vladimir V. 10 2015 Polynomial threshold functions and Boolean threshold circuits. Zbl 1312.68089Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V. 9 2015 Tropical effective primary and dual Nullstellensätze. Zbl 1356.14058Grigoriev, Dima; Podolskii, Vladimir V. 5 2015 Tree-like queries in OWL 2 QL: succinctness and complexity results. Zbl 1401.68058Bienvenu, Meghyn; Kikot, Stanislav; Podolskii, Vladimir 2 2015 Circuit complexity meets ontology-based data access. Zbl 1464.68096Podolskii, Vladimir V. 2 2015 The price of query rewriting in ontology-based data access. Zbl 1390.68246Gottlob, Georg; Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir; Schwentick, Thomas; Zakharyaschev, Michael 10 2014 On the succinctness of query rewriting over shallow ontologies. Zbl 1401.68316Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir V.; Zakharyaschev, Michael 3 2014 Polynomial threshold functions and Boolean threshold circuits. Zbl 1312.68088Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V. 2 2013 Lower bound on weights of large degree threshold functions. Zbl 1297.68086Podolskii, Vladimir V. 1 2013 Exponential lower bounds and separation for query rewriting. Zbl 1367.68089Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir; Zakharyaschev, Michael 4 2012 Exponential lower bound for bounded depth circuits with few threshold gates. Zbl 1237.68091Podolskii, Vladimir V. 2 2012 Weights of exact threshold functions. Zbl 1287.94129Babai, László; Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V.; Sun, Xiaoming 5 2010 Perceptrons of large weight. Zbl 1171.68585Podolskii, V. V. 9 2009 A uniform lower bound on weights of perceptrons. Zbl 1142.94400Podolskii, Vladimir V. 5 2008 Perceptrons of large weight. Zbl 1188.94053Podolskii, Vladimir V. 1 2007 all cited Publications top 5 cited Publications all top 5 Cited by 100 Authors 12 Podol’skiĭ, Vladimir Vladimirovich 11 Grigor’ev, Dmitriĭ Yur’evich 3 Hansen, Kristoffer Arnsfelt 3 Zakharyaschev, Michael Viktorovich 2 Amendola, Giovanni 2 Bodirsky, Manuel 2 Bun, Mark 2 Cuenca Grau, Bernardo 2 Gottlob, Georg 2 Kikot, Stanislav 2 Kontchakov, Roman 2 Kostylev, Egor V. 2 Leone, Nicola 2 Mamino, Marcello 2 Manna, Marco 2 Ortiz, Magdalena 2 Servedio, Rocco A. 2 Sherstov, Alexander A. 2 Sun, Xiaoming 2 Thaler, Justin 2 Vorob’ëv, Nikolaĭ N. jun. 2 Williams, Richard Ryan 2 Zamaraeva, Elena 2 Žunić, Joviša D. 1 Ahmetaj, Shqiponja 1 Amano, Kazuyuki 1 Artale, Alessandro 1 Babai, László 1 Bajpai, Swapnam 1 Baldi, Pierre 1 Benedikt, Michael A. 1 Bienvenu, Meghyn 1 Calautti, Marco 1 Chattopadhyay, Arkadev 1 Chen, Fangyue 1 Chen, Lijie 1 Chen, Xue 1 Davydow, Alex 1 De, Anindya K. 1 Engels, Christian 1 Garg, Mohit 1 Gaubert, Stéphane 1 Gerasimova, Olga 1 Glimm, Birte 1 Görlach, Paul 1 Greco, Sergio 1 Hajnal, Péter 1 He, Qinbin 1 Horrocks, Ian 1 Hu, Guangda 1 Ibsen-Jensen, Rasmus 1 Kaminski, Mark 1 Kawana, Akihiro 1 Kazakov, Yevgeny 1 Koch, Christoph T. 1 Kombarov, Yuriy A. 1 Konstantinidis, George 1 Kovtunova, Alisa 1 Krishan, Vaibhav 1 Kulikov, Alexander S. 1 Kurucz, Agi 1 Kush, Deepanshu 1 Kuznetsov, Stepan L’vovich 1 Limaye, Nutan 1 Litvinov, Grigory Lazarevich 1 Liu, Zhi-Hao 1 Loho, Georg 1 Maccaig, Marie 1 Makino, Kazuhisa 1 Mande, Nikhil S. 1 Matsui, Tomomi 1 Molinaro, Cristian 1 Nikolaou, Charalampos 1 Oztop, Erhan 1 Pantović, Jovanka 1 Perri, Tal 1 Pieris, Andreas 1 Prokić, Ivan 1 Rowen, Louis Halle 1 Ryzhikov, Vladislav 1 Sakai, Takayuki 1 Schwentick, Thomas 1 Seto, Kazuhisa 1 Sezener, Can Eren 1 Shayevitz, Ofer 1 Šimkus, Mantas 1 Srinivasan, Srikanth 1 Tamaki, Suguru 1 Tan, Liyang 1 Teruyama, Junichi 1 Tran, Trung-Kien 1 Trubitsyna, Irina 1 Tsigaridas, Elias P. 1 Turán, Gyorgy 1 Veltri, Pierfrancesco 1 Vershynin, Roman 1 Viola, Emanuele 1 Weinberger, Nir 1 Wolter, Frank 1 Zhang, Leon all top 5 Cited in 33 Serials 7 Artificial Intelligence 3 Journal of Symbolic Computation 3 Information and Computation 3 Computational Complexity 3 Theory of Computing Systems 2 SIAM Journal on Computing 2 Discrete & Computational Geometry 2 SIAM Journal on Discrete Mathematics 2 Proceedings of the Steklov Institute of Mathematics 2 Theory of Computing 1 Computers & Mathematics with Applications 1 Discrete Applied Mathematics 1 Mathematical Notes 1 Moscow University Mathematics Bulletin 1 Journal of Computer and System Sciences 1 Theoretical Computer Science 1 Theory and Decision 1 Advances in Applied Mathematics 1 Combinatorica 1 Probability Theory and Related Fields 1 Algorithmica 1 Neural Computation 1 International Journal of Algebra and Computation 1 Applicable Algebra in Engineering, Communication and Computing 1 International Journal of Bifurcation and Chaos in Applied Sciences and Engineering 1 The Electronic Journal of Combinatorics 1 Izvestiya: Mathematics 1 Foundations of Computational Mathematics 1 Theory and Practice of Logic Programming 1 Journal of Multiple-Valued Logic and Soft Computing 1 Journal of Algebra and its Applications 1 Arnold Mathematical Journal 1 SIAM Journal on Mathematics of Data Science all top 5 Cited in 17 Fields 45 Computer science (68-XX) 17 Information and communication theory, circuits (94-XX) 13 Algebraic geometry (14-XX) 5 Combinatorics (05-XX) 4 Mathematical logic and foundations (03-XX) 4 Order, lattices, ordered algebraic structures (06-XX) 4 Convex and discrete geometry (52-XX) 4 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 3 Linear and multilinear algebra; matrix theory (15-XX) 3 Associative rings and algebras (16-XX) 3 Operations research, mathematical programming (90-XX) 2 Commutative algebra (13-XX) 2 Probability theory and stochastic processes (60-XX) 1 Number theory (11-XX) 1 Field theory and polynomials (12-XX) 1 Numerical analysis (65-XX) 1 Biology and other natural sciences (92-XX) Citations by Year