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)

  • 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

  • "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

    • Universities visited

  • 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.

    • Selected academic talks

  • The 2-Paths Min-Sum Orientation Problem. WAOA 2013, Sophia Antipolis, France, 5-6 September 2013.
  • The Asynchronous Border Minimization Problem. MPI, Saarbrücken, Germany, 16 July, 2013.
  • The Mendelsohn Triple Systems of Order 13. NORCOM 2013, Stockholm, 17-19 June 2013.
  • Modelling the Power Supply Network - Hardness and Approximation. TAMC 2013, Hong Kong, 20-22 May 2013.
  • The maximum edge q-coloring problem. Masaryk University, Brno, Czech Republic, 16 january, 2013.
  • The Asynchronous Border Minimization Problem. Marne-la-Vallée University, Champs-sur-Marne, France, 2 October, 2012.
  • Approximating the Rainbow - Better Lower and Upper Bounds. COCOON 2012, Sydney, Australia, 20-22 August, 2012
  • Hardness and Approximation of The Asynchronous Border Minimization Problem. TAMC 2012, Beijing, China, 16-21 May, 2012.
  • The maximum edge q-coloring problem. University of Helsinki, Helsinki, Finland, 2 December 2011.
  • The maximum edge q-coloring problem. University of Liverpool, Liverpool, United Kingdom, 17 March 2011.
  • Approximation and hardness results for the maximum edge q-coloring problem. ISAAC 2010, Jeju Island, South Korea, 15-17 December 2010.
  • On Shortest Common Superstring and Swap Permutations. SPIRE 2010, Los Cabos, Mexico, 11-13 October 2010.
  • Approximation and hardness results for the maximum edge q-coloring problem. KTH Royal Institute of Technology, Stockholm, Sweden, 24 September, 2010.
  • (In)approximability results for pattern matching problems. Prague Stringology Conference 2010, Prague, Czech Republic, August 30 - September 1, 2010.
  • Tree Decomposition of Graphs. DIMAP Workshop on Extremal and Probabilistic Combinatorics, Petersfield, Hampshire, England, 18 - 25 July 2010
  • Permuted Common Supersequence . BCTCS 2010 . University of Edinburgh, 6-9 April 2010.
  • (In)approximability results for problems inspired from biology . University of Bucharest, 29 March 2010.
  • Generalized Matching . SPIRE 2009 . Saariselkä, Finland, 25-27 August 2009.
  • Interactive Programs with Registers and Voices - Foundations. GlobalComp Workshop , Technical University Cluj-Napoca, Romania, 26 February 2008
  • High Level Structured Programs with Registers and Voices: Agapia v0.2 Language. GlobalComp Workshop , Technical University Cluj-Napoca, Romania, 26 February 2008

    • Teaching

    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
  • Alexandru Gheorghita (co-supervised with Prof. Florin Pop)

    • Past student supervision

  • 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: 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 metion 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.