On the role of private coins in unbounded-round Information Complexity. - Alexander Kozachinsky (Electron. Colloquium Comput. Complex., 2014)

Making Randomness Public in Unbounded-Round Information Complexity. - Alexander Kozachinskiy (CSR, 2015)

Some Bounds on Communication Complexity of Gap Hamming Distance. - Alexander Kozachinskiy (CoRR, 2015)

On Slepian-Wolf Theorem with Interaction. - Alexander Kozachinsky (Electron. Colloquium Comput. Complex., 2015)

One-sided error communication complexity of Gap Hamming Distance. - Egor Klenin; Alexander Kozachinsky (Electron. Colloquium Comput. Complex., 2016)

From Expanders to Hitting Distributions and Simulation Theorems. - Alexander Kozachinskiy (MFCS, 2018)

Raz-McKenzie simulation: new gadget and unimprovability of Thickness Lemma. - Alexander Kozachinskiy (CoRR, 2018)

Two Characterizations of Finite-State Dimension. - Alexander Kozachinskiy; Alexander Shen 001 (FCT, 2019)

Lower bounds on separation automata for Parity Games. - Alexander Kozachinskiy; Mikhail N. Vyalyi (CoRR, 2019)

Multiparty Karchmer-Wigderson Games and Threshold Circuits. - Alexander Kozachinskiy; Vladimir V. Podolskii (Electron. Colloquium Comput. Complex., 2020)

Recognizing Read-Once Functions from Depth-Three Formulas. - Alexander Kozachinskiy (Theory Comput. Syst., 2020)

Polyhedral Value Iteration for Discounted Games and Energy Games. - Alexander Kozachinskiy (SODA, 2021)

Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. - Alexander Kozachinskiy; Alexander Shen 001 (J. Comput. Syst. Sci., 2021)

New Bounds for the Flock-of-Birds Problem. - Alexander Kozachinskiy (CSR, 2022)

One-To-Two-Player Lifting for Mildly Growing Memory. - Alexander Kozachinskiy (STACS, 2022)

State Complexity of Chromatic Memory in Infinite-Duration Games. - Alexander Kozachinskiy (CoRR, 2022)

Constant-Depth Sorting Networks. - Natalia Dobrokhotova-Maikova; Alexander Kozachinskiy; Vladimir V. Podolskii (Electron. Colloquium Comput. Complex., 2022)

Find a witness or shatter: the landscape of computable PAC learning. - Valentino Delle Rose; Alexander Kozachinskiy; Cristóbal Rojas; Tomasz Steifer (COLT, 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ó (NeurIPS, 2023)

Inapproximability of sufficient reasons for decision trees. - Alexander Kozachinskiy (CoRR, 2023)

Simple online learning with consistency oracle. - Alexander Kozachinskiy; Tomasz Steifer (CoRR, 2023)

Towards Simpler Sorting Networks and Monotone Circuits for Majority. - Natalia Dobrokhotova-Maikova; Alexander Kozachinskiy; Vladimir V. Podolskii (Electron. Colloquium Comput. Complex., 2023)

Continuous Positional Payoffs. - Alexander Kozachinskiy (Log. Methods Comput. Sci., 2023)

Simple online learning with consistent oracle. - Alexander Kozachinskiy; Tomasz Steifer (COLT, 2024)

Energy Games over Totally Ordered Groups. - Alexander Kozachinskiy (CSL, 2024)

Logical Languages Accepted by Transformer Encoders with Hard Attention. - Pablo Barceló; Alexander Kozachinskiy; Anthony Widjaja Lin; Vladimir V. Podolskii (ICLR, 2024)

On dimensionality of feature vectors in MPNNs. - César Bravo; Alexander Kozachinskiy; Cristobal Rojas (ICML, 2024)

Infinite Separation Between General and Chromatic Memory. - Alexander Kozachinskiy (LATIN (2), 2024)

Lower bounds on transformers with infinite precision. - Alexander Kozachinskiy (CoRR, 2024)

Optimal Bounds for Dissatisfaction in Perpetual Voting. - Alexander Kozachinskiy; Alexander Shen 001; Tomasz Steifer (AAAI, 2025)

Effective Littlestone dimension. - Valentino Delle Rose; Alexander Kozachinskiy; Tomasz Steifer (ALT, 2025)

On Computing Probabilistic Explanations for Decision Trees. - Marcelo Arenas; Pablo Barceló; Alexander Kozachinskiy; Miguel Romero 001; Bernardo Subercaseaux (J. Artif. Intell. Res., 2025)

A completely uniform transformer for parity. - Alexander Kozachinskiy; Tomasz Steifer (CoRR, 2025)

Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations. - Pablo Barceló; Alexander Kozachinskiy; Miguel A. Romero Orth; Bernardo Subercaseaux; José Verschae (CoRR, 2025)

Ehrenfeucht-Haussler Rank and Chain of Thought. - Pablo Barceló; Alexander Kozachinskiy; Tomasz Steifer (CoRR, 2025)

Strassen Attention: Unlocking Compositional Abilities in Transformers Based on a New Lower Bound Method. - Alexander Kozachinskiy; Felipe Urrutia; Hector Jimenez; Tomasz Steifer; Germán Pizarro; Matías Fuentes; Francisco Meza; Cristian Buc; Cristóbal Rojas (CoRR, 2025)

Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Models. - Hector Pasten; Felipe Urrutia; Hector Jimenez; Cristian Buc Calderon; Cristóbal Rojas; Alexander Kozachinskiy (CoRR, 2025)

NoPE: The Counting Power of Transformers with No Positional Encodings. - Chris Köcher; Alexander Kozachinskiy; Anthony Widjaja Lin; Marco Sälzer; Georg Zetzsche (CoRR, 2025)

Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations. - Pablo Barceló; Alexander Kozachinskiy; Miguel Romero 001; Bernardo Subercaseaux; José Verschae (Proc. ACM Manag. Data, 2025)

All Kolmogorov complexity functions are optimal, but are some more optimal? - Bruno Bauwens; Alexander Kozachinskiy; Alexander Shen 001 (CoRR, 2025)

Dvorak-Dell-Grohe-Rattan theorem via an asymptotic argument. - Alexander Kozachinskiy (CoRR, 2025)