Dimitrios Myrisiotis

职务：Assistant Professor

邮箱：dimyrisiotis@gbu.edu.cn

【科研领域】

       Computational complexity theory; theoretical machine learning

【主要成果】

       Dimitrios works in theoretical computer science, focusing on computational complexity theory and the foundations of machine learning. His research investigates the limits of efficient computation and learning, with contributions spanning circuit complexity, probabilistic inference, distribution learning, and reinforcement learning. He has established new hardness results for fundamental computation models such as De Morgan formulas, as well as for central problems in computational complexity theory such as the Minimum Circuit Size Problem (MCSP), strengthening our understanding of circuit lower bounds and the intrinsic difficulty of core complexity-theoretic problems. In parallel, he has studied the computational aspects of learning structured probabilistic models, proving NP-hardness results for learning Bayes networks even in realizable settings, while also designing algorithms that recover such models from samples. A major thread of his work concerns quantifying differences between probability distributions. He has shown strong hardness results for computing total variation distance and statistical similarity between product distributions and Ising models, while also developing efficient approximation algorithms and uncovering a novel connection between statistical distance estimation and probabilistic inference. These insights yield new algorithms for structured distributions such as tree-structured Bayes networks. More recently, he has contributed to theoretical reinforcement learning by proposing space-efficient and time-efficient variants of RL algorithms for linear Markov decision processes. His long-term goal is to deepen the connections between complexity theory, machine learning, and reinforcement learning in order to design efficient, reliable, and theoretically grounded learning systems.

【学习经历】

       Dimitrios holds a PhD in Computing from the Department of Computing of Imperial College London, where he conducted research in computational complexity theory under the supervision of Mahdi Cheraghchi. He received an MSc in Logic, Algorithms and Computation from the Department of Mathematics of the University of Athens, carrying out research in quantum computational complexity theory under the supervision of Iordanis Kerenidis and Stathis Zachos. He also earned a joint BEng-MEng diploma in Mechanical Engineering from the National Technical University of Athens, where he conducted research in robotics under the supervision of Evangelos Papadopoulos.

【工作经历】

       Prior to joining Great Bay University, Dimitrios served as a Research Fellow at CNRS@CREATE LTD. in Singapore, and as a visiting researcher at the School of Computing at the National University of Singapore, where he was hosted by Arnab Bhattacharyya and Silviu Maniu. Earlier, he held a Research Fellowship in Computer Science at the School of Computing at the National University of Singapore, under the host supervision of Arnab Bhattacharyya.

【代表性论文】

       [1] Efficient, low-regret, online reinforcement learning for linear MDPs

       Joint with Philips George John, Arnab Bhattacharyya, Silviu Maniu, and Zhenan Wu.

       In submission (2026)

       [2] 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)

       [3] 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)

       [4] 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)

       [5] Learnability of parameter-bounded Bayes nets

       Joint with Arnab Bhattacharyya, Davin Choo, and Sutanu Gayen.

       SPIGM @ ICML 2024 (Poster)

       AAAI 2025

       [6] Total variation distance meets probabilistic inference

       Joint with Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, A. Pavan, and N. V. Vinodchandran.

       ICML 2024

       [7] On approximating total variation distance

       Joint with Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, A. Pavan, and N. V. Vinodchandran.

       IJCAI 2023

       [8] One-way functions and a conditional variant of MKTP

       Joint with Eric Allender, Mahdi Cheraghchi, Harsha Tirumala, and Ilya Volkovich.

       FSTTCS 2021

       [9] 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)

       [10] 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)

       [11] 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)

       [12] On the effects of design parameters on quadruped robot gaits

       Joint with Ioannis Poulakakis and Evangelos Papadopoulos.

       ROBIO 2015

       [13] Quadruped optimum gaits analysis for planetary exploration

       Joint with Ioannis Kontolatis, Iosif Paraskevas, Evangelos Papadopoulos, Guido de Croon, and Dario Izzo.

       ASTRA 2013