Alexander Kozachinskiy

According to our database, Alexander Kozachinskiy authored at least 28 papers between 2014 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Infinite Separation Between General and Chromatic Memory.

Alexander Kozachinskiy

Proceedings of the LATIN 2024: Theoretical Informatics, 2024

On dimensionality of feature vectors in MPNNs.

César Bravo, Alexander Kozachinskiy, Cristobal Rojas

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Logical Languages Accepted by Transformer Encoders with Hard Attention.

Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii

Proceedings of the Twelfth International Conference on Learning Representations, 2024

Energy Games over Totally Ordered Groups.

Alexander Kozachinskiy

Proceedings of the 32nd EACSL Annual Conference on Computer Science Logic, 2024

Simple online learning with consistent oracle.

Alexander Kozachinskiy, Tomasz Steifer

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Continuous Positional Payoffs.

Alexander Kozachinskiy

Log. Methods Comput. Sci., 2023

Towards Simpler Sorting Networks and Monotone Circuits for Majority.

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2023

Simple online learning with consistency oracle.

Alexander Kozachinskiy, Tomasz Steifer

CoRR, 2023

Inapproximability of sufficient reasons for decision trees.

Alexander Kozachinskiy

CoRR, 2023

Three Iterations of (d - 1)-WL Test Distinguish Non Isometric Clouds of d-dimensional Points.

Valentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas, Mircea Petrache, Pablo Barceló

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Find a witness or shatter: the landscape of computable PAC learning.

Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Tomasz Steifer

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Constant-Depth Sorting Networks.

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2022

State Complexity of Chromatic Memory in Infinite-Duration Games.

Alexander Kozachinskiy

CoRR, 2022

One-To-Two-Player Lifting for Mildly Growing Memory.

Alexander Kozachinskiy

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

New Bounds for the Flock-of-Birds Problem.

Alexander Kozachinskiy

Proceedings of the Computer Science - Theory and Applications, 2022

2021

Automatic Kolmogorov complexity, normality, and finite-state dimension revisited.

Alexander Kozachinskiy, Alexander Shen

J. Comput. Syst. Sci., 2021

Polyhedral Value Iteration for Discounted Games and Energy Games.

Alexander Kozachinskiy

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Recognizing Read-Once Functions from Depth-Three Formulas.

Alexander Kozachinskiy

Theory Comput. Syst., 2020

Multiparty Karchmer-Wigderson Games and Threshold Circuits.

Alexander Kozachinskiy, Vladimir V. Podolskii

Electron. Colloquium Comput. Complex., 2020

2019

Lower bounds on separation automata for Parity Games.

Alexander Kozachinskiy, Mikhail Vyalyi

CoRR, 2019

Two Characterizations of Finite-State Dimension.

Alexander Kozachinskiy, Alexander Shen

Proceedings of the Fundamentals of Computation Theory - 22nd International Symposium, 2019

2018

Raz-McKenzie simulation: new gadget and unimprovability of Thickness Lemma.

Alexander Kozachinskiy

CoRR, 2018

From Expanders to Hitting Distributions and Simulation Theorems.

Alexander Kozachinskiy

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

2016

One-sided error communication complexity of Gap Hamming Distance.

Egor Klenin, Alexander Kozachinsky

Electron. Colloquium Comput. Complex., 2016

2015

On Slepian-Wolf Theorem with Interaction.

Alexander Kozachinsky

Electron. Colloquium Comput. Complex., 2015

Some Bounds on Communication Complexity of Gap Hamming Distance.

Alexander Kozachinskiy

CoRR, 2015

Making Randomness Public in Unbounded-Round Information Complexity.

Alexander Kozachinskiy

Proceedings of the Computer Science - Theory and Applications, 2015

2014

On the role of private coins in unbounded-round Information Complexity.

Alexander Kozachinsky

Electron. Colloquium Comput. Complex., 2014