Dimitrios Myrisiotis

I am a Research Fellow in CNRS@CREATE LTD. (Singapore) hosted by Arnab Bhattacharyya and Silviu Maniu. My research area is theoretical computer science, with an emphasis on the foundations of machine learning and computational complexity theory.

Previously, I was a Research Fellow in Computer Science at the School of Computing of the National University of Singapore, hosted by Arnab Bhattacharyya.

I hold 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 BEng-MEng from the School of Mechanical Engineering of the National Technical University of Athens, whereby I worked with Evangelos Papadopoulos on four-legged robots.

[CV] [DBLP] [Google Scholar] [Mathematics Genealogy Project] [LinkedIn] [LeetCode]

I am in the 2024–2025 academic job market! :)

Contact

Emails: dimitrios.myrisiotis[AT]cnrsatcreate[DOT]sg; dimyrisiotis[AT]gmail[DOT]com.

Papers

In theoretical computer science, the authors are usually ordered alphabetically.

Efficient, low-regret, online reinforcement learning for linear MDPs
Joint with Philips George John, Arnab Bhattacharyya, Silviu Maniu, and Zhenan Wu.
In submission (2024)
[arXiv]

Computational explorations of total variation distance
Joint with Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, A. Pavan, and N. V. Vinodchandran.
In submission (2024)

Estimating statistical similarity between product distributions
Joint with Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, A. Pavan, and N. V. Vinodchandran.
In submission (2024)

Total variation distance for product distributions is #P-complete
Joint with Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, A. Pavan, and N. V. Vinodchandran.
In submission (Journal, 2024)
[arXiv]

Learnability of parameter-bounded Bayes nets
Joint with Arnab Bhattacharyya, Davin Choo, and Sutanu Gayen.
SPIGM @ ICML 2024 (Poster)
In submission (2024)
[arXiv] [Poster]

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]

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 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]

Theses

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 BEng-MEng diploma thesis, School of Mechanical Engineering, National Technical University of Athens, 2013 (in Greek)
[Official version]

The human mind is incapable of formulating (or mechanizing) all its mathematical intuitions, i.e., if it has succeeded in formulating some of them, this very fact yields new intuitive knowledge, e.g., the consistency of this formalism. This fact may be called the “incompletability” of mathematics. On the other hand, on the basis of what has been proved so far, it remains possible that there may exist (and even be empirically discoverable) a theorem proving machine which in fact is equivalent to mathematical intuition, but cannot be proved to be so, nor even be proved to yield only correct theorems of finitary number theory.

―Kurt Gödel