A Uniform Lower Bound on Weights of Perceptrons. - Vladimir V. Podolskii (CSR, 2008)

Perceptrons of large weight. - Vladimir V. Podolskii (Probl. Inf. Transm., 2009)

Exact Threshold Circuits. - Kristoffer Arnsfelt Hansen; Vladimir V. Podolskii (CCC, 2010)

Weights of Exact Threshold Functions. - László Babai; Kristoffer Arnsfelt Hansen; Vladimir V. Podolskii; Xiaoming Sun 001 (MFCS, 2010)

Long Rewritings, Short Rewritings. - Stanislav Kikot; Roman Kontchakov; Vladimir V. Podolskii; Michael Zakharyaschev (Description Logics, 2012)

Exponential Lower Bounds and Separation for Query Rewriting. - Stanislav Kikot; Roman Kontchakov; Vladimir V. Podolskii; Michael Zakharyaschev (ICALP (2), 2012)

Exponential lower bound for bounded depth circuits with few threshold gates. - Vladimir V. Podolskii (Inf. Process. Lett., 2012)

Query Rewriting over Shallow Ontologies. - Stanislav Kikot; Roman Kontchakov; Vladimir V. Podolskii; Michael Zakharyaschev (Description Logics, 2013)

Lower Bound on Weights of Large Degree Threshold Functions - Vladimir V. Podolskii (Log. Methods Comput. Sci., 2013)

Patience of matrix games. - Kristoffer Arnsfelt Hansen; Rasmus Ibsen-Jensen; Vladimir V. Podolskii; Elias P. Tsigaridas (Discret. Appl. Math., 2013)

Polynomial threshold functions and Boolean threshold circuits. - Kristoffer Arnsfelt Hansen; Vladimir V. Podolskii (Electron. Colloquium Comput. Complex., 2013)

On the succinctness of query rewriting over shallow ontologies. - Stanislav Kikot; Roman Kontchakov; Vladimir V. Podolskii; Michael Zakharyaschev (CSL-LICS, 2014)

Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries. - Meghyn Bienvenu; Stanislav Kikot; Vladimir V. Podolskii (Description Logics, 2014)

The price of query rewriting in ontology-based data access. - Georg Gottlob; Stanislav Kikot; Roman Kontchakov; Vladimir V. Podolskii; Thomas Schwentick; Michael Zakharyaschev (Artif. Intell., 2014)

On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Shallow Chases. - Stanislav Kikot; Roman Kontchakov; Vladimir V. Podolskii; Michael Zakharyaschev (CoRR, 2014)

Circuit Complexity Meets Ontology-Based Data Access. - Vladimir V. Podolskii (CSR, 2015)

Combined Complexity of Answering Tree-like Queries in OWL 2 QL. - Meghyn Bienvenu; Stanislav Kikot; Vladimir V. Podolskii (Description Logics, 2015)

Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results. - Meghyn Bienvenu; Stanislav Kikot; Vladimir V. Podolskii (LICS, 2015)

Tropical Effective Primary and Dual Nullstellens"atze. - Dima Grigoriev; Vladimir V. Podolskii (STACS, 2015)

Complexity of Tropical and Min-plus Linear Prevarieties. - Dima Grigoriev; Vladimir V. Podolskii (Comput. Complex., 2015)

Theoretically Optimal Datalog Rewritings for OWL 2 QL Ontology-Mediated Queries. - Meghyn Bienvenu; Stanislav Kikot; Roman Kontchakov; Vladimir V. Podolskii; Michael Zakharyaschev (Description Logics, 2016)

Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. - Alexander S. Kulikov; Vladimir V. Podolskii (Electron. Colloquium Comput. Complex., 2016)

On the Data Complexity of Ontology-Mediated Queries with a Covering Axiom. - Olga Gerasimova; Stanislav Kikot; Vladimir V. Podolskii; Michael Zakharyaschev (Description Logics, 2017)

Tropical Combinatorial Nullstellensatz and Fewnomials Testing. - Dima Grigoriev; Vladimir V. Podolskii (FCT, 2017)

More on the Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom. - Olga Gerasimova; Stanislav Kikot; Vladimir V. Podolskii; Michael Zakharyaschev (KESW, 2017)

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 (PODS, 2017)

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. - Vladimir V. Podolskii; Alexander A. Sherstov (Electron. Colloquium Comput. Complex., 2017)

Bounds in Ontology-Based Data Access via Circuit Complexity. - Vladimir V. Podolskii (Theory Comput. Syst., 2017)

Tropical Effective Primary and Dual Nullstellensätze. - Dima Grigoriev; Vladimir V. Podolskii (Discret. Comput. Geom., 2018)

Parity Decision Tree Complexity is Greater Than Granularity. - Anastasiya Chistopolskaya; Vladimir V. Podolskii (Electron. Colloquium Comput. Complex., 2018)

Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity. - Meghyn Bienvenu; Stanislav Kikot; Roman Kontchakov; Vladimir V. Podolskii; Michael Zakharyaschev (J. ACM, 2018)

Complexity of Linear Operators. - Alexander S. Kulikov; Ivan Mikhailin; Andrey Mokhov; Vladimir V. Podolskii (Electron. Colloquium Comput. Complex., 2019)

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 (KR, 2020)

Multiparty Karchmer-Wigderson Games and Threshold Circuits. - Alexander Kozachinskiy; Vladimir V. Podolskii (Electron. Colloquium Comput. Complex., 2020)

Tropical Combinatorial Nullstellensatz and Sparse Polynomials. - Dima Grigoriev; Vladimir V. Podolskii (Found. Comput. Math., 2020)

CSR 2018 Special Issue on TOCS. - Fedor V. Fomin; Vladimir V. Podolskii (Theory Comput. Syst., 2020)

Deciding Boundedness of Monadic Sirups. - Stanislav Kikot; Agi Kurucz; Vladimir V. Podolskii; Michael Zakharyaschev (PODS, 2021)

Polynomial Threshold Functions for Decision Lists. - Vladimir V. Podolskii; Nikolay V. Proskurin (ISAAC, 2022)

A tetrachotomy of ontology-mediated queries with a covering axiom. - Olga Gerasimova; Stanislav Kikot; Agi Kurucz; Vladimir V. Podolskii; Michael Zakharyaschev (Artif. Intell., 2022)

Constant-Depth Sorting Networks. - Natalia Dobrokhotova-Maikova; Alexander Kozachinskiy; Vladimir V. Podolskii (Electron. Colloquium Comput. Complex., 2022)

On the Decision Tree Complexity of Threshold Functions. - Anastasiya Chistopolskaya; Vladimir V. Podolskii (Theory Comput. Syst., 2022)

Towards Simpler Sorting Networks and Monotone Circuits for Majority. - Natalia Dobrokhotova-Maikova; Alexander Kozachinskiy; Vladimir V. Podolskii (Electron. Colloquium Comput. Complex., 2023)

One-Way Communication Complexity of Partial XOR Functions. - Vladimir V. Podolskii; Dmitrii Sluch (Electron. Colloquium Comput. Complex., 2023)

Logical Languages Accepted by Transformer Encoders with Hard Attention. - Pablo Barceló; Alexander Kozachinskiy; Anthony Widjaja Lin; Vladimir V. Podolskii (ICLR, 2024)

Complexity Aspects of the Extension of Wagner's Hierarchy to k-Partitions. - Vladimir Podolskii 001; Victor Selivanov (NCMA, 2024)

Nearest Neighbor Complexity and Boolean Circuits. - Mason DiCicco; Vladimir Podolskii 001; Daniel Reichman 001 (Electron. Colloquium Comput. Complex., 2024)

Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity. - Vladimir Podolskii 001; Alexander Shekhovtsov (Electron. Colloquium Comput. Complex., 2024)

Communication Complexity of Equality and Error Correcting Codes. - Dale Jacobs; John Jeang; Vladimir Podolskii 001; Morgan E. Prior; Ilya Volkovich (Electron. Colloquium Comput. Complex., 2025)