My papers. Back to homepage.

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
  
  
• ENERGY GAMES OVER TOTALLY ORDERED GROUPS [pdf]
  Preprint
  
  
• 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

• CONTINUOUS POSITIONAL PAYOFFS [pdf]
  In CONCUR 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]
  (In Russian).
  PhD Thesis, MSU 2019.
  
  
• TWO CHARACTERIZATIONS OF FINITE-STATE DIMENSION (joint with A. Shen).
  In FCT 2019
  
  

2018

• FROM EXPANDERS TO HITTING DISTRIBUTIONS AND SIMULATION THEOREMS.
  In MFCS 2018
  
  
• ONE-SIDED ERROR COMMUNICATION OF GAP HAMMING DISTANCE (joint with E. Klenin).
  In MFCS 2018
  
  

2016

• ON SLEPIAN-WOLF THEOREM WITH INTERACTION.
  CSR 2016. Best student paper award.
  Journal version: Theory of Computing Systems 62(3), 583-599 (2018).
  
  

2015

• MAKING RANDOMNESS PUBLIC IN UNBOUNDED ROUND INFORMATION COMPLEXITY.
  CSR 2015.