Alexander Kozachinskiy

Publication Activity (10 Years)

Years Active: 2015-2024
Publications (10 Years): 44

Top Topics

Nash Equilibria

Totally Ordered

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Alexander Kozachinskiy
Energy Games over Totally Ordered Groups. CSL (2024)
Alexander Kozachinskiy, Tomasz Steifer
Simple online learning with consistent oracle. COLT (2024)
César Bravo, Alexander Kozachinskiy, Cristóbal Rojas
On dimensionality of feature vectors in MPNNs. CoRR (2024)
Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii
Logical Languages Accepted by Transformer Encoders with Hard Attention. ICLR (2024)
Alexander Kozachinskiy
Infinite Separation Between General and Chromatic Memory. LATIN (2) (2024)
Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Tomasz Steifer
Find a witness or shatter: the landscape of computable PAC learning. COLT (2023)
Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Mircea Petrache, Pablo Barceló
Three iterations of (d-1)-WL test distinguish non isometric clouds of d-dimensional points. CoRR (2023)
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
Towards Simpler Sorting Networks and Monotone Circuits for Majority. Electron. Colloquium Comput. Complex. (2023)
Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii
Logical Languages Accepted by Transformer Encoders with Hard Attention. CoRR (2023)
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
Constant-Depth Sorting Networks. ITCS (2023)
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
Towards Simpler Sorting Networks and Monotone Circuits for Majority. CoRR (2023)
Valentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas, Mircea Petrache, Pablo Barceló
Three Iterations of (d - 1)-WL Test Distinguish Non Isometric Clouds of d-dimensional Points. NeurIPS (2023)
Alexander Kozachinskiy, Tomasz Steifer
Simple online learning with consistency oracle. CoRR (2023)
Alexander Kozachinskiy
Continuous Positional Payoffs. Log. Methods Comput. Sci. 19 (3) (2023)
Alexander Kozachinskiy
Inapproximability of sufficient reasons for decision trees. CoRR (2023)
Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Tomasz Steifer
Find a witness or shatter: the landscape of computable PAC learning. CoRR (2023)
Alexander Kozachinskiy, Vladimir V. Podolskii
Multiparty Karchmer-Wigderson Games and Threshold Circuits. Theory Comput. 18 (2022)
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
Constant-Depth Sorting Networks. CoRR (2022)
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
Constant-Depth Sorting Networks. Electron. Colloquium Comput. Complex. (2022)
Alexander Kozachinskiy
State Complexity of Chromatic Memory in Infinite-Duration Games. CoRR (2022)
Alexander Kozachinskiy
Energy Games over Totally Ordered Groups. CoRR (2022)
Alexander Kozachinskiy
New Bounds for the Flock-of-Birds Problem. CSR (2022)
Alexander Kozachinskiy
One-To-Two-Player Lifting for Mildly Growing Memory. STACS (2022)
Alexander Kozachinskiy
Infinite Separation between General and Chromatic Memory. CoRR (2022)
Alexander Kozachinskiy
One-to-Two-Player Lifting for Mildly Growing Memory. CoRR (2021)
Alexander Kozachinskiy
Continuous Positional Payoffs. CONCUR (2021)
Alexander Kozachinskiy
New Bounds for the Flock-of-Birds Problem. CoRR (2021)
Alexander Kozachinskiy, Alexander Shen
Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. J. Comput. Syst. Sci. 118 (2021)
Alexander Kozachinskiy
Polyhedral Value Iteration for Discounted Games and Energy Games. SODA (2021)
Alexander Kozachinskiy, Vladimir V. Podolskii
Multiparty Karchmer - Wigderson Games and Threshold Circuits. Computational Complexity Conference (2020)
Alexander Kozachinskiy
Continuous Positional Payoffs. CoRR (2020)
Alexander Kozachinskiy, Vladimir V. Podolskii
Multiparty Karchmer-Wigderson Games and Threshold Circuits. Electron. Colloquium Comput. Complex. 27 (2020)
Alexander Kozachinskiy
Polyhedral value iteration for discounted games and energy games. CoRR (2020)
Alexander Kozachinskiy
Recognizing Read-Once Functions from Depth-Three Formulas. Theory Comput. Syst. 64 (1) (2020)
Alexander Kozachinskiy, Vladimir V. Podolskii
Multiparty Karchmer-Wigderson Games and Threshold Circuits. CoRR (2020)
Alexander Kozachinskiy, Mikhail Vyalyi
Lower bounds on separation automata for Parity Games. CoRR (2019)
Alexander Kozachinskiy, Alexander Shen
Two Characterizations of Finite-State Dimension. FCT (2019)
Egor Klenin, Alexander Kozachinskiy
One-Sided Error Communication Complexity of Gap Hamming Distance. MFCS (2018)
Alexander Kozachinskiy
Recognizing Read-Once Functions from Depth-Three Formulas. CSR (2018)
Alexander Kozachinskiy
Recognizing Read-Once Functions from Depth-Three Formulas. CoRR (2018)
Alexander Kozachinskiy
Raz-McKenzie simulation: new gadget and unimprovability of Thickness Lemma. CoRR (2018)
Alexander Kozachinskiy
On Slepian-Wolf Theorem with Interaction. Theory Comput. Syst. 62 (3) (2018)
Alexander Kozachinskiy
From Expanders to Hitting Distributions and Simulation Theorems. MFCS (2018)
Alexander Kozachinskiy
On Slepian-Wolf Theorem with Interaction. CSR (2016)
Alexander Kozachinskiy
Some Bounds on Communication Complexity of Gap Hamming Distance. CoRR (2015)
Alexander Kozachinskiy
Making Randomness Public in Unbounded-Round Information Complexity. CSR (2015)
Alexander Kozachinskiy
On Slepian-Wolf Theorem with Interaction. CoRR (2015)