Alexander Kozachinskiy
Двери напоролись на свои ключи
Researcher at CENIA, Chile
Contact: kozmath(at)proton(dot)me
My papers:
2026
-
DECOUPLING POSITIONAL AND SYMBOLIC ATTENTION IN TRANSFORMERS
[pdf]
(with F. Urrutia, J. Salas, C.B. Calderon, H. Pasten, and C. Rojas)
Accepted at ICLR 2026
-
THE COUNTING POWER OF TRANSFORMERS [pdf]
(with C. Köcher, A.W. Lin, M. Sälzer, G. Zetzsche)
Accepted at ICLR 2026
2025
-
LANGUAGE GENERATION: COMPLEXITY BARRIERS AND IMPLICATIONS FOR LEARNING
[pdf]
(with M. Arenas, P. Barceló, and C. Cofré)
Preprint
-
MESSAGE PASSING ON THE EDGE: TOWARDS SCALABLE AND EXPRESSIVE GNNs
[pdf]
(with P. Barceló, F. Jogl, M. Lanzinger, S. Neumann, and C. Rojas)
Preprint
-
ON COMPUTING PROBABILISTIC EXPLANATION FOR DECISION TREES
[pdf]
(with M. Arenas, P. Barcelo, M. Romero, and B. Subercaseaux)
In Journal of Artificial Intelligence Research 83(34), 44 pp (2025)
-
ALL KOLMOGOROV COMPLEXITY FUNCTIONS ARE OPTIMAL, BUT ARE SOME MORE OPTIMAL?
[pdf]
(with B. Bauwens and A. Shen)
Preprint
-
A COMPLETELY UNIFORM TRANSFORMER FOR PARITY [pdf]
(with T. Steifer)
Preprint
-
CONTINUITY AND ISOLATION LEAD TO DOUBTS OR DILEMMAS IN LARGE LANGUAGE MODELS [pdf]
(with H. Pasten, F. Urrutia, H. Jimenez, C. B. Calderon, and C. Rojas)
Accepted at NeurIPS 2025
-
STRASSEN ATTENTION, SPLIT VC DIMENSION, AND COMPOSITIONALITY IN TRANSFORMERS [pdf]
(with F. Urrutia, H. Jimenez, T. Steifer, G. Pizarro, M. Fuentes, F. Meza, C. B. Calderon, and C. Rojas)
Accepted at NeurIPS 2025
-
EHRENFEUCHT-HAUSSLER RANK AND CHAIN OF THOUGHT [pdf]
(with P. Barcelo and T. Steifer)
In ICML 2025.
-
EXPLAINING K-NEAREST NEIGHBORS: ABDUCTIVE AND COUNTERFACTUAL EXPLANATION [pdf]
(with P. Barcelo, M. Romero, B. Subercaseaux and J. Verschae)
In PODS 2025. Distinguished paper award.
-
EFFECTIVE LITTLESTONE DIMENSION [pdf]
(with V. Delle Rose and T. Steifer)
In ALT 2025
-
OPTIMAL BOUNDS FOR DISSATISFACTION IN PERPETUAL VOTING [pdf]
(with A. Shen and T. Steifer)
In AAAI 2025
2024
-
TOWARDS SIMPLER SORTING NETWORKS AND MONOTONE CIRCUITS FOR MAJORITY [pdf]
(with N. Dobrhokhotova-Maikova and V. Podolskii)
In RANDOM 2024
-
SIMPLE ONLINE LEARNING WITH CONSISTENT ORACLE [pdf]
(with T. Steifer)
In COLT 2024
-
ON DIMENSIONALITY OF FEATURE VECTORS IN MPNNS [pdf]
(with C. Bravo and C. Rojas)
In ICML 2024
-
LOGICAL LANGUAGES ACCEPTED BY TRANSFORMERS WITH HARD ATTENTION [pdf]
(with P. Barceló, A. Lin, and V. Podolskii)
In ICLR 2024
-
INFINITE SEPARATION BETWEEN GENERAL AND CHROMATIC MEMORY [pdf]
In LATIN 2024
-
ENERGY GAMES OVER TOTALLY ORDERED GROUPS [pdf]
In CSL 2024
2023
2022
2021
2020
2019
- COMPARISON OF COMMUNICATION, INFORMATION AND DECISION TREE COMPLEXITIES [pdf]
PhD Thesis, MSU 2019.
- TWO CHARACTERIZATIONS OF FINITE-STATE DIMENSION [pdf]
(with A. Shen)
In FCT 2019
2018
2015
- MAKING RANDOMNESS PUBLIC IN UNBOUNDED ROUND INFORMATION COMPLEXITY [pdf]
In CSR 2015.