Christos Kapoutsis holds a B.Sc. in informatics from the Aristotle University of Thessaloniki, Greece and an M.Sc. from the Graduate Program in Logic, Algorithms, and Computation (μΠλΑ) at the University of Athens, Greece. He received his Ph.D. in 2006 from MIT. He worked as postdoctoral researcher at ETH-Zurich and as visiting lecturer at the University of Cyprus. In 2010, he was awarded a Marie Curie Individual Fellowship to work on his project Minicomplexity at LIAFA (Laboratoire d'Informatique Algorithmique: Fondements et Applications) in Paris, France. He joined Carnegie Mellon University in Qatar in 2012.

Ph.D., Computer Science, MIT, Cambridge, MA, USA
M.Sc., Computer Science, MIT, Cambridge, MA, USA
M.Sc., Logic, Algorithms, and Computation (μΠλΑ), University of Athens, Greece
B.Sc., Informatics, Aristotle University of Thessaloniki, Greece

Descriptional complexity
Computational complexity
Descriptive complexity
Theory of computation

Kapoutsis’ main research area is the size complexity of two-way finite automata (2FA). Since 2001, he has worked extensively on the so-called Sakoda-Sipser conjecture. This is a question about the power of non-determinism in size-limited 2FA, which can be viewed as a miniature version of complexity theory's deep open questions on the power of non-determinism. Since 2009, he has also been working on a general size-complexity theory for 2FA, which he likes to call "minicomplexity". Here, the aim is to show that many properties of computation that we observe in standard complexity theory emerge already in machines as weak as the 2FA.

size complexity, two-way finite automata, exact trade-offs, descriptional complexity, minicomplexity, computational complexity, space complexity, descriptive complexity, extremal combinatorics

V. Geffert, C. Kapoutsis, and M. Zakzok. Complement for two-way alternating automata. Acta Informatica (2020).

A. Chatzigeorgiou, R. Dondi, H. Herodotou, C. Kapoutsis, Y. Manolopoulos, G. Papadopoulos, F.Sikora (editors). Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2020). Springer 2020 (LNCS 12011).

C. Kapoutsis and M. Zakzok. Alternation in two-way finite automata. International Conference on Implementation and Application of Automata (CIAA 2019). Invited talk. Extended version to appear in the respective special issue of Theoretical Computer Science.

M. Anabtawi, C. Kapoutsis , S. Hassan, and M. Zakzok. An oracle hierarchy for small one-way finite automata. Proceedings of the International Conference on Language and Automata Theory and Applications (LATA 2019), LNCS 11417, pp. 1–13, 2019.

C. Kapoutsis. Minicomplexity: Some motivation, some history, and some structure. Proceedings of the International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2019), LNCS 11376, pp. 28–38, 2019. Invited talk.

C. Kapoutsis and L. Mulaffer. A logical characterization of small 2NFAs. Proceedings of the International Conference on Implementation and Application of Automata (CIAA 2016), LNCS 9705, pp. 163–175, 2016. Best paper award. Extended version also in the respective special issue of the International Journal of Foundations of Computer Science, 28(5):445–464, 2017.

C. Kapoutsis. Minicomplexity. Proceedings of the International Workshop on Descriptional Complexity of Formal Systems (DCFS 2012), LNCS 7386, pp. 20–42, 2012. Invited talk. Extended version also in the respective special issue of Journal of Automata, Languages and Combinatorics, 17(2–4):205–224, 2012.

C. Kapoutsis and G. Pighizzini. Two-way automata characterizations of L/poly versus NL. Proceedings of the International Computer Science Symposium in Russia (CSR 2012), LNCS 7353, pp. 222–233, 2012. Best paper award. Extended version also in the respective special issue of Theory of Computing Systems, 56(4):662–685, 2015.

C. Kapoutsis. Nondeterminism is essential in small 2FAs with few reversals. Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2011) vol.2, LNCS 6756, pp.192-209, 2011. Extended version also in the respective special issue of Information and Computation, 222:208—227, 2013.

C. Kapoutsis. Size complexity of two-way finite automata. Proceedings of the International Conference on Developments in Language Theory (DLT 2009), LNCS 5583, pp.47–66, 2009. Invited talk.

C. Kapoutsis. Small sweeping 2NFAs are not closed under complement. Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2006), vol.1, LNCS 4051, pp.144-156, 2006.

C. Kapoutsis (translator). Συνκριτά Μαθηματικά: Μια Θεμελίωση της Επιστήμης Υπολογιστών, Klidarithmos Publishing (Athens, Greece), 2013. Greek translation of Concrete Mathematics: A Foundation for Computer Science, by R. Graham, D. Knuth, and O. Patashnik, 2nd ed., Addison-Wesley Professional, 1994.

C. Kapoutsis (translator). Υπολογιστική Γεωμετρία: Αλγόριθμοι και Εφαρμογές, Crete University Press (Heraklion, Greece), 2011. Greek translation of Computational Geometry: Algorithms and Applications, by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, 2nd ed., Springer, 2000.

C. Kapoutsis (translator). Εισαγωγή στη Θεωρία Υπολογισμού, Crete University Press (Heraklion, Greece), 2007. Greek translation of Introduction to the Theory of Computation, by M. Sipser, 2nd ed., Course Technology, 2005.

Member of IFIP Working Group 1.2 “Descriptional Complexity”.

Computer Science Advisor

Advisor to Stellic, Inc.

15-251 Great Theoretical Ideas in Computer Science

15-295 Competition Programming and Problem Solving

15-451 Algorithm Design and Analysis

15-453 Formal Languages, Automata, and Computability

15-455 Undergraduate Complexity Theory

Minicomplexity. Internal seed funding at CMUQ. March 2017–February 2020.

Minicomplexity: Computational Complexity meets Automata Theory. Intra-European Fellowship for Career Development (PIEF-GA-2009-253368). Marie Curie Action within the European Union 7th Framework Programme (FP7/2007-2013 ). September 2010–August 2012.