Mahdi Belbasi

I am Mahdi Belbasi, a fourth-year Ph.D. candidate of theoretical computer science at Penn State University working under the supervision of Dr. Martin Fürer. Generally speaking, I am interested in anything related to theoretical CS and combinatorics. Going into depth, my current focus is on Fixed Parameter Tractable (FPT) algorithms, and Approximation Algorithms.

I have done my undergrad in computer engineering and mathematics at Sharif University of Technology, Tehran, Iran. I did my undergrad project (thesis) with Dr. Ebadollah Mahmoodian which was about The Chromatic Number of Finite Group Cayley Tables.

Email: mub329 [at]


News: I will be teaching CMPSC 464 (Theory of Computation) Spring 2020 (as the instructor of the course). I will need few TAs, LAs, and graders. Please contact me if you are a PSU student and interested in filling these positions.

Research Interests:

  • Approximation Algorithms
  • Graph Algorithms and Algebraic Graph Theory
  • Fixed Parameter Tractable Algorithms
  • Computational Complexity
  • Theoretical Machine Learning

Teaching (as a teaching assistant):

  • CMPSC 464 (Theory of Computation) - Fall 2019
  • CMPSC 464 (Theory of Computation) - Spring 2019
  • CMPSC 464 (Theory of Computation) - Fall 2017
  • CMPSC 465 (Algorithm Design) - Spring 2018
  • CSE 565 (Grad-Level Algorithm Design) - Fall 2018

Problems that I am thinking on at the moment:

    • Approximating clique-width with a polynomial factor
    • Approximating treewidth with a faster running time (same ratio as Reed's)
    • Multi-cliqe-width is NP-hard



  • Biking around SC.
  • Playing Badminton (I was a professional player for 9 years)
  • Hitting the gym
  • Playing/Watching Football (in US: "soccer"). I am a huge fan of Bayern Munich and Juventus (except C. Ronaldo).
"I don't want to believe, I want to know!" -Carl Sagan