Alexander Kozachinskiy

Researcher at CENIA, Chile

Contact: kozmath(at)proton(dot)me

My papers:

2025

• STRASSEN ATTENTION: UNLOCKING COMPOSITIONAL ABILITIES OF TRASNFORMERS BASED ON A NEW LOWER BOUND METHOD [pdf]
  (with F. Urrutia, H. Jimenez, T. Steifer, G. Pizarro, M. Fuentes, F. Meza, C. Buc, and C. Rojas)
  Preprint
  
  
• EHRENFEUCHT-HAUSSLER RANK AND CHAIN OF THOUGHT [pdf]
  (with P. Barcelo and T. Steifer)
  Preprint
  
  
• EFFECTIVE LITTLESTONE DIMENSION [pdf]
  (with V. Delle Rose and T. Steifer)
  Accepted at ALT 2025
  
  
• OPTIMAL BOUNDS FOR DISSATISFACTION IN PERPETUAL VOTING [pdf]
  (with A. Shen and T. Steifer)
  Accepted at AAAI 2025
  
  

2024

• EXPLAINING K-NEAREST NEIGHBORS: ABDUCTIVE AND COUNTERFACTUAL EXPLANATION [pdf]
  (with P. Barcelo, M. Romero, B. Subercaseaux and J. Verschae)
  Preprint
  
  
• 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
  

  [Video, FLaNN seminar 12.02.24]

• INFINITE SEPARATION BETWEEN GENERAL AND CHROMATIC MEMORY [pdf]
  In LATIN 2024
  
  
• ENERGY GAMES OVER TOTALLY ORDERED GROUPS [pdf]
  In CSL 2024
  
  

2023

• CONTINUOUS POSITIONAL PAYOFFS [pdf]
  In Logical Methods in Computer Science 19(3), 10:1–10:40 (2023)
  Preliminary version in CONCUR 2021
  
  
• 3 ITERATIONS OF (d-1)-WL TEST DISTINGUISH NON-ISOMETTRIC CLOUDS OF d-DIMENSIONAL POINTS [pdf]
  (with P. Barcelo, V. Delle Rose, M. Petrache and C. Rojas)
  In NeurIPS 2023
  
  
• FIND A WITNESS OR SHATTER: THE LANDSCAPE OF COMPUTABLE PAC LEARNING [pdf]
  (with V. Delle Rose, C. Rojas and T. Steifer)
  In COLT 2023
  
  
• CONSTANT-DEPTH SORTING NETWORKS [pdf]
  (with N. Dobrhokhotova-Maikova and V. Podolskii)
  In ITCS 2023
  
  

2022

• MULTIPARTY KARCHMER-WIGDERSON GAMES AND THRESHOLD CIRCUITS [pdf]
  (with V. Podolskii)
  In Theory of Computing 18(15), 1-33 (2022)
  Preliminary version in CCC 2020
  
  
• STATE COMPLEXITY OF CHROMATIC MEMORY IN INFINITE-DURATION GAMES [pdf]
  Preprint
  
  
• NEW BOUNDS FOR THE FLOCK-OF-BIRDS PROBLEM [pdf]
  In CSR 2022
  
  
• ONE-TO-TWO-PLAYER LIFTING FOR MILDLY GROWING MEMORY [pdf]
  In STACS 2022
  
  

2021

• AUTOMATIC KOLMOGOROV COMPPLEXITY, NORMALITY AND FINITE-STATE DIMENSION REVISITED [pdf]
  (with A. Shen)
  in Journal of Computer and System Sciences 118, pp. 75-107 (2021).
  
  
• POLYHEDRAL VALUE ITERATION FOR DISCOUNTED GAMES AND ENERGY GAMES [pdf]
  In SODA 2021
  
  

2020

• RECOGNIZING READ-ONCE FUNCTIONS FROM DEPTH-THREE FORMULAS [pdf]
  In Theory of Computing Systems 64(1), 3-16 (2020)
  Preliminary version in CSR 2018. Best student paper award.
  
  

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

• ON SLEPIAN-WOLF THEOREM WITH INTERACTION [pdf]
  In Theory of Computing Systems 62(3), 583-599 (2018)
  Preliminary version in CSR 2016. Best student paper award.
  
  
• FROM EXPANDERS TO HITTING DISTRIBUTIONS AND SIMULATION THEOREMS [pdf]
  In MFCS 2018
  
  
• ONE-SIDED ERROR COMMUNICATION OF GAP HAMMING DISTANCE [pdf]
  (with E. Klenin)
  In MFCS 2018
  
  

2015

• MAKING RANDOMNESS PUBLIC IN UNBOUNDED ROUND INFORMATION COMPLEXITY [pdf]
  In CSR 2015.