default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Vladimir V. Podolskii
@inproceedings{DBLP:conf/approx/Dobrokhotova-Maikova24,
author = {Natalia Dobrokhotova{-}Maikova and
Alexander Kozachinskiy and
Vladimir V. Podolskii},
editor = {Amit Kumar and
Noga Ron{-}Zewi},
title = {Towards Simpler Sorting Networks and Monotone Circuits for Majority},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2024, August 28-30, 2024, London School
of Economics, London, {UK}},
series = {LIPIcs},
volume = {317},
pages = {50:1--50:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024},
url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.50},
doi = {10.4230/LIPICS.APPROX/RANDOM.2024.50},
timestamp = {Mon, 16 Sep 2024 17:07:54 +0200},
biburl = {https://dblp.org/rec/conf/approx/Dobrokhotova-Maikova24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/PodolskiiS24,
author = {Vladimir V. Podolskii and
Dmitrii Sluch},
editor = {Karl Bringmann and
Martin Grohe and
Gabriele Puppis and
Ola Svensson},
title = {One-Way Communication Complexity of Partial {XOR} Functions},
booktitle = {51st International Colloquium on Automata, Languages, and Programming,
{ICALP} 2024, July 8-12, 2024, Tallinn, Estonia},
series = {LIPIcs},
volume = {297},
pages = {116:1--116:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2024.116},
doi = {10.4230/LIPICS.ICALP.2024.116},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/PodolskiiS24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/iclr/BarceloKLP24,
author = {Pablo Barcel{\'{o}} and
Alexander Kozachinskiy and
Anthony Widjaja Lin and
Vladimir V. Podolskii},
title = {Logical Languages Accepted by Transformer Encoders with Hard Attention},
booktitle = {The Twelfth International Conference on Learning Representations,
{ICLR} 2024, Vienna, Austria, May 7-11, 2024},
publisher = {OpenReview.net},
year = {2024},
url = {https://openreview.net/forum?id=gbrHZq07mq},
timestamp = {Wed, 07 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/iclr/BarceloKLP24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/Dobrokhotova-Maikova23,
author = {Natalia Dobrokhotova{-}Maikova and
Alexander Kozachinskiy and
Vladimir V. Podolskii},
editor = {Yael Tauman Kalai},
title = {Constant-Depth Sorting Networks},
booktitle = {14th Innovations in Theoretical Computer Science Conference, {ITCS}
2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, {USA}},
series = {LIPIcs},
volume = {251},
pages = {43:1--43:19},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2023.43},
doi = {10.4230/LIPICS.ITCS.2023.43},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/Dobrokhotova-Maikova23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2310-03817,
author = {Pablo Barcel{\'{o}} and
Alexander Kozachinskiy and
Anthony Widjaja Lin and
Vladimir V. Podolskii},
title = {Logical Languages Accepted by Transformer Encoders with Hard Attention},
journal = {CoRR},
volume = {abs/2310.03817},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2310.03817},
doi = {10.48550/ARXIV.2310.03817},
eprinttype = {arXiv},
eprint = {2310.03817},
timestamp = {Thu, 19 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2310-03817.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2310-12270,
author = {Natalia Dobrokhotova{-}Maikova and
Alexander Kozachinskiy and
Vladimir V. Podolskii},
title = {Towards Simpler Sorting Networks and Monotone Circuits for Majority},
journal = {CoRR},
volume = {abs/2310.12270},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2310.12270},
doi = {10.48550/ARXIV.2310.12270},
eprinttype = {arXiv},
eprint = {2310.12270},
timestamp = {Fri, 27 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2310-12270.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2310-20606,
author = {Vladimir V. Podolskii and
Dmitrii Sluch},
title = {One-Way Communication Complexity of Partial {XOR} Functions},
journal = {CoRR},
volume = {abs/2310.20606},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2310.20606},
doi = {10.48550/ARXIV.2310.20606},
eprinttype = {arXiv},
eprint = {2310.20606},
timestamp = {Fri, 03 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2310-20606.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Dobrokhotova-Maikova23,
author = {Natalia Dobrokhotova{-}Maikova and
Alexander Kozachinskiy and
Vladimir V. Podolskii},
title = {Towards Simpler Sorting Networks and Monotone Circuits for Majority},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-153}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/153},
eprinttype = {ECCC},
eprint = {TR23-153},
timestamp = {Wed, 10 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/Dobrokhotova-Maikova23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/PodolskiiS23,
author = {Vladimir V. Podolskii and
Dmitrii Sluch},
title = {One-Way Communication Complexity of Partial {XOR} Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-157}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/157},
eprinttype = {ECCC},
eprint = {TR23-157},
timestamp = {Wed, 10 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/PodolskiiS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ai/GerasimovaKKPZ22,
author = {Olga Gerasimova and
Stanislav Kikot and
Agi Kurucz and
Vladimir V. Podolskii and
Michael Zakharyaschev},
title = {A tetrachotomy of ontology-mediated queries with a covering axiom},
journal = {Artif. Intell.},
volume = {309},
pages = {103738},
year = {2022},
url = {https://doi.org/10.1016/j.artint.2022.103738},
doi = {10.1016/J.ARTINT.2022.103738},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ai/GerasimovaKKPZ22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/ChistopolskayaP22,
author = {Anastasiya Chistopolskaya and
Vladimir V. Podolskii},
title = {On the Decision Tree Complexity of Threshold Functions},
journal = {Theory Comput. Syst.},
volume = {66},
number = {6},
pages = {1074--1098},
year = {2022},
url = {https://doi.org/10.1007/s00224-022-10084-x},
doi = {10.1007/S00224-022-10084-X},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/ChistopolskayaP22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/KozachinskiyP22,
author = {Alexander Kozachinskiy and
Vladimir V. Podolskii},
title = {Multiparty Karchmer-Wigderson Games and Threshold Circuits},
journal = {Theory Comput.},
volume = {18},
pages = {1--33},
year = {2022},
url = {https://theoryofcomputing.org/articles/v018a015/},
timestamp = {Thu, 02 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toc/KozachinskiyP22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/PodolskiiP22,
author = {Vladimir V. Podolskii and
Nikolay V. Proskurin},
editor = {Sang Won Bae and
Heejin Park},
title = {Polynomial Threshold Functions for Decision Lists},
booktitle = {33rd International Symposium on Algorithms and Computation, {ISAAC}
2022, December 19-21, 2022, Seoul, Korea},
series = {LIPIcs},
volume = {248},
pages = {52:1--52:12},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.ISAAC.2022.52},
doi = {10.4230/LIPICS.ISAAC.2022.52},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/isaac/PodolskiiP22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2207-09371,
author = {Vladimir V. Podolskii and
Nikolay V. Proskurin},
title = {Polynomial Threshold Functions for Decision Lists},
journal = {CoRR},
volume = {abs/2207.09371},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2207.09371},
doi = {10.48550/ARXIV.2207.09371},
eprinttype = {arXiv},
eprint = {2207.09371},
timestamp = {Mon, 25 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2207-09371.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2208-08394,
author = {Natalia Dobrokhotova{-}Maikova and
Alexander Kozachinskiy and
Vladimir V. Podolskii},
title = {Constant-Depth Sorting Networks},
journal = {CoRR},
volume = {abs/2208.08394},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2208.08394},
doi = {10.48550/ARXIV.2208.08394},
eprinttype = {arXiv},
eprint = {2208.08394},
timestamp = {Mon, 22 Aug 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2208-08394.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Dobrokhotova-Maikova22,
author = {Natalia Dobrokhotova{-}Maikova and
Alexander Kozachinskiy and
Vladimir V. Podolskii},
title = {Constant-Depth Sorting Networks},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR22-116}},
year = {2022},
url = {https://eccc.weizmann.ac.il/report/2022/116},
eprinttype = {ECCC},
eprint = {TR22-116},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Dobrokhotova-Maikova22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/pods/KikotKPZ21,
author = {Stanislav Kikot and
Agi Kurucz and
Vladimir V. Podolskii and
Michael Zakharyaschev},
editor = {Leonid Libkin and
Reinhard Pichler and
Paolo Guagliardo},
title = {Deciding Boundedness of Monadic Sirups},
booktitle = {PODS'21: Proceedings of the 40th {ACM} {SIGMOD-SIGACT-SIGAI} Symposium
on Principles of Database Systems, Virtual Event, China, June 20-25,
2021},
pages = {370--387},
publisher = {{ACM}},
year = {2021},
url = {https://doi.org/10.1145/3452021.3458332},
doi = {10.1145/3452021.3458332},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/pods/KikotKPZ21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2108-00433,
author = {Stanislav Kikot and
Agi Kurucz and
Vladimir V. Podolskii and
Michael Zakharyaschev},
title = {Deciding boundedness of monadic sirups},
journal = {CoRR},
volume = {abs/2108.00433},
year = {2021},
url = {https://arxiv.org/abs/2108.00433},
eprinttype = {arXiv},
eprint = {2108.00433},
timestamp = {Thu, 05 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2108-00433.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/focm/GrigorievP20,
author = {Dima Grigoriev and
Vladimir V. Podolskii},
title = {Tropical Combinatorial Nullstellensatz and Sparse Polynomials},
journal = {Found. Comput. Math.},
volume = {20},
number = {4},
pages = {753--781},
year = {2020},
url = {https://doi.org/10.1007/s10208-019-09431-1},
doi = {10.1007/S10208-019-09431-1},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/focm/GrigorievP20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/FominP20,
author = {Fedor V. Fomin and
Vladimir V. Podolskii},
title = {{CSR} 2018 Special Issue on {TOCS}},
journal = {Theory Comput. Syst.},
volume = {64},
number = {1},
pages = {1--2},
year = {2020},
url = {https://doi.org/10.1007/s00224-019-09954-8},
doi = {10.1007/S00224-019-09954-8},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/FominP20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/PodolskiiS20,
author = {Vladimir V. Podolskii and
Alexander A. Sherstov},
title = {Inner Product and Set Disjointness: Beyond Logarithmically Many Parties},
journal = {{ACM} Trans. Comput. Theory},
volume = {12},
number = {4},
pages = {26:1--26:28},
year = {2020},
url = {https://doi.org/10.1145/3428671},
doi = {10.1145/3428671},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/PodolskiiS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/KozachinskiyP20,
author = {Alexander Kozachinskiy and
Vladimir V. Podolskii},
editor = {Shubhangi Saraf},
title = {Multiparty Karchmer - Wigderson Games and Threshold Circuits},
booktitle = {35th Computational Complexity Conference, {CCC} 2020, July 28-31,
2020, Saarbr{\"{u}}cken, Germany (Virtual Conference)},
series = {LIPIcs},
volume = {169},
pages = {24:1--24:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.CCC.2020.24},
doi = {10.4230/LIPICS.CCC.2020.24},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/KozachinskiyP20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/ChistopolskayaP20,
author = {Anastasiya Chistopolskaya and
Vladimir V. Podolskii},
editor = {Henning Fernau},
title = {On the Decision Tree Complexity of Threshold Functions},
booktitle = {Computer Science - Theory and Applications - 15th International Computer
Science Symposium in Russia, {CSR} 2020, Yekaterinburg, Russia, June
29 - July 3, 2020, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {12159},
pages = {198--210},
publisher = {Springer},
year = {2020},
url = {https://doi.org/10.1007/978-3-030-50026-9\_14},
doi = {10.1007/978-3-030-50026-9\_14},
timestamp = {Thu, 06 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/csr/ChistopolskayaP20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/kr/GerasimovaKKPZ20,
author = {Olga Gerasimova and
Stanislav Kikot and
Agi Kurucz and
Vladimir V. Podolskii and
Michael Zakharyaschev},
editor = {Diego Calvanese and
Esra Erdem and
Michael Thielscher},
title = {A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated
Queries with a Covering Axiom},
booktitle = {Proceedings of the 17th International Conference on Principles of
Knowledge Representation and Reasoning, {KR} 2020, Rhodes, Greece,
September 12-18, 2020},
pages = {403--413},
year = {2020},
url = {https://doi.org/10.24963/kr.2020/41},
doi = {10.24963/KR.2020/41},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/kr/GerasimovaKKPZ20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2002-07444,
author = {Alexander Kozachinskiy and
Vladimir V. Podolskii},
title = {Multiparty Karchmer-Wigderson Games and Threshold Circuits},
journal = {CoRR},
volume = {abs/2002.07444},
year = {2020},
url = {https://arxiv.org/abs/2002.07444},
eprinttype = {arXiv},
eprint = {2002.07444},
timestamp = {Fri, 17 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2002-07444.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2006-04167,
author = {Olga Gerasimova and
Stanislav Kikot and
Agi Kurucz and
Vladimir V. Podolskii and
Michael Zakharyaschev},
title = {A data complexity and rewritability tetrachotomy of ontology-mediated
queries with a covering axiom},
journal = {CoRR},
volume = {abs/2006.04167},
year = {2020},
url = {https://arxiv.org/abs/2006.04167},
eprinttype = {arXiv},
eprint = {2006.04167},
timestamp = {Fri, 12 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2006-04167.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KozachinskiyP20,
author = {Alexander Kozachinskiy and
Vladimir V. Podolskii},
title = {Multiparty Karchmer-Wigderson Games and Threshold Circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR20-017}},
year = {2020},
url = {https://eccc.weizmann.ac.il/report/2020/017},
eprinttype = {ECCC},
eprint = {TR20-017},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KozachinskiyP20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/KulikovP19,
author = {Alexander S. Kulikov and
Vladimir V. Podolskii},
title = {Computing Majority by Constant Depth Majority Circuits with Low Fan-in
Gates},
journal = {Theory Comput. Syst.},
volume = {63},
number = {5},
pages = {956--986},
year = {2019},
url = {https://doi.org/10.1007/s00224-018-9900-3},
doi = {10.1007/S00224-018-9900-3},
timestamp = {Wed, 25 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/KulikovP19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/KulikovMMP19,
author = {Alexander S. Kulikov and
Ivan Mikhailin and
Andrey Mokhov and
Vladimir V. Podolskii},
editor = {Pinyan Lu and
Guochuan Zhang},
title = {Complexity of Linear Operators},
booktitle = {30th International Symposium on Algorithms and Computation, {ISAAC}
2019, December 8-11, 2019, Shanghai University of Finance and Economics,
Shanghai, China},
series = {LIPIcs},
volume = {149},
pages = {17:1--17:12},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.ISAAC.2019.17},
doi = {10.4230/LIPICS.ISAAC.2019.17},
timestamp = {Wed, 21 Aug 2024 22:46:00 +0200},
biburl = {https://dblp.org/rec/conf/isaac/KulikovMMP19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KulikovMMP19,
author = {Alexander S. Kulikov and
Ivan Mikhailin and
Andrey Mokhov and
Vladimir V. Podolskii},
title = {Complexity of Linear Operators},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-002}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/002},
eprinttype = {ECCC},
eprint = {TR19-002},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KulikovMMP19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dcg/GrigorievP18,
author = {Dima Grigoriev and
Vladimir V. Podolskii},
title = {Tropical Effective Primary and Dual Nullstellens{\"{a}}tze},
journal = {Discret. Comput. Geom.},
volume = {59},
number = {3},
pages = {507--552},
year = {2018},
url = {https://doi.org/10.1007/s00454-018-9966-3},
doi = {10.1007/S00454-018-9966-3},
timestamp = {Thu, 12 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dcg/GrigorievP18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/BienvenuKKPZ18,
author = {Meghyn Bienvenu and
Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Michael Zakharyaschev},
title = {Ontology-Mediated Queries: Combined Complexity and Succinctness of
Rewritings via Circuit Complexity},
journal = {J. {ACM}},
volume = {65},
number = {5},
pages = {28:1--28:51},
year = {2018},
url = {https://doi.org/10.1145/3191832},
doi = {10.1145/3191832},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/BienvenuKKPZ18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/csr/2018,
editor = {Fedor V. Fomin and
Vladimir V. Podolskii},
title = {Computer Science - Theory and Applications - 13th International Computer
Science Symposium in Russia, {CSR} 2018, Moscow, Russia, June 6-10,
2018, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {10846},
publisher = {Springer},
year = {2018},
url = {https://doi.org/10.1007/978-3-319-90530-3},
doi = {10.1007/978-3-319-90530-3},
isbn = {978-3-319-90529-7},
timestamp = {Tue, 14 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/csr/2018.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1810-08668,
author = {Anastasiya Chistopolskaya and
Vladimir V. Podolskii},
title = {Parity Decision Tree Complexity is Greater Than Granularity},
journal = {CoRR},
volume = {abs/1810.08668},
year = {2018},
url = {http://arxiv.org/abs/1810.08668},
eprinttype = {arXiv},
eprint = {1810.08668},
timestamp = {Wed, 31 Oct 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1810-08668.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1812-11772,
author = {Alexander S. Kulikov and
Ivan Mikhailin and
Andrey Mokhov and
Vladimir V. Podolskii},
title = {Complexity of Linear Operators},
journal = {CoRR},
volume = {abs/1812.11772},
year = {2018},
url = {http://arxiv.org/abs/1812.11772},
eprinttype = {arXiv},
eprint = {1812.11772},
timestamp = {Wed, 02 Jan 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1812-11772.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChistopolskayaP18,
author = {Anastasiya Chistopolskaya and
Vladimir V. Podolskii},
title = {Parity Decision Tree Complexity is Greater Than Granularity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-174}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/174},
eprinttype = {ECCC},
eprint = {TR18-174},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChistopolskayaP18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/Podolskii17,
author = {Vladimir V. Podolskii},
title = {Bounds in Ontology-Based Data Access via Circuit Complexity},
journal = {Theory Comput. Syst.},
volume = {61},
number = {2},
pages = {464--493},
year = {2017},
url = {https://doi.org/10.1007/s00224-016-9707-z},
doi = {10.1007/S00224-016-9707-Z},
timestamp = {Wed, 26 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/Podolskii17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dlog/GerasimovaKPZ17,
author = {Olga Gerasimova and
Stanislav Kikot and
Vladimir V. Podolskii and
Michael Zakharyaschev},
editor = {Alessandro Artale and
Birte Glimm and
Roman Kontchakov},
title = {On the Data Complexity of Ontology-Mediated Queries with a Covering
Axiom},
booktitle = {Proceedings of the 30th International Workshop on Description Logics,
Montpellier, France, July 18-21, 2017},
series = {{CEUR} Workshop Proceedings},
volume = {1879},
publisher = {CEUR-WS.org},
year = {2017},
url = {https://ceur-ws.org/Vol-1879/paper39.pdf},
timestamp = {Fri, 10 Mar 2023 16:23:17 +0100},
biburl = {https://dblp.org/rec/conf/dlog/GerasimovaKPZ17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fct/GrigorievP17,
author = {Dima Grigoriev and
Vladimir V. Podolskii},
editor = {Ralf Klasing and
Marc Zeitoun},
title = {Tropical Combinatorial Nullstellensatz and Fewnomials Testing},
booktitle = {Fundamentals of Computation Theory - 21st International Symposium,
{FCT} 2017, Bordeaux, France, September 11-13, 2017, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {10472},
pages = {284--297},
publisher = {Springer},
year = {2017},
url = {https://doi.org/10.1007/978-3-662-55751-8\_23},
doi = {10.1007/978-3-662-55751-8\_23},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/fct/GrigorievP17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/kesw/GerasimovaKPZ17,
author = {Olga Gerasimova and
Stanislav Kikot and
Vladimir V. Podolskii and
Michael Zakharyaschev},
editor = {Przemyslaw R{\'{o}}zewski and
Christoph Lange},
title = {More on the Data Complexity of Answering Ontology-Mediated Queries
with a Covering Axiom},
booktitle = {Knowledge Engineering and Semantic Web - 8th International Conference,
{KESW} 2017, Szczecin, Poland, November 8-10, 2017, Proceedings},
series = {Communications in Computer and Information Science},
volume = {786},
pages = {143--158},
publisher = {Springer},
year = {2017},
url = {https://doi.org/10.1007/978-3-319-69548-8\_11},
doi = {10.1007/978-3-319-69548-8\_11},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/kesw/GerasimovaKPZ17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/pods/BienvenuKKPRZ17,
author = {Meghyn Bienvenu and
Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Vladislav Ryzhikov and
Michael Zakharyaschev},
editor = {Emanuel Sallinger and
Jan Van den Bussche and
Floris Geerts},
title = {The Complexity of Ontology-Based Data Access with {OWL} 2 {QL} and
Bounded Treewidth Queries},
booktitle = {Proceedings of the 36th {ACM} {SIGMOD-SIGACT-SIGAI} Symposium on Principles
of Database Systems, {PODS} 2017, Chicago, IL, USA, May 14-19, 2017},
pages = {201--216},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3034786.3034791},
doi = {10.1145/3034786.3034791},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/pods/BienvenuKKPRZ17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/KulikovP17,
author = {Alexander S. Kulikov and
Vladimir V. Podolskii},
editor = {Heribert Vollmer and
Brigitte Vall{\'{e}}e},
title = {Computing Majority by Constant Depth Majority Circuits with Low Fan-in
Gates},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science, {STACS}
2017, March 8-11, 2017, Hannover, Germany},
series = {LIPIcs},
volume = {66},
pages = {49:1--49:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.STACS.2017.49},
doi = {10.4230/LIPICS.STACS.2017.49},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stacs/KulikovP17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BienvenuKKPRZ17,
author = {Meghyn Bienvenu and
Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Vladislav Ryzhikov and
Michael Zakharyaschev},
title = {The Complexity of Ontology-Based Data Access with {OWL} 2 {QL} and
Bounded Treewidth Queries},
journal = {CoRR},
volume = {abs/1702.03358},
year = {2017},
url = {http://arxiv.org/abs/1702.03358},
eprinttype = {arXiv},
eprint = {1702.03358},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BienvenuKKPRZ17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/GrigorievP17,
author = {Dima Grigoriev and
Vladimir V. Podolskii},
title = {Tropical Combinatorial Nullstellensatz and Fewnomials Testing},
journal = {CoRR},
volume = {abs/1706.00080},
year = {2017},
url = {http://arxiv.org/abs/1706.00080},
eprinttype = {arXiv},
eprint = {1706.00080},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/GrigorievP17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1711-10661,
author = {Vladimir V. Podolskii and
Alexander A. Sherstov},
title = {Inner Product and Set Disjointness: Beyond Logarithmically Many Parties},
journal = {CoRR},
volume = {abs/1711.10661},
year = {2017},
url = {http://arxiv.org/abs/1711.10661},
eprinttype = {arXiv},
eprint = {1711.10661},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1711-10661.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/PodolskiiS17,
author = {Vladimir V. Podolskii and
Alexander A. Sherstov},
title = {Inner Product and Set Disjointness: Beyond Logarithmically Many Parties},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-184}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/184},
eprinttype = {ECCC},
eprint = {TR17-184},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/PodolskiiS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dlog/BienvenuKKPZ16,
author = {Meghyn Bienvenu and
Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Michael Zakharyaschev},
editor = {Maurizio Lenzerini and
Rafael Pe{\~{n}}aloza},
title = {Theoretically Optimal Datalog Rewritings for {OWL} 2 {QL} Ontology-Mediated
Queries},
booktitle = {Proceedings of the 29th International Workshop on Description Logics,
Cape Town, South Africa, April 22-25, 2016},
series = {{CEUR} Workshop Proceedings},
volume = {1577},
publisher = {CEUR-WS.org},
year = {2016},
url = {https://ceur-ws.org/Vol-1577/paper\_28.pdf},
timestamp = {Fri, 10 Mar 2023 16:23:16 +0100},
biburl = {https://dblp.org/rec/conf/dlog/BienvenuKKPZ16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BienvenuKKPZ16,
author = {Meghyn Bienvenu and
Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Michael Zakharyaschev},
title = {Theoretically Optimal Datalog Rewritings for {OWL} 2 {QL} Ontology-Mediated
Queries},
journal = {CoRR},
volume = {abs/1604.05258},
year = {2016},
url = {http://arxiv.org/abs/1604.05258},
eprinttype = {arXiv},
eprint = {1604.05258},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BienvenuKKPZ16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BienvenuKKPZ16a,
author = {Meghyn Bienvenu and
Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Michael Zakharyaschev},
title = {Ontology-Mediated Queries: Combined Complexity and Succinctness of
Rewritings via Circuit Complexity},
journal = {CoRR},
volume = {abs/1605.01207},
year = {2016},
url = {http://arxiv.org/abs/1605.01207},
eprinttype = {arXiv},
eprint = {1605.01207},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BienvenuKKPZ16a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KulikovP16,
author = {Alexander S. Kulikov and
Vladimir V. Podolskii},
title = {Computing Majority by Constant Depth Majority Circuits with Low Fan-in
Gates},
journal = {CoRR},
volume = {abs/1610.02686},
year = {2016},
url = {http://arxiv.org/abs/1610.02686},
eprinttype = {arXiv},
eprint = {1610.02686},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KulikovP16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KulikovP16,
author = {Alexander S. Kulikov and
Vladimir V. Podolskii},
title = {Computing Majority by Constant Depth Majority Circuits with Low Fan-in
Gates},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-158}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/158},
eprinttype = {ECCC},
eprint = {TR16-158},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KulikovP16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/GrigorievP15,
author = {Dima Grigoriev and
Vladimir V. Podolskii},
title = {Complexity of Tropical and Min-plus Linear Prevarieties},
journal = {Comput. Complex.},
volume = {24},
number = {1},
pages = {31--64},
year = {2015},
url = {https://doi.org/10.1007/s00037-013-0077-5},
doi = {10.1007/S00037-013-0077-5},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/GrigorievP15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/HansenP15,
author = {Kristoffer Arnsfelt Hansen and
Vladimir V. Podolskii},
title = {Polynomial threshold functions and Boolean threshold circuits},
journal = {Inf. Comput.},
volume = {240},
pages = {56--73},
year = {2015},
url = {https://doi.org/10.1016/j.ic.2014.09.008},
doi = {10.1016/J.IC.2014.09.008},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iandc/HansenP15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/Podolskii15,
author = {Vladimir V. Podolskii},
editor = {Lev D. Beklemishev and
Daniil V. Musatov},
title = {Circuit Complexity Meets Ontology-Based Data Access},
booktitle = {Computer Science - Theory and Applications - 10th International Computer
Science Symposium in Russia, {CSR} 2015, Listvyanka, Russia, July
13-17, 2015, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {9139},
pages = {7--26},
publisher = {Springer},
year = {2015},
url = {https://doi.org/10.1007/978-3-319-20297-6\_2},
doi = {10.1007/978-3-319-20297-6\_2},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/csr/Podolskii15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dlog/BienvenuKP15,
author = {Meghyn Bienvenu and
Stanislav Kikot and
Vladimir V. Podolskii},
editor = {Diego Calvanese and
Boris Konev},
title = {Combined Complexity of Answering Tree-like Queries in {OWL} 2 {QL}},
booktitle = {Proceedings of the 28th International Workshop on Description Logics,
Athens,Greece, June 7-10, 2015},
series = {{CEUR} Workshop Proceedings},
volume = {1350},
publisher = {CEUR-WS.org},
year = {2015},
url = {https://ceur-ws.org/Vol-1350/paper-10.pdf},
timestamp = {Fri, 10 Mar 2023 16:23:17 +0100},
biburl = {https://dblp.org/rec/conf/dlog/BienvenuKP15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/lics/BienvenuKP15,
author = {Meghyn Bienvenu and
Stanislav Kikot and
Vladimir V. Podolskii},
title = {Tree-like Queries in {OWL} 2 {QL:} Succinctness and Complexity Results},
booktitle = {30th Annual {ACM/IEEE} Symposium on Logic in Computer Science, {LICS}
2015, Kyoto, Japan, July 6-10, 2015},
pages = {317--328},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/LICS.2015.38},
doi = {10.1109/LICS.2015.38},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/lics/BienvenuKP15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/GrigorievP15,
author = {Dima Grigoriev and
Vladimir V. Podolskii},
editor = {Ernst W. Mayr and
Nicolas Ollinger},
title = {Tropical Effective Primary and Dual Nullstellens"atze},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science,
{STACS} 2015, March 4-7, 2015, Garching, Germany},
series = {LIPIcs},
volume = {30},
pages = {379--391},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015},
url = {https://doi.org/10.4230/LIPIcs.STACS.2015.379},
doi = {10.4230/LIPICS.STACS.2015.379},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stacs/GrigorievP15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/Podolskii15,
author = {Vladimir V. Podolskii},
title = {Circuit Complexity Meets Ontology-Based Data Access},
journal = {CoRR},
volume = {abs/1506.01296},
year = {2015},
url = {http://arxiv.org/abs/1506.01296},
eprinttype = {arXiv},
eprint = {1506.01296},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/Podolskii15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ai/GottlobKKPSZ14,
author = {Georg Gottlob and
Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Thomas Schwentick and
Michael Zakharyaschev},
title = {The price of query rewriting in ontology-based data access},
journal = {Artif. Intell.},
volume = {213},
pages = {42--59},
year = {2014},
url = {https://doi.org/10.1016/j.artint.2014.04.004},
doi = {10.1016/J.ARTINT.2014.04.004},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ai/GottlobKKPSZ14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csl/KikotKPZ14,
author = {Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Michael Zakharyaschev},
editor = {Thomas A. Henzinger and
Dale Miller},
title = {On the succinctness of query rewriting over shallow ontologies},
booktitle = {Joint Meeting of the Twenty-Third {EACSL} Annual Conference on Computer
Science Logic {(CSL)} and the Twenty-Ninth Annual {ACM/IEEE} Symposium
on Logic in Computer Science (LICS), {CSL-LICS} '14, Vienna, Austria,
July 14 - 18, 2014},
pages = {57:1--57:10},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2603088.2603131},
doi = {10.1145/2603088.2603131},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/csl/KikotKPZ14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dlog/BienvenuKP14,
author = {Meghyn Bienvenu and
Stanislav Kikot and
Vladimir V. Podolskii},
editor = {Meghyn Bienvenu and
Magdalena Ortiz and
Riccardo Rosati and
Mantas Simkus},
title = {Succinctness of Query Rewriting in {OWL} 2 {QL:} The Case of Tree-like
Queries},
booktitle = {Informal Proceedings of the 27th International Workshop on Description
Logics, Vienna, Austria, July 17-20, 2014},
series = {{CEUR} Workshop Proceedings},
volume = {1193},
pages = {45--57},
publisher = {CEUR-WS.org},
year = {2014},
url = {https://ceur-ws.org/Vol-1193/paper\_43.pdf},
timestamp = {Mon, 26 Jun 2023 20:43:45 +0200},
biburl = {https://dblp.org/rec/conf/dlog/BienvenuKP14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KikotKPZ14,
author = {Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Michael Zakharyaschev},
title = {On the Succinctness of Query Rewriting over {OWL} 2 {QL} Ontologies
with Shallow Chases},
journal = {CoRR},
volume = {abs/1401.4420},
year = {2014},
url = {http://arxiv.org/abs/1401.4420},
eprinttype = {arXiv},
eprint = {1401.4420},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KikotKPZ14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BienvenuKP14,
author = {Meghyn Bienvenu and
Stanislav Kikot and
Vladimir V. Podolskii},
title = {Succinctness of Query Rewriting in {OWL} 2 {QL:} The Case of Tree-like
Queries},
journal = {CoRR},
volume = {abs/1406.3047},
year = {2014},
url = {http://arxiv.org/abs/1406.3047},
eprinttype = {arXiv},
eprint = {1406.3047},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BienvenuKP14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/GrigorievP14,
author = {Dima Grigoriev and
Vladimir V. Podolskii},
title = {Tropical Effective Primary and Dual Nullstellens{\"{a}}tze},
journal = {CoRR},
volume = {abs/1409.6215},
year = {2014},
url = {http://arxiv.org/abs/1409.6215},
eprinttype = {arXiv},
eprint = {1409.6215},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/GrigorievP14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1204-2652,
author = {Vladimir V. Podolskii},
title = {Lower Bound on Weights of Large Degree Threshold Functions},
journal = {Log. Methods Comput. Sci.},
volume = {9},
number = {2},
year = {2013},
url = {https://doi.org/10.2168/LMCS-9(2:13)2013},
doi = {10.2168/LMCS-9(2:13)2013},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1204-2652.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dam/HansenIPT13,
author = {Kristoffer Arnsfelt Hansen and
Rasmus Ibsen{-}Jensen and
Vladimir V. Podolskii and
Elias P. Tsigaridas},
title = {Patience of matrix games},
journal = {Discret. Appl. Math.},
volume = {161},
number = {16-17},
pages = {2440--2459},
year = {2013},
url = {https://doi.org/10.1016/j.dam.2013.05.008},
doi = {10.1016/J.DAM.2013.05.008},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/dam/HansenIPT13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dlog/KikotKPZ13,
author = {Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Michael Zakharyaschev},
editor = {Thomas Eiter and
Birte Glimm and
Yevgeny Kazakov and
Markus Kr{\"{o}}tzsch},
title = {Query Rewriting over Shallow Ontologies},
booktitle = {Informal Proceedings of the 26th International Workshop on Description
Logics, Ulm, Germany, July 23 - 26, 2013},
series = {{CEUR} Workshop Proceedings},
volume = {1014},
pages = {316--327},
publisher = {CEUR-WS.org},
year = {2013},
url = {https://ceur-ws.org/Vol-1014/paper\_27.pdf},
timestamp = {Fri, 10 Mar 2023 16:23:17 +0100},
biburl = {https://dblp.org/rec/conf/dlog/KikotKPZ13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/HansenP13,
author = {Kristoffer Arnsfelt Hansen and
Vladimir V. Podolskii},
editor = {Krishnendu Chatterjee and
Jir{\'{\i}} Sgall},
title = {Polynomial Threshold Functions and Boolean Threshold Circuits},
booktitle = {Mathematical Foundations of Computer Science 2013 - 38th International
Symposium, {MFCS} 2013, Klosterneuburg, Austria, August 26-30, 2013.
Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8087},
pages = {516--527},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-40313-2\_46},
doi = {10.1007/978-3-642-40313-2\_46},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/HansenP13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/HansenP13,
author = {Kristoffer Arnsfelt Hansen and
Vladimir V. Podolskii},
title = {Polynomial threshold functions and Boolean threshold circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-021}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/021},
eprinttype = {ECCC},
eprint = {TR13-021},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/HansenP13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/Podolskii12,
author = {Vladimir V. Podolskii},
title = {Exponential lower bound for bounded depth circuits with few threshold
gates},
journal = {Inf. Process. Lett.},
volume = {112},
number = {7},
pages = {267--271},
year = {2012},
url = {https://doi.org/10.1016/j.ipl.2011.12.011},
doi = {10.1016/J.IPL.2011.12.011},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/Podolskii12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cie/Podolskii12,
author = {Vladimir V. Podolskii},
editor = {S. Barry Cooper and
Anuj Dawar and
Benedikt L{\"{o}}we},
title = {Lower Bound on Weights of Large Degree Threshold Functions},
booktitle = {How the World Computes - Turing Centenary Conference and 8th Conference
on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012.
Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7318},
pages = {599--608},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-30870-3\_60},
doi = {10.1007/978-3-642-30870-3\_60},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cie/Podolskii12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dlog/KikotKPZ12,
author = {Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Michael Zakharyaschev},
editor = {Yevgeny Kazakov and
Domenico Lembo and
Frank Wolter},
title = {Long Rewritings, Short Rewritings},
booktitle = {Proceedings of the 2012 International Workshop on Description Logics,
DL-2012, Rome, Italy, June 7-10, 2012},
series = {{CEUR} Workshop Proceedings},
volume = {846},
publisher = {CEUR-WS.org},
year = {2012},
url = {https://ceur-ws.org/Vol-846/paper\_41.pdf},
timestamp = {Fri, 10 Mar 2023 16:23:17 +0100},
biburl = {https://dblp.org/rec/conf/dlog/KikotKPZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/KikotKPZ12,
author = {Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Michael Zakharyaschev},
editor = {Artur Czumaj and
Kurt Mehlhorn and
Andrew M. Pitts and
Roger Wattenhofer},
title = {Exponential Lower Bounds and Separation for Query Rewriting},
booktitle = {Automata, Languages, and Programming - 39th International Colloquium,
{ICALP} 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part {II}},
series = {Lecture Notes in Computer Science},
volume = {7392},
pages = {263--274},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-31585-5\_26},
doi = {10.1007/978-3-642-31585-5\_26},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/KikotKPZ12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1202-4193,
author = {Stanislav Kikot and
Roman Kontchakov and
Vladimir V. Podolskii and
Michael Zakharyaschev},
title = {Exponential Lower Bounds and Separation for Query Rewriting},
journal = {CoRR},
volume = {abs/1202.4193},
year = {2012},
url = {http://arxiv.org/abs/1202.4193},
eprinttype = {arXiv},
eprint = {1202.4193},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1202-4193.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1204-4578,
author = {Dima Grigoriev and
Vladimir V. Podolskii},
title = {Complexity of tropical and min-plus linear prevarieties},
journal = {CoRR},
volume = {abs/1204.4578},
year = {2012},
url = {http://arxiv.org/abs/1204.4578},
eprinttype = {arXiv},
eprint = {1204.4578},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1204-4578.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1206-1751,
author = {Kristoffer Arnsfelt Hansen and
Rasmus Ibsen{-}Jensen and
Vladimir V. Podolskii and
Elias P. Tsigaridas},
title = {Patience of Matrix Games},
journal = {CoRR},
volume = {abs/1206.1751},
year = {2012},
url = {http://arxiv.org/abs/1206.1751},
eprinttype = {arXiv},
eprint = {1206.1751},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1206-1751.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/HansenP10,
author = {Kristoffer Arnsfelt Hansen and
Vladimir V. Podolskii},
title = {Exact Threshold Circuits},
booktitle = {Proceedings of the 25th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2010, Cambridge, Massachusetts, USA, June 9-12,
2010},
pages = {270--279},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/CCC.2010.33},
doi = {10.1109/CCC.2010.33},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/HansenP10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/BabaiHPS10,
author = {L{\'{a}}szl{\'{o}} Babai and
Kristoffer Arnsfelt Hansen and
Vladimir V. Podolskii and
Xiaoming Sun},
editor = {Petr Hlinen{\'{y}} and
Anton{\'{\i}}n Kucera},
title = {Weights of Exact Threshold Functions},
booktitle = {Mathematical Foundations of Computer Science 2010, 35th International
Symposium, {MFCS} 2010, Brno, Czech Republic, August 23-27, 2010.
Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6281},
pages = {66--77},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-15155-2\_8},
doi = {10.1007/978-3-642-15155-2\_8},
timestamp = {Sun, 04 Aug 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/BabaiHPS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/poit/Podolskii09,
author = {Vladimir V. Podolskii},
title = {Perceptrons of large weight},
journal = {Probl. Inf. Transm.},
volume = {45},
number = {1},
pages = {46--53},
year = {2009},
url = {https://doi.org/10.1134/S0032946009010062},
doi = {10.1134/S0032946009010062},
timestamp = {Sat, 09 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/poit/Podolskii09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/Podolskii08,
author = {Vladimir V. Podolskii},
editor = {Edward A. Hirsch and
Alexander A. Razborov and
Alexei L. Semenov and
Anatol Slissenko},
title = {A Uniform Lower Bound on Weights of Perceptrons},
booktitle = {Computer Science - Theory and Applications, Third International Computer
Science Symposium in Russia, {CSR} 2008, Moscow, Russia, June 7-12,
2008, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5010},
pages = {261--272},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-79709-8\_27},
doi = {10.1007/978-3-540-79709-8\_27},
timestamp = {Tue, 21 Mar 2023 21:00:47 +0100},
biburl = {https://dblp.org/rec/conf/csr/Podolskii08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/Podolskii07,
author = {Vladimir V. Podolskii},
editor = {Volker Diekert and
Mikhail V. Volkov and
Andrei Voronkov},
title = {Perceptrons of Large Weight},
booktitle = {Computer Science - Theory and Applications, Second International Symposium
on Computer Science in Russia, {CSR} 2007, Ekaterinburg, Russia, September
3-7, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4649},
pages = {328--336},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74510-5\_33},
doi = {10.1007/978-3-540-74510-5\_33},
timestamp = {Thu, 09 Nov 2023 20:20:35 +0100},
biburl = {https://dblp.org/rec/conf/csr/Podolskii07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
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.
last updated on 2024-09-18 01:08 CEST 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:
