| 2024 | ICALP | One-Way Communication Complexity of Partial XOR Functions. | Vladimir V. Podolskii, Dmitrii Sluch |
| 2024 | ICLR | Logical Languages Accepted by Transformer Encoders with Hard Attention. | Pablo Barcel, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii |
| 2022 | ISAAC | Polynomial Threshold Functions for Decision Lists. | Vladimir V. Podolskii, Nikolay V. Proskurin |
| 2021 | PODS | Deciding Boundedness of Monadic Sirups. | Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev |
| 2020 | CSR | On the Decision Tree Complexity of Threshold Functions. | Anastasiya Chistopolskaya, Vladimir V. Podolskii |
| 2020 | KR | A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom. | Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev |
| 2019 | ISAAC | Complexity of Linear Operators. | Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii |
| 2017 | FCT | Tropical Combinatorial Nullstellensatz and Fewnomials Testing. | Dima Grigoriev, Vladimir V. Podolskii |
| 2017 | PODS | The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries. | Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Vladislav Ryzhikov, Michael Zakharyaschev |
| 2017 | STACS | Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. | Alexander S. Kulikov, Vladimir V. Podolskii |
| 2015 | CSR | Circuit Complexity Meets Ontology-Based Data Access. | Vladimir V. Podolskii |
| 2015 | LICS | Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results. | Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii |
| 2015 | STACS | Tropical Effective Primary and Dual Nullstellens"atze. | Dima Grigoriev, Vladimir V. Podolskii |
| 2014 | CSL | On the succinctness of query rewriting over shallow ontologies. | Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev |
| 2013 | MFCS | Polynomial Threshold Functions and Boolean Threshold Circuits. | Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii |
| 2012 | CiE | Lower Bound on Weights of Large Degree Threshold Functions. | Vladimir V. Podolskii |
| 2012 | ICALP | Exponential Lower Bounds and Separation for Query Rewriting. | Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev |
| 2010 | MFCS | Weights of Exact Threshold Functions. | Lszl Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun |
| 2008 | CSR | A Uniform Lower Bound on Weights of Perceptrons. | Vladimir V. Podolskii |
| 2007 | CSR | Perceptrons of Large Weight. | Vladimir V. Podolskii |