Vladimir V. Podolskii

Publication Activity (10 Years)

Years Active: 2007-2024
Publications (10 Years): 56

Top Topics

Bounded Treewidth

Combined Complexity

Query Rewriting

Top Venues

Electron. Colloquium Comput. Complex.

Description Logics

Theory Comput. Syst.

Publications

Vladimir V. Podolskii, Dmitrii Sluch
One-Way Communication Complexity of Partial XOR Functions. ICALP (2024)
Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii
Logical Languages Accepted by Transformer Encoders with Hard Attention. ICLR (2024)
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
Towards Simpler Sorting Networks and Monotone Circuits for Majority. Electron. Colloquium Comput. Complex. (2023)
Vladimir V. Podolskii, Dmitrii Sluch
One-Way Communication Complexity of Partial XOR Functions. CoRR (2023)
Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii
Logical Languages Accepted by Transformer Encoders with Hard Attention. CoRR (2023)
Vladimir V. Podolskii, Dmitrii Sluch
One-Way Communication Complexity of Partial XOR Functions. Electron. Colloquium Comput. Complex. (2023)
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
Constant-Depth Sorting Networks. ITCS (2023)
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
Towards Simpler Sorting Networks and Monotone Circuits for Majority. CoRR (2023)
Alexander Kozachinskiy, Vladimir V. Podolskii
Multiparty Karchmer-Wigderson Games and Threshold Circuits. Theory Comput. 18 (2022)
Anastasiya Chistopolskaya, Vladimir V. Podolskii
On the Decision Tree Complexity of Threshold Functions. Theory Comput. Syst. 66 (6) (2022)
Vladimir V. Podolskii, Nikolay V. Proskurin
Polynomial Threshold Functions for Decision Lists. ISAAC (2022)
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
Constant-Depth Sorting Networks. CoRR (2022)
Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev
A tetrachotomy of ontology-mediated queries with a covering axiom. Artif. Intell. 309 (2022)
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
Constant-Depth Sorting Networks. Electron. Colloquium Comput. Complex. (2022)
Vladimir V. Podolskii, Nikolay V. Proskurin
Polynomial Threshold Functions for Decision Lists. CoRR (2022)
Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev
Deciding boundedness of monadic sirups. CoRR (2021)
Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev
Deciding Boundedness of Monadic Sirups. PODS (2021)
Alexander Kozachinskiy, Vladimir V. Podolskii
Multiparty Karchmer - Wigderson Games and Threshold Circuits. Computational Complexity Conference (2020)
Vladimir V. Podolskii, Alexander A. Sherstov
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. ACM Trans. Comput. Theory 12 (4) (2020)
Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev
A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom. CoRR (2020)
Alexander Kozachinskiy, Vladimir V. Podolskii
Multiparty Karchmer-Wigderson Games and Threshold Circuits. Electron. Colloquium Comput. Complex. 27 (2020)
Alexander Kozachinskiy, Vladimir V. Podolskii
Multiparty Karchmer-Wigderson Games and Threshold Circuits. CoRR (2020)
Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev
A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom. KR (2020)
Dima Grigoriev, Vladimir V. Podolskii
Tropical Combinatorial Nullstellensatz and Sparse Polynomials. Found. Comput. Math. 20 (4) (2020)
Fedor V. Fomin, Vladimir V. Podolskii
CSR 2018 Special Issue on TOCS. Theory Comput. Syst. 64 (1) (2020)
Anastasiya Chistopolskaya, Vladimir V. Podolskii
On the Decision Tree Complexity of Threshold Functions. CSR (2020)
Alexander S. Kulikov, Vladimir V. Podolskii
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. Theory Comput. Syst. 63 (5) (2019)
Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii
Complexity of Linear Operators. ISAAC (2019)
Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii
Complexity of Linear Operators. Electron. Colloquium Comput. Complex. 26 (2019)
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev
Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity. J. ACM 65 (5) (2018)
Dima Grigoriev, Vladimir V. Podolskii
Tropical Effective Primary and Dual Nullstellensätze. Discret. Comput. Geom. 59 (3) (2018)
Anastasiya Chistopolskaya, Vladimir V. Podolskii
Parity Decision Tree Complexity is Greater Than Granularity. Electron. Colloquium Comput. Complex. 25 (2018)
Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii
Complexity of Linear Operators. CoRR (2018)
Anastasiya Chistopolskaya, Vladimir V. Podolskii
Parity Decision Tree Complexity is Greater Than Granularity. CoRR (2018)
Dima Grigoriev, Vladimir V. Podolskii
Tropical Combinatorial Nullstellensatz and Fewnomials Testing. CoRR (2017)
Olga Gerasimova, Stanislav Kikot, Vladimir V. Podolskii, Michael Zakharyaschev
More on the Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom. KESW (2017)
Alexander S. Kulikov, Vladimir V. Podolskii
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. STACS (2017)
Dima Grigoriev, Vladimir V. Podolskii
Tropical Combinatorial Nullstellensatz and Fewnomials Testing. FCT (2017)
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Vladislav Ryzhikov, Michael Zakharyaschev
The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries. PODS (2017)
Vladimir V. Podolskii, Alexander A. Sherstov
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. Electron. Colloquium Comput. Complex. 24 (2017)
Vladimir V. Podolskii
Bounds in Ontology-Based Data Access via Circuit Complexity. Theory Comput. Syst. 61 (2) (2017)
Vladimir V. Podolskii, Alexander A. Sherstov
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. CoRR (2017)
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Vladislav Ryzhikov, Michael Zakharyaschev
The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries. CoRR (2017)
Olga Gerasimova, Stanislav Kikot, Vladimir V. Podolskii, Michael Zakharyaschev
On the Data Complexity of Ontology-Mediated Queries with a Covering Axiom. Description Logics (2017)
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev
Theoretically Optimal Datalog Rewritings for OWL 2 QL Ontology-Mediated Queries. CoRR (2016)
Alexander S. Kulikov, Vladimir V. Podolskii
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. CoRR (2016)
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev
Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity. CoRR (2016)
Alexander S. Kulikov, Vladimir V. Podolskii
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. Electron. Colloquium Comput. Complex. 23 (2016)
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev
Theoretically Optimal Datalog Rewritings for OWL 2 QL Ontology-Mediated Queries. Description Logics (2016)
Vladimir V. Podolskii
Circuit Complexity Meets Ontology-Based Data Access. CSR (2015)
Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii
Polynomial threshold functions and Boolean threshold circuits. Inf. Comput. 240 (2015)
Dima Grigoriev, Vladimir V. Podolskii
Tropical Effective Primary and Dual Nullstellens"atze. STACS (2015)
Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii
Combined Complexity of Answering Tree-like Queries in OWL 2 QL. Description Logics (2015)
Vladimir V. Podolskii
Circuit Complexity Meets Ontology-Based Data Access. CoRR (2015)
Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii
Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results. LICS (2015)
Dima Grigoriev, Vladimir V. Podolskii
Complexity of Tropical and Min-plus Linear Prevarieties. Comput. Complex. 24 (1) (2015)
Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev
On the succinctness of query rewriting over shallow ontologies. CSL-LICS (2014)
Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev
On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Shallow Chases. CoRR (2014)
Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii
Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries. CoRR (2014)
Dima Grigoriev, Vladimir V. Podolskii
Tropical Effective Primary and Dual Nullstellensätze. CoRR (2014)
Georg Gottlob, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Thomas Schwentick, Michael Zakharyaschev
The price of query rewriting in ontology-based data access. Artif. Intell. 213 (2014)
Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii
Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries. Description Logics (2014)
Vladimir V. Podolskii
Lower Bound on Weights of Large Degree Threshold Functions Log. Methods Comput. Sci. 9 (2) (2013)
Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii
Polynomial threshold functions and Boolean threshold circuits. Electron. Colloquium Comput. Complex. 20 (2013)
Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev
Query Rewriting over Shallow Ontologies. Description Logics (2013)
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Vladimir V. Podolskii, Elias P. Tsigaridas
Patience of matrix games. Discret. Appl. Math. 161 (16-17) (2013)
Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii
Polynomial Threshold Functions and Boolean Threshold Circuits. MFCS (2013)
Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev
Exponential Lower Bounds and Separation for Query Rewriting. ICALP (2) (2012)
Vladimir V. Podolskii
Lower Bound on Weights of Large Degree Threshold Functions. CiE (2012)
Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev
Exponential Lower Bounds and Separation for Query Rewriting CoRR (2012)
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Vladimir V. Podolskii, Elias P. Tsigaridas
Patience of Matrix Games CoRR (2012)
Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev
Long Rewritings, Short Rewritings. Description Logics (2012)
Vladimir V. Podolskii
Exponential lower bound for bounded depth circuits with few threshold gates. Inf. Process. Lett. 112 (7) (2012)
Dima Grigoriev, Vladimir V. Podolskii
Complexity of tropical and min-plus linear prevarieties CoRR (2012)
Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii
Exact Threshold Circuits. Computational Complexity Conference (2010)
László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun
Weights of Exact Threshold Functions. MFCS (2010)
Vladimir V. Podolskii
Perceptrons of large weight. Probl. Inf. Transm. 45 (1) (2009)
Vladimir V. Podolskii
A Uniform Lower Bound on Weights of Perceptrons. CSR (2008)
Vladimir V. Podolskii
Perceptrons of Large Weight. CSR (2007)