Alex Popa

View my complete CV

Associate Professor
Faculty of Mathematics and Computer Science
University of Bucharest

Senior Researcher (CS II)
National Institute for Research and Development in Informatics


E-mail: alexandru.popa "at" fmi "dot" unibuc "dot" ro



Research interests

  • I am interested in overcoming the computational difficulty of various NP-hard optimization problems via approximation algorithms, fixed parameter algorithms or heuristics.

    • Previous employment

  • Assistant Professor - Nazarbayev University, Kazakhstan. 2015 - 2016
  • Assistant Professor - Masaryk University, Czech Republic. 2013 - 2015
  • Postdoctoral Researcher - Aalto University, Finland. 2011 - 2013

    • Education

  • PhD - University of Bristol. 2008 - 2011
  • Bachelors - University of Bucharest. 2005 - 2008

    • Selected publications (see CV for the complete list)

  • The b-Matching problem in distance-hereditary graphs and beyond. ISAAC 2018. Guillaume Ducoffe, Alexandru Popa
  • The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes. ISAAC 2018. Guillaume Ducoffe, Alexandru Popa
  • Better Heuristic Algorithms for the Repetition Free LCS and Other Variants. SPIRE 2018. Radu-Stefan Mincu, Alexandru Popa
  • Heuristic algorithms for the min-max edge 2-coloring problem. COCOON 2018. Radu-Stefan Mincu, Alexandru Popa
  • Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. SODA 2018. David Coudert, Guillaume Ducoffe, Alexandru Popa
  • Hardness and Approximation of The Asynchronous Border Minimization Problem. Discrete Applied Mathematics 2017. Cindy Y. Li, Alexandru Popa, Prudence W.H. Wong, Fencol C.C. Yung
  • On the (di)graphs with (directed) proper connection number two. LAGOS 2017. Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Alexandru Popa
  • SOBRA - Shielding Optimization for BRAchytherapy. IWOCA 2016. Guillaume Blin, Marie Gasparoux, Sebastian Ordyniak, Alexandru Popa
  • Better Bounds for the Maximum Edge q-Coloring Problem. Journal of Discrete Algorithms 2016. Anna Adamaszek, Alexandru Popa
  • Making "Fast" Atomic Operations Computationally Tractable. OPODIS 2015. Antonio Fernandez Anta, Nicolas Nicolaou, Alexandru Popa
  • A Unifying Framework for Interactive Programming and Applications to Communicating Peer-to-peer Systems. EGC 2015. Alexandru Popa, Iulia Teodora Banu-Demergian, Camelia Chira, Florian Mircea Boian and Gheorghe Stefanescu
  • Parameterized Complexity of Asynchronous Border Minimization. TAMC 2015. Robert Ganian, Martin Kronegger, Andreas Pfandler and Alexandru Popa
  • Explaining a Weighted DAG with Few Paths for Solving Genome-Guided Multiassembly. IEEE/ACM Transactions on Computational Biology and Bioinformatics 2015. Alexandru Tomescu, Travis Gagie, Alexandru Popa, Romeo Rizzi, Anna Kuosmanen, Veli Makinen
  • A Parameterized Study of Generalized Function and Pattern Matching. Algorithmica 2015. Sebastian Ordyniak, Alexandru Popa
  • The 2-Paths Min-Sum Orientation Problem. Theory of Computing Systems 2015. Trevor Fenner, Oded Lachish, Alexandru Popa
  • The Min-max Edge q-Coloring Problem. Journal of Graph Algorithms and Applications 2015. Tommi Larjomaa, Alexandru Popa
  • Algorithmic and Hardness Results for the Colorful Components Problems. Algorithmica 2015. Anna Adamaszek, Alexandru Popa
  • A Parameterized Study of Generalized Function and Pattern Matching. IPEC 2014. Sebastian Ordyniak, Alexandru Popa
  • Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem. IWOCA 2014. Anna Adamaszek, Guillaume Blin, Alexandru Popa
  • The Min-max Edge q-Coloring Problem. IWOCA 2014. Tommi Larjomaa, Alexandru Popa
  • Algorithmic and Hardness Results for the Colorful Components Problems. LATIN 2014. Anna Adamaszek, Alexandru Popa
  • Better lower and upper bounds for the minimum rainbow subgraph problem. Theoretical Computer Science, Volume 543, 2013, pp. 1-8 Alexandru Popa
  • Enumerating Cube Tilings. Discrete and Computational Geometry 2013. K Ashik Mathew, Patric R. J. Östergård, Alexandru Popa
  • On the Shannon Capacity of Triangular Graphs. Electronic Journal of Combinatorics 2013. K Ashik Mathew, Patric R. J. Östergård, Alexandru Popa
  • The Mendelsohn Triple Systems of Order 13. Journal of Combinatorial Designs 2013. Mahdad Khatirinejad, Patric R. J. Östergård, Alexandru Popa
  • The 2-Paths Min-Sum Orientation Problem. WAOA 2013. Trevor Fenner, Oded Lachish, Alexandru Popa
  • Modelling the Power Supply Network - Hardness and Approximation. TAMC 2013. Alexandru Popa
  • Synthesizing Minimal Tile Sets for Complex Patterns in the framework of Patterned DNA Self-Assembly. Theoretical Computer Science. Eugen Czeizler, Alexandru Popa
  • Approximating the Rainbow - Better Lower and Upper Bounds. COCOON 2012. Alexandru Popa
  • Synthesizing Minimal Tile Sets for Complex Patterns in the framework of Patterned DNA Self-Assembly. DNA 2012. Eugen Czeizler, Alexandru Popa
  • On the Closest String via Rank Distance. CPM 2012. Liviu Dinu, Alexandru Popa
  • Hardness and Approximation of The Asynchronous Border Minimization Problem. TAMC 2012. Alexandru Popa, Prudence W.H. Wong and Fencol C.C. Yung
  • Restricted Common Superstring and Restricted Common Supersequence. CPM 2011. Raphael Clifford, Zvi Gotthilf, Moshe Lewenstein, Alexandru Popa
  • Maximum Subset Intersection. Information Processing Letters. Raphael Clifford and Alexandru Popa
  • On Shortest Common Superstring and Swap Permutations. SPIRE 2010. Zvi Gotthilf, Moshe Lewenstein, Alexandru Popa
  • Approximation and hardness results for the maximum edge q-coloring problem. ISAAC 2010. Anna Adamaszek, Alexandru Popa
  • (In)approximability results for pattern matching problems . Prague Stringology Conference 2010 (PSC 2010). Raphael Clifford, Alexandru Popa
  • Generalised Matching. SPIRE 2009. Raphael Clifford, Aram Harrow, Alexandru Popa, Benjamin Sach.
  • Undecidability Results for Finite Interactive Systems . ROMJIST (Romanian Journal of Information Science and Technology) . Alexandru Sofronia, Alexandru Popa, Gheorghe Stefanescu.
  • Undecidability Results for Finite Interactive Systems . Alexandru Sofronia, Alexandru Popa, Gheorghe Stefanescu. SYNASC 2008.
  • Interactive systems with registers and voices and AGAPIA language. Alexandru Popa. Bachelor Thesis, Faculty of Mathematics and Computer Science, University of Bucharest, June 2008
  • High-level Structured Interactive Programs with Registers and Voices. JUCS (Journal of Universal Computer Science) Alexandru Popa, Alexandru Sofronia, Gheorghe Stefanescu.

    • Awards and grants (selection)

  • Innovation Cheque "Optimization algorithms in banking systems", project no. PN-III-P2-2.1-CI-2018-1518, project for cooperation with a partner from industry, September 2018 - December 2018.
  • Mobility project for researchers, project no. EEA-MG-RO-NO-2018-0093, September 2018.
  • Award for top research publication project no. PN-III-P1-1.1-PRECISI-2018-22471, June 2018.
  • National coordinator of the COST Action CA 15210, "European Network for Collaboration on Kidney Exchange Programmes", since February 2018.
  • Mobility project for researchers, project no. PN-III-P1-1.1-MC-2017-0638, November 2017.
  • Erasmus Award to visit Instituto Superior Miguel Torga, March 2018.
  • DAAD fellowship to visit Max-Planck-Institut fur Informatik through programme "Research Stays for University Academics and Scientists", May - July 2018.
  • Erasmus Award to visit Abo Akademi, June 2017.
  • "Biocentrum Helsinki: Connecting Aalto University and University of Helsinki Scientists" research grant (5000 euros) - joint with Elodie Renvoisé - 13 December 2012.
  • "Biocentrum Helsinki: Connecting Aalto University and University of Helsinki Scientists" research grant (5000 euros) - joint with Elodie Renvoisé - 13 December 2012.
  • Travel grant to attend the 12th Max Planck Advanced Course on the Foundations of Computer Science, August 29 - September 2, 2011, Saarbrücken, Germany.
  • Yahoo! Research student support to attend SPIRE 2010, Los Cabos, Mexico, 11-13 October 2010
  • Studentship to attend the DIMAP Workshop on Extremal and Probabilistic Combinatorics, Petersfield, Hampshire, England, 18 - 25 July 2010
  • Fellowship to attend 26th Annual British Colloquium on Theoretical Computer Science (BCTCS 2010), Edinburgh, 6-9 April 2010
  • Fellowship to attend 25th Annual British Colloquium on Theoretical Computer Science (BCTCS 2009), Warwick, 6-9 April 2009
  • Special prize at FameLab 2008 final Romania , Bucharest, Romania, 17 May 2008
  • Thrid place at FameLab 2008 regional selection , Bucharest, Romania, April 2008
  • Erasmus study grant at University of Bristol, Department of Computer Science , September 2007 - January 2008
  • Member of Romanian National Team of Informatics, 2005
  • Special mention at Romanian National Olympiads in Informatics, 2004
  • Special mention at Romanian National Informatics Contest "Great Prize of National Palace of Children", 2004
  • First prize at Romanian National Informatics Contest "Great Prize of National Palace of Children", 2003

    • Academic visits

  • Reykjavik University - September 2018 - hosted by Prof. Magnus Halldorsson
  • Corvinus University of Budapest - April 2018 - hosted by Dr. Peter Biro
  • NISER, India - February 2018 - hosted by Dr. Anisur Rahaman Molla
  • University of Copenhagen - October 2015 - hosted by Dr. Anna Adamaszek
  • TU Vienna - July 2015 - hosted by Dr. Sebastian Ordyniak
  • IMDEA Networks, Madrid - June 2015 - hosted by Prof. Antonio Fernandez Anta
  • A.P. Ershov Institute of Informatics Systems, Novosibirsk - March 2015 - hosted by Prof. Nikolay Shilov
  • LaBRI CS Lab, Bordeaux University - December 2015 - hosted by Prof. Guillaume Blin
  • MPI - June 2014 - hosted by Dr. Anna Adamaszek
  • MPI - July 2013 - hosted by Dr. Anna Adamaszek
  • Marne-la-Vallée University - October 2012 - hosted by Prof. Guillaume Blin
  • Tsinghua University - May 2012
  • University of Liverpool - March 2011 - hosted by Dr. Prudence W.H. Wong
  • KTH Royal Institute of Technology - September 2010 - hosted by Prof. Johan Håstad
  • University of Bar-Ilan - May 2010 - hosted by Prof. Moshe Lewenstein
  • University of Warwick - February 2010 - hosted by Dr. Anna Adamaszek
  • University of Warwick - August 2009 - hosted by Dr. Oded Lachish
  • University of Illinois at Urbana-Champaign - January 2009 - hosted by Prof. Gheorghe Stefanescu

    • Popular science and motivational talks

  • TEDx - "There are not bad countries, only bad people", 4 March 2016.
  • Computers are nothing without maths! from ScienceSLAM Helsinki, 13 December 2011.
  • Instant Scientific Talk Contest - Aalto University Science Day (random talk). Espoo, Finland, 20 September 2012.
  • Sisteme interactive from Famelab Final Romania, 17 May 2008.

    • Teaching

    University of Bucharest
  • Algorithms and Data Structures
  • Advanced Programming Techniques
  • Graph Theory

    • Nazarbayev University
  • Performance and Data Structures
  • CS Track Core - Theory
  • Programming for Scientists and Engineers
  • Networks and Security

    • Masaryk University
  • String Algorithms
  • Compuational Logic
  • Introduction to Algorithms
  • Graph Theory
  • Mathematical Foundations of Computer Science

    • University of Bristol
  • Theory of Computation
  • Advanced Algorithms

    • Current PhD students

  • Radu-Stefan Mincu
  • Camelia Obreja
  • Lucian-Ionut Gavrila

    • Past student supervision

  • Claudiu Gatina, University of Bucharest, BSc 2018
  • Daniel Maxim, University of Bucharest, BSc 2017
  • Vlad Panait, University of Bucharest, BSc 2017
  • Alexandru Traila,University of Bucharest, BSc 2017
  • Katarina Martinova, Masaryk University, MSc 2015
  • Ioannis Marcoullis, University of Bristol, MSc 2011
  • Tommi Larjomaa, Aalto University, MSc 2013
  • K Ashik Mathew, Aalto University, PhD 2015 (co-supervisor)

    • Community service

  • Program committee member: CSE 2018, SYNASC 2014, CONTENT 2013, FUTURE COMPUTING 2013, CONTENT 2012.
  • Reviewer: Theoretical Computer Science, Algorithmica, Journal of Discrete Algorithms, Discrete Applied Mathematics, MFCS 2013, ISAAC 2013, UCNC 2013, WABI 2012, COCOON 2012, CCS 2011, ICALP 2011.

    • Non-academic achievements and activities

  • Recently I have travelled to North Korea and I wrote a book about this experience. You may buy the book here.
  • I like very much literature and poetry (both reading and writing). To view my poems (in Romanian) click here. Please e-mail me if you have any suggestions or critics regarding the poems.
  • I have published the essay O noua forma de libertate (joint work with Oana Gabroveanu) in Gheorghe Paun's magazine Curtea de la Arges .
  • I have published a poem in the collective volume Antologia vinovatelor placeri. Some of the co-authors of this volume are the artists Mircea Albulescu, Tudor Gheorghe and Dorel Visan.
  • Special mention at the International Poetry Contest in Romanian Language STARPRESS 2010 (5612 participants).
  • I have published several poems in Antologia scriitorilor romani din intreaga lume - STARPRESS 2011.
  • I have published eight poems in the collective volume Ce enigmatica esti, femeie... .
  • I also like to play the guitar.
  • Some of my dangerous hobbies are motorcycling and horse riding.
  • I have yellow belt at Judo.