Alexander Kozachinskiy

69 papers A* 8A 4B 6Misc 4Journal 46Unranked 1

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Parity, Sensitivity, and Transformers. CoRR Alexander Kozachinskiy, Tomasz Steifer, Przemyslaw Andrzej Walega
2025	J	`jnl`	A completely uniform transformer for parity. CoRR Alexander Kozachinskiy, Tomasz Steifer
2025	J	`jnl`	All Kolmogorov complexity functions are optimal, but are some more optimal? CoRR Bruno Bauwens, Alexander Kozachinskiy, Alexander Shen
2025	J	`jnl`	Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Models. CoRR Hector Pasten, Felipe Urrutia, Hector Jimenez, Cristian Buc Calderon, Cristóbal Rojas, Alexander Kozachinskiy
2025	J	`jnl`	Decoupling Positional and Symbolic Attention Behavior in Transformers. CoRR Felipe Urrutia, Jorge Salas, Alexander Kozachinskiy, Cristian Buc Calderon, Hector Pasten, Cristobal Rojas
2025	J	`jnl`	Dvorak-Dell-Grohe-Rattan theorem via an asymptotic argument. CoRR Alexander Kozachinskiy
2025	B	`conf`	Effective Littlestone dimension. ALT Valentino Delle Rose, Alexander Kozachinskiy, Tomasz Steifer
2025	A*	`conf`	Ehrenfeucht-Haussler Rank and Chain of Thought. ICML Pablo Barceló, Alexander Kozachinskiy, Tomasz Steifer
2025	J	`jnl`	Ehrenfeucht-Haussler Rank and Chain of Thought. CoRR Pablo Barceló, Alexander Kozachinskiy, Tomasz Steifer
2025	J	`jnl`	Explaining Proc. ACM Manag. Data Pablo Barceló, Alexander Kozachinskiy, Miguel Romero, Bernardo Subercaseaux, José Verschae
2025	J	`jnl`	Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations. CoRR Pablo Barceló, Alexander Kozachinskiy, Miguel A. Romero Orth, Bernardo Subercaseaux, José Verschae
2025	J	`jnl`	Language Generation: Complexity Barriers and Implications for Learning. CoRR Marcelo Arenas, Pablo Barceló, Luis Cofré, Alexander Kozachinskiy
2025	J	`jnl`	Message Passing on the Edge: Towards Scalable and Expressive GNNs. CoRR Pablo Barceló, Fabian Jogl, Alexander Kozachinskiy, Matthias Lanzinger, Stefan Neumann, Cristóbal Rojas
2025	J	`jnl`	NoPE: The Counting Power of Transformers with No Positional Encodings. CoRR Chris Köcher, Alexander Kozachinskiy, Anthony Widjaja Lin, Marco Sälzer, Georg Zetzsche
2025	J	`jnl`	On Computing Probabilistic Explanations for Decision Trees. J. Artif. Intell. Res. Marcelo Arenas, Pablo Barceló, Alexander Kozachinskiy, Miguel Romero, Bernardo Subercaseaux
2025	A*	`conf`	Optimal Bounds for Dissatisfaction in Perpetual Voting. AAAI Alexander Kozachinskiy, Alexander Shen, Tomasz Steifer
2025	J	`jnl`	Optimal bounds for dissatisfaction in perpetual voting. CoRR Alexander Kozachinskiy, Alexander Shen, Tomasz Steifer
2025	J	`jnl`	Strassen Attention: Unlocking Compositional Abilities in Transformers Based on a New Lower Bound Method. CoRR Alexander Kozachinskiy, Felipe Urrutia, Hector Jimenez, Tomasz Steifer, Germán Pizarro, Matías Fuentes, Francisco Meza, Cristian Buc, Cristóbal Rojas
2024	J	`jnl`	Effective Littlestone Dimension. CoRR Valentino Delle Rose, Alexander Kozachinskiy, Tomasz Steifer
2024	B	`conf`	Energy Games over Totally Ordered Groups. CSL Alexander Kozachinskiy
2024	—	`conf`	Infinite Separation Between General and Chromatic Memory. LATIN (2) Alexander Kozachinskiy
2024	A*	`conf`	Logical Languages Accepted by Transformer Encoders with Hard Attention. ICLR Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii
2024	J	`jnl`	Lower bounds on transformers with infinite precision. CoRR Alexander Kozachinskiy
2024	A*	`conf`	On dimensionality of feature vectors in MPNNs. ICML César Bravo, Alexander Kozachinskiy, Cristobal Rojas
2024	J	`jnl`	On dimensionality of feature vectors in MPNNs. CoRR César Bravo, Alexander Kozachinskiy, Cristóbal Rojas
2024	A*	`conf`	Simple online learning with consistent oracle. COLT Alexander Kozachinskiy, Tomasz Steifer
2024	A	`conf`	Towards Simpler Sorting Networks and Monotone Circuits for Majority. APPROX/RANDOM Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
2023	A	`conf`	Constant-Depth Sorting Networks. ITCS Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
2023	J	`jnl`	Continuous Positional Payoffs. Log. Methods Comput. Sci. Alexander Kozachinskiy
2023	A*	`conf`	Find a witness or shatter: the landscape of computable PAC learning. COLT Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Tomasz Steifer
2023	J	`jnl`	Find a witness or shatter: the landscape of computable PAC learning. CoRR Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Tomasz Steifer
2023	J	`jnl`	Inapproximability of sufficient reasons for decision trees. CoRR Alexander Kozachinskiy
2023	J	`jnl`	Logical Languages Accepted by Transformer Encoders with Hard Attention. CoRR Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir V. Podolskii
2023	J	`jnl`	Simple online learning with consistency oracle. CoRR Alexander Kozachinskiy, Tomasz Steifer
2023	A*	`conf`	Three Iterations of (d - 1)-WL Test Distinguish Non Isometric Clouds of d-dimensional Points. NeurIPS Valentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas, Mircea Petrache, Pablo Barceló
2023	J	`jnl`	Three iterations of (d-1)-WL test distinguish non isometric clouds of d-dimensional points. CoRR Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Mircea Petrache, Pablo Barceló
2023	J	`jnl`	Towards Simpler Sorting Networks and Monotone Circuits for Majority. CoRR Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
2023	J	`jnl`	Towards Simpler Sorting Networks and Monotone Circuits for Majority. Electron. Colloquium Comput. Complex. Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
2022	J	`jnl`	Constant-Depth Sorting Networks. CoRR Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
2022	J	`jnl`	Constant-Depth Sorting Networks. Electron. Colloquium Comput. Complex. Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii
2022	J	`jnl`	Energy Games over Totally Ordered Groups. CoRR Alexander Kozachinskiy
2022	J	`jnl`	Infinite Separation between General and Chromatic Memory. CoRR Alexander Kozachinskiy
2022	J	`jnl`	Multiparty Karchmer-Wigderson Games and Threshold Circuits. Theory Comput. Alexander Kozachinskiy, Vladimir V. Podolskii
2022	Misc	`conf`	New Bounds for the Flock-of-Birds Problem. CSR Alexander Kozachinskiy
2022	A	`conf`	One-To-Two-Player Lifting for Mildly Growing Memory. STACS Alexander Kozachinskiy
2022	J	`jnl`	State Complexity of Chromatic Memory in Infinite-Duration Games. CoRR Alexander Kozachinskiy
2021	J	`jnl`	Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. J. Comput. Syst. Sci. Alexander Kozachinskiy, Alexander Shen
2021	B	`conf`	Continuous Positional Payoffs. CONCUR Alexander Kozachinskiy
2021	J	`jnl`	New Bounds for the Flock-of-Birds Problem. CoRR Alexander Kozachinskiy
2021	J	`jnl`	One-to-Two-Player Lifting for Mildly Growing Memory. CoRR Alexander Kozachinskiy
2021	A*	`conf`	Polyhedral Value Iteration for Discounted Games and Energy Games. SODA Alexander Kozachinskiy
2020	J	`jnl`	Continuous Positional Payoffs. CoRR Alexander Kozachinskiy
2020	A	`conf`	Multiparty Karchmer - Wigderson Games and Threshold Circuits. CCC Alexander Kozachinskiy, Vladimir V. Podolskii
2020	J	`jnl`	Multiparty Karchmer-Wigderson Games and Threshold Circuits. CoRR Alexander Kozachinskiy, Vladimir V. Podolskii
2020	J	`jnl`	Multiparty Karchmer-Wigderson Games and Threshold Circuits. Electron. Colloquium Comput. Complex. Alexander Kozachinskiy, Vladimir V. Podolskii
2020	J	`jnl`	Polyhedral value iteration for discounted games and energy games. CoRR Alexander Kozachinskiy
2020	J	`jnl`	Recognizing Read-Once Functions from Depth-Three Formulas. Theory Comput. Syst. Alexander Kozachinskiy
2019	J	`jnl`	Lower bounds on separation automata for Parity Games. CoRR Alexander Kozachinskiy, Mikhail N. Vyalyi
2019	B	`conf`	Two Characterizations of Finite-State Dimension. FCT Alexander Kozachinskiy, Alexander Shen
2018	B	`conf`	From Expanders to Hitting Distributions and Simulation Theorems. MFCS Alexander Kozachinskiy
2018	J	`jnl`	On Slepian-Wolf Theorem with Interaction. Theory Comput. Syst. Alexander Kozachinskiy
2018	B	`conf`	One-Sided Error Communication Complexity of Gap Hamming Distance. MFCS Egor Klenin, Alexander Kozachinskiy
2018	J	`jnl`	Raz-McKenzie simulation: new gadget and unimprovability of Thickness Lemma. CoRR Alexander Kozachinskiy
2018	Misc	`conf`	Recognizing Read-Once Functions from Depth-Three Formulas. CSR Alexander Kozachinskiy
2018	J	`jnl`	Recognizing Read-Once Functions from Depth-Three Formulas. CoRR Alexander Kozachinskiy
2016	Misc	`conf`	On Slepian-Wolf Theorem with Interaction. CSR Alexander Kozachinskiy
2015	Misc	`conf`	Making Randomness Public in Unbounded-Round Information Complexity. CSR Alexander Kozachinskiy
2015	J	`jnl`	On Slepian-Wolf Theorem with Interaction. CoRR Alexander Kozachinskiy
2015	J	`jnl`	Some Bounds on Communication Complexity of Gap Hamming Distance. CoRR Alexander Kozachinskiy