default search action
Vladimir V. Podolskii
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c31]Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
:
Towards Simpler Sorting Networks and Monotone Circuits for Majority. APPROX/RANDOM 2024: 50:1-50:18 - [c30]Vladimir V. Podolskii
One-Way Communication Complexity of Partial XOR Functions. ICALP 2024: 116:1-116:16 - [c29]Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii:
Logical Languages Accepted by Transformer Encoders with Hard Attention. ICLR 2024 - 2023
- [c28]Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii:
Constant-Depth Sorting Networks. ITCS 2023: 43:1-43:19 - [i32]Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii:
Logical Languages Accepted by Transformer Encoders with Hard Attention. CoRR abs/2310.03817 (2023) - [i31]Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii:
Towards Simpler Sorting Networks and Monotone Circuits for Majority. CoRR abs/2310.12270 (2023) - [i30]Vladimir V. Podolskii, Dmitrii Sluch:
One-Way Communication Complexity of Partial XOR Functions. CoRR abs/2310.20606 (2023) - [i29]Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii:
Towards Simpler Sorting Networks and Monotone Circuits for Majority. Electron. Colloquium Comput. Complex. TR23 (2023) - [i28]Vladimir V. Podolskii, Dmitrii Sluch:
One-Way Communication Complexity of Partial XOR Functions. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j17]Olga Gerasimova, Stanislav Kikot, Agi Kurucz
A tetrachotomy of ontology-mediated queries with a covering axiom. Artif. Intell. 309: 103738 (2022) - [j16]Anastasiya Chistopolskaya, Vladimir V. Podolskii
On the Decision Tree Complexity of Threshold Functions. Theory Comput. Syst. 66(6): 1074-1098 (2022) - [j15]Alexander Kozachinskiy, Vladimir V. Podolskii:
Multiparty Karchmer-Wigderson Games and Threshold Circuits. Adv. Math. Commun. 18: 1-33 (2022) - [c27]Vladimir V. Podolskii, Nikolay V. Proskurin:
Polynomial Threshold Functions for Decision Lists. ISAAC 2022: 52:1-52:12 - [i27]Vladimir V. Podolskii, Nikolay V. Proskurin:
Polynomial Threshold Functions for Decision Lists. CoRR abs/2207.09371 (2022) - [i26]Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii:
Constant-Depth Sorting Networks. CoRR abs/2208.08394 (2022) - [i25]Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii:
Constant-Depth Sorting Networks. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c26]Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev
Deciding Boundedness of Monadic Sirups. PODS 2021: 370-387 - [i24]Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii, Michael Zakharyaschev:
Deciding boundedness of monadic sirups. CoRR abs/2108.00433 (2021) - 2020
- [j14]Dima Grigoriev, Vladimir V. Podolskii
Tropical Combinatorial Nullstellensatz and Sparse Polynomials. Found. Comput. Math. 20(4): 753-781 (2020) - [j13]Fedor V. Fomin
CSR 2018 Special Issue on TOCS. Theory Comput. Syst. 64(1): 1-2 (2020) - [j12]Vladimir V. Podolskii
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. ACM Trans. Comput. Theory 12(4): 26:1-26:28 (2020) - [c25]Alexander Kozachinskiy
Multiparty Karchmer - Wigderson Games and Threshold Circuits. CCC 2020: 24:1-24:23 - [c24]Anastasiya Chistopolskaya, Vladimir V. Podolskii
On the Decision Tree Complexity of Threshold Functions. CSR 2020: 198-210 - [c23]Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir V. Podolskii
A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom. KR 2020: 403-413 - [i23]Alexander Kozachinskiy, Vladimir V. Podolskii:
Multiparty Karchmer-Wigderson Games and Threshold Circuits. CoRR abs/2002.07444 (2020) - [i22]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 abs/2006.04167 (2020) - [i21]Alexander Kozachinskiy, Vladimir V. Podolskii:
Multiparty Karchmer-Wigderson Games and Threshold Circuits. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j11]Alexander S. Kulikov
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. Theory Comput. Syst. 63(5): 956-986 (2019) - [c22]Alexander S. Kulikov
Complexity of Linear Operators. ISAAC 2019: 17:1-17:12 - [i20]Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii:
Complexity of Linear Operators. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j10]Dima Grigoriev, Vladimir V. Podolskii
Tropical Effective Primary and Dual Nullstellensätze. Discret. Comput. Geom. 59(3): 507-552 (2018) - [j9]Meghyn Bienvenu
Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity. J. ACM 65(5): 28:1-28:51 (2018) - [e1]Fedor V. Fomin, Vladimir V. Podolskii:
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, ISBN 978-3-319-90529-7 [contents] - [i19]Anastasiya Chistopolskaya, Vladimir V. Podolskii:
Parity Decision Tree Complexity is Greater Than Granularity. CoRR abs/1810.08668 (2018) - [i18]Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii:
Complexity of Linear Operators. CoRR abs/1812.11772 (2018) - [i17]Anastasiya Chistopolskaya, Vladimir V. Podolskii:
Parity Decision Tree Complexity is Greater Than Granularity. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j8]Vladimir V. Podolskii
Bounds in Ontology-Based Data Access via Circuit Complexity. Theory Comput. Syst. 61(2): 464-493 (2017) - [c21]Olga Gerasimova, Stanislav Kikot, Vladimir V. Podolskii, Michael Zakharyaschev:
On the Data Complexity of Ontology-Mediated Queries with a Covering Axiom. Description Logics 2017 - [c20]Dima Grigoriev, Vladimir V. Podolskii
Tropical Combinatorial Nullstellensatz and Fewnomials Testing. FCT 2017: 284-297 - [c19]Olga Gerasimova, Stanislav Kikot, Vladimir V. Podolskii
More on the Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom. KESW 2017: 143-158 - [c18]Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii
The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries. PODS 2017: 201-216 - [c17]Alexander S. Kulikov
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. STACS 2017: 49:1-49:14 - [i16]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 abs/1702.03358 (2017) - [i15]Dima Grigoriev, Vladimir V. Podolskii:
Tropical Combinatorial Nullstellensatz and Fewnomials Testing. CoRR abs/1706.00080 (2017) - [i14]Vladimir V. Podolskii, Alexander A. Sherstov:
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. CoRR abs/1711.10661 (2017) - [i13]Vladimir V. Podolskii, Alexander A. Sherstov:
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [c16]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 - [i12]Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev:
Theoretically Optimal Datalog Rewritings for OWL 2 QL Ontology-Mediated Queries. CoRR abs/1604.05258 (2016) - [i11]Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev:
Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity. CoRR abs/1605.01207 (2016) - [i10]Alexander S. Kulikov, Vladimir V. Podolskii:
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. CoRR abs/1610.02686 (2016) - [i9]Alexander S. Kulikov, Vladimir V. Podolskii:
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j7]Dima Grigoriev, Vladimir V. Podolskii
Complexity of Tropical and Min-plus Linear Prevarieties. Comput. Complex. 24(1): 31-64 (2015) - [j6]Kristoffer Arnsfelt Hansen
Polynomial threshold functions and Boolean threshold circuits. Inf. Comput. 240: 56-73 (2015) - [c15]Vladimir V. Podolskii
Circuit Complexity Meets Ontology-Based Data Access. CSR 2015: 7-26 - [c14]Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii:
Combined Complexity of Answering Tree-like Queries in OWL 2 QL. Description Logics 2015 - [c13]Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii
Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results. LICS 2015: 317-328 - [c12]Dima Grigoriev, Vladimir V. Podolskii
Tropical Effective Primary and Dual Nullstellens"atze. STACS 2015: 379-391 - [i8]Vladimir V. Podolskii:
Circuit Complexity Meets Ontology-Based Data Access. CoRR abs/1506.01296 (2015) - 2014
- [j5]Georg Gottlob
The price of query rewriting in ontology-based data access. Artif. Intell. 213: 42-59 (2014) - [c11]Stanislav Kikot, Roman Kontchakov
On the succinctness of query rewriting over shallow ontologies. CSL-LICS 2014: 57:1-57:10 - [c10]Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii:
Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries. Description Logics 2014: 45-57 - [i7]Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev:
On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Shallow Chases. CoRR abs/1401.4420 (2014) - [i6]Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii:
Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries. CoRR abs/1406.3047 (2014) - [i5]Dima Grigoriev, Vladimir V. Podolskii:
Tropical Effective Primary and Dual Nullstellensätze. CoRR abs/1409.6215 (2014) - 2013
- [j4]Vladimir V. Podolskii
Lower Bound on Weights of Large Degree Threshold Functions. Log. Methods Comput. Sci. 9(2) (2013) - [j3]Kristoffer Arnsfelt Hansen
Patience of matrix games. Discret. Appl. Math. 161(16-17): 2440-2459 (2013) - [c9]Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev:
Query Rewriting over Shallow Ontologies. Description Logics 2013: 316-327 - [c8]Kristoffer Arnsfelt Hansen
Polynomial Threshold Functions and Boolean Threshold Circuits. MFCS 2013: 516-527 - [i4]Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii:
Polynomial threshold functions and Boolean threshold circuits. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j2]Vladimir V. Podolskii
Exponential lower bound for bounded depth circuits with few threshold gates. Inf. Process. Lett. 112(7): 267-271 (2012) - [c7]Vladimir V. Podolskii
Lower Bound on Weights of Large Degree Threshold Functions. CiE 2012: 599-608 - [c6]Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev:
Long Rewritings, Short Rewritings. Description Logics 2012 - [c5]Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii
Exponential Lower Bounds and Separation for Query Rewriting. ICALP (2) 2012: 263-274 - [i3]Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev:
Exponential Lower Bounds and Separation for Query Rewriting. CoRR abs/1202.4193 (2012) - [i2]Dima Grigoriev, Vladimir V. Podolskii:
Complexity of tropical and min-plus linear prevarieties. CoRR abs/1204.4578 (2012) - [i1]Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Vladimir V. Podolskii, Elias P. Tsigaridas:
Patience of Matrix Games. CoRR abs/1206.1751 (2012) - 2010
- [c4]Kristoffer Arnsfelt Hansen
Exact Threshold Circuits. CCC 2010: 270-279 - [c3]László Babai
Weights of Exact Threshold Functions. MFCS 2010: 66-77
2000 – 2009
- 2009
- [j1]Vladimir V. Podolskii
Perceptrons of large weight. Probl. Inf. Transm. 45(1): 46-53 (2009) - 2008
- [c2]Vladimir V. Podolskii
A Uniform Lower Bound on Weights of Perceptrons. CSR 2008: 261-272 - 2007
- [c1]Vladimir V. Podolskii
Perceptrons of Large Weight. CSR 2007: 328-336
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-12 20:58 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: