Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, and Vladimir Podolskii. Constant-Depth Sorting Networks. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 43:1-43:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{dobrokhotovamaikova_et_al:LIPIcs.ITCS.2023.43, author = {Dobrokhotova-Maikova, Natalia and Kozachinskiy, Alexander and Podolskii, Vladimir}, title = {{Constant-Depth Sorting Networks}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {43:1--43:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.43}, URN = {urn:nbn:de:0030-drops-175468}, doi = {10.4230/LIPIcs.ITCS.2023.43}, annote = {Keywords: Sorting networks, constant depth, lower bounds, threshold circuits} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Alexander Kozachinskiy. One-To-Two-Player Lifting for Mildly Growing Memory. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 43:1-43:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{kozachinskiy:LIPIcs.STACS.2022.43, author = {Kozachinskiy, Alexander}, title = {{One-To-Two-Player Lifting for Mildly Growing Memory}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {43:1--43:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.43}, URN = {urn:nbn:de:0030-drops-158535}, doi = {10.4230/LIPIcs.STACS.2022.43}, annote = {Keywords: Games on graphs, one-to-two-player lifting, strategy complexity, positional determinacy, finite-memory determinacy} }
Published in: LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021)
Alexander Kozachinskiy. Continuous Positional Payoffs. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 10:1-10:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kozachinskiy:LIPIcs.CONCUR.2021.10, author = {Kozachinskiy, Alexander}, title = {{Continuous Positional Payoffs}}, booktitle = {32nd International Conference on Concurrency Theory (CONCUR 2021)}, pages = {10:1--10:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-203-7}, ISSN = {1868-8969}, year = {2021}, volume = {203}, editor = {Haddad, Serge and Varacca, Daniele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.10}, URN = {urn:nbn:de:0030-drops-143874}, doi = {10.4230/LIPIcs.CONCUR.2021.10}, annote = {Keywords: Games on graphs, positional strategies, continuous payoffs} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Alexander Kozachinskiy and Vladimir Podolskii. Multiparty Karchmer - Wigderson Games and Threshold Circuits. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 24:1-24:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{kozachinskiy_et_al:LIPIcs.CCC.2020.24, author = {Kozachinskiy, Alexander and Podolskii, Vladimir}, title = {{Multiparty Karchmer - Wigderson Games and Threshold Circuits}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {24:1--24:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.24}, URN = {urn:nbn:de:0030-drops-125767}, doi = {10.4230/LIPIcs.CCC.2020.24}, annote = {Keywords: Karchmer-Wigderson Games, Threshold Circuits, threshold gates, majority function} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Alexander Kozachinskiy. From Expanders to Hitting Distributions and Simulation Theorems. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 4:1-4:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{kozachinskiy:LIPIcs.MFCS.2018.4, author = {Kozachinskiy, Alexander}, title = {{From Expanders to Hitting Distributions and Simulation Theorems}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {4:1--4:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.4}, URN = {urn:nbn:de:0030-drops-95863}, doi = {10.4230/LIPIcs.MFCS.2018.4}, annote = {Keywords: simulation theorems, hitting distributions, expanders} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Egor Klenin and Alexander Kozachinskiy. One-Sided Error Communication Complexity of Gap Hamming Distance. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 7:1-7:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{klenin_et_al:LIPIcs.MFCS.2018.7, author = {Klenin, Egor and Kozachinskiy, Alexander}, title = {{One-Sided Error Communication Complexity of Gap Hamming Distance}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {7:1--7:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.7}, URN = {urn:nbn:de:0030-drops-95893}, doi = {10.4230/LIPIcs.MFCS.2018.7}, annote = {Keywords: Communication Complexity, Gap Hamming Distance, one-sided error} }
Feedback for Dagstuhl Publishing