# Christos Kapoutsis

#### Associate Teaching Professor of Computer Science

### Biography

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.

### Education

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

### Area Of Expertise

Descriptional complexity

Computational complexity

Descriptive complexity

Theory of computation

### Research Description

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.

### Research Keywords

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

### Publications

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. Optimal 2DFA algorithms for one-way liveness on two and three symbols. In *Adventures between lower bounds and higher altitudes – Essays dedicated to Juraj Hromkovič on the occasion of his 60th birthday*, LNCS 11011, H.-J. Bökenhauer, D. Komm, and W. Unger eds., pp. 33–48, Springer 2018.

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 and N. Lefebvre. Analogs of Fagin’s Theorem for small nondeterministic finite automata. Proceedings of the *International Conference on Developments in Language Theory *(DLT 2012), LNCS 7410, pp.202–213, 2012.

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. Two-way automata versus logarithmic space. Proceedings of the *International Computer Science Symposium in Russia *(CSR 2011), LNCS 6651, pp.359–372, 2011. Extended version also in the respective special issue of *Theory of Computing Systems*, 55(2):421–447, 2014.

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, R. Královič, and T. Mömke. On the size complexity of rotating and sweeping automata. Proceedings of the *International Conference on Developments in Language Theory *(DLT 2008), LNCS 5257, pp.455–466, 2008. Extended version also in *Journal of Computer and System Sciences*, 78(2):537–558, 2012.

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. Removing bidirectionality from nondeterministic finite automata. Proceedings of the *International Symposium on Mathematical Foundations of Computer Science *(MFCS 2005), LNCS 3618, pp.544–555, 2005.

C. Kapoutsis. Deterministic moles cannot solve liveness. Proceedings of the *International Workshop on Descriptional Complexity of Formal Systems *(DCFS 2005), pp.194–205, 2005. Extended version also in the respective special issue of *Journal of Automata, Languages and Combinatorics*, 12:215–235, 2007.

C. Kapoutsis. From k+1 to k heads the descriptive trade-off is non-recursive. Proceedings of the *International Workshop on Descriptional Complexity of Formal Systems *(DCFS 2004), pp.213–224, 2004. Extended version also in the respective special issue of the *International Journal of Foundations of Computer Science*, 16:943–956, 2005.

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.

### University Service

Computer Science Advisor

### Courses Taught

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

### Academic Projects

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.