I am an Assistant Professor at the School of Computing and Information Technology of Great Bay University (China). My research area is theoretical computer science, with an emphasis on computational complexity theory and the foundations of machine learning.
Previously, I held postdoctoral positions at CNRS@CREATE LTD. (Singapore) and the School of Computing of the National University of Singapore, hosted by Silviu Maniu and Arnab Bhattacharyya, respectively.
I have earned a PhD in Computing from the Department of Computing of Imperial College London, whereby I worked with Mahdi Cheraghchi on computational complexity theory, an MSc in Logic, Algorithms and Computation from the Department of Mathematics of the University of Athens, whereby I worked with Iordanis Kerenidis and Stathis Zachos on quantum computational complexity theory, and a joint BSc-MSc in Mechanical Engineering from the School of Mechanical Engineering of the National Technical University of Athens, whereby I worked with Evangelos Papadopoulos on robotics.
[CV] [DBLP] [Google Scholar] [ORCiD] [Mathematics Genealogy Project] [LinkedIn] [LeetCode]
Emails: dimyrisiotis[AT]gbu.edu.cn; dimyrisiotis[AT]gmail.com.
Efficient, low-regret, online reinforcement learning for linear MDPs
Joint with
Philips George John,
Arnab Bhattacharyya,
Silviu Maniu,
and
Zhenan Wu.
In submission (2026)
[arXiv]
Algorithms and hardness for estimating statistical similarity
Joint with
Arnab Bhattacharyya,
Sutanu Gayen,
Kuldeep S. Meel,
A. Pavan,
and
N. V. Vinodchandran.
In submission (2026)
[arXiv]
Computational explorations of total variation distance
Joint with
Arnab Bhattacharyya,
Sutanu Gayen,
Kuldeep S. Meel,
A. Pavan,
and
N. V. Vinodchandran.
ICLR 2025 (Spotlight; Top 5.1% of submitted papers)
[arXiv]
[Conference version]
Total variation distance for product distributions is #P-complete
Joint with
Arnab Bhattacharyya,
Sutanu Gayen,
Kuldeep S. Meel,
A. Pavan,
and
N. V. Vinodchandran.
Information Processing Letters (2025)
[arXiv]
[Journal version]
Learnability of parameter-bounded Bayes nets
Joint with
Arnab Bhattacharyya,
Davin Choo,
and
Sutanu Gayen.
SPIGM @ ICML 2024 (Poster)
AAAI 2025
[arXiv]
[Poster]
[Conference version]
Total variation distance meets probabilistic inference
Joint with
Arnab Bhattacharyya,
Sutanu Gayen,
Kuldeep S. Meel,
A. Pavan,
and
N. V. Vinodchandran.
ICML 2024
[arXiv]
[ECCC]
[Conference version]
[Poster]
[YouTube Talk (2024)]
On approximating total variation distance
Joint with
Arnab Bhattacharyya,
Sutanu Gayen,
Kuldeep S. Meel,
A. Pavan,
and
N. V. Vinodchandran.
IJCAI 2023
[arXiv]
[Conference version]
[Poster]
[Oded's Choices]
One-way functions and a conditional variant of MKTP
Joint with
Eric Allender,
Mahdi Cheraghchi,
Harsha Tirumala,
and
Ilya Volkovich.
FSTTCS 2021
[ECCC]
[Conference version]
[Harsha's talk @ FSTTCS 2021]
[Talk @ DIMACS (2022)]
One-tape Turing machine and branching program lower
bounds for MCSP
Joint with
Mahdi Cheraghchi,
Shuichi Hirahara,
and
Yuichi Yoshida.
STACS 2021
Invited to the special issue of Theory of Computing Systems (2022)
[ECCC]
[Conference version]
[Journal version]
[Talk @ STACS 2021]
Algorithms and lower bounds for De Morgan formulas
of low-communication leaf gates
Joint with
Valentine Kabanets,
Sajin Koroth,
Zhenjian Lu,
and
Igor C. Oliveira.
CCC 2020
ACM Transactions on Computation Theory (2021)
[arXiv]
[ECCC]
[Conference version]
[Journal version]
[Talk @ CCC 2020]
Circuit lower bounds for MCSP from local pseudorandom
generators
Joint with
Mahdi Cheraghchi,
Valentine Kabanets,
and
Zhenjian Lu.
ICALP 2019
ACM Transactions on Computation Theory (2020)
[ECCC]
[Conference version]
[Journal version]
On the effects of design parameters on quadruped robot gaits
Joint with Ioannis Poulakakis and Evangelos
Papadopoulos.
ROBIO 2015
[Conference version]
[Conference version PDF]
Quadruped optimum gaits analysis for planetary exploration
Joint with Ioannis Kontolatis,
Iosif Paraskevas,
Evangelos
Papadopoulos,
Guido de Croon,
and
Dario Izzo.
ASTRA 2013
[Conference version PDF]
The complexity and applications of circuit minimization
PhD thesis, Department of Computing, Imperial College London, 2021
[Official version]
Quantum complexity, relativized worlds, and oracle separations
MSc thesis, Department of Mathematics, University of Athens, 2016
[Official version]
Parametric study of the gaits of a quadruped
robot using Hildebrand diagrams
Joint BSc-MSc thesis, School of Mechanical Engineering,
National Technical University of Athens, 2013 (in Greek)
[Official version]