I am a research fellow in Computer Science at the School of Computing of the National University of Singapore, hosted by Arnab Bhattacharyya. My research interests are computational complexity theory, computational learning theory, and causality.
Previously, I earned a PhD in Computing from the Department of Computing of Imperial College London, whereby I was advised by Mahdi Cheraghchi. I hold a MSc in Logic, Algorithms and Computation from the Department of Mathematics of the University of Athens, and a joint BEng-MEng diploma from the School of Mechanical Engineering of the National Technical University of Athens. During my studies at the Department of Mathematics, I worked with Stathis Zachos and Iordanis Kerenidis on quantum computational complexity theory, and during my studies at the School of Mechanical Engineering, I worked with Evangelos Papadopoulos on four-legged robots.
[CV] [DBLP] [Google Scholar] [LinkedIn]
NUS School of Computing, COM1,
13 Computing Dr, Singapore 117417
dimyrisiotis [AT] gmail [DOT] com
On approximating total variation distance
Joint with Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, A. Pavan, and N. V. Vinodchandran.
One-way functions and a conditional variant of MKTP
Joint with Eric Allender, Mahdi Cheraghchi, Harsha Tirumala, and Ilya Volkovich.
[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.
Invited to the special issue of Theory of Computing Systems (2022)
[ECCC] [Conference 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.
ACM Transactions on Computation Theory (2021)
[ECCC] [arXiv] [Conference version] [Journal version] [Talk @ CCC 2020]
Circuit lower bounds for MCSP from local pseudorandom
Joint with Mahdi Cheraghchi, Valentine Kabanets, and Zhenjian Lu.
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.
[Conference version PDF]
Quadruped optimum gaits analysis for planetary exploration
Joint with Ioannis Kontolatis, Iosif Paraskevas, Evangelos Papadopoulos, Guido de Croon, and Dario Izzo.
[Conference version PDF]
The complexity and applications of circuit minimization
PhD thesis, Department of Computing, Imperial College London, 2021
Quantum complexity, relativized worlds, and oracle separations
MSc thesis, Department of Mathematics, University of Athens, 2016
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)