Yiannis Koutis


Associate Professor
Associate Chair of Graduate Studies

GITC 4105
Department of Computer Science
New Jersey Institute of Technology


I am an Associate Professor of Computer Science at the New Jersey Institute of Technology. I am interested in spectral graph theory and its powerful applications in designing algorithms for problems on graphs and hypergraphs with applications in various contexts, including Machine Learning, Electronic Design Automation, and Computational Biology. I am also interested in applications of algebra in the design of exact algorithms for NP-hard problems. My work has received two best paper awards, at ICALP 2017 and ICCAD 2022. I have received support from the National Science Foundation, including an NSF CAREER award.

I have a PhD in Computer Science from Carnegie Mellon University. I obtained my undergraduate Diploma from the Computer Engineering and Informatics Department at the University of Patras, Greece, where I had the honor of being the valedictorian of the University's School of Engineering. Before coming to NJIT, I was faculty in the Computer Science Department at the University of Puerto Rico - Rio Piedras. Earlier I was a Systems Scientist at CMU. I have also spent two semesters as visiting faculty at the Institute of Computational and Experimental Mathematics (Spring 2014) and at the Simon's Institute for the Theory of Computing (Fall 2014) .

research highlights
In my work on linear system solvers for graph Laplacians I have pursued two threads of work on constructing preconditioners. The first thread on subgraph preconditioners, led to an asymptotically optimal algorithm for planar graphs and a near-optimal algorithm for the general case, co-authored with Gary Miller and Richard Peng. Our work improved dramatically upon the previous celebrated work of Spielman and Teng. It was hailed as a "Breakthrough in Algorithm Design" and a "new breed of ultrafast algorithms" for Network Solutions . It also led to an invited article in the prestigious Research Highlights section of the Communications of the ACM.

It was however the second thread on 'super-graph' preconditioners that lived up to the promise of practically fast speed. My implementation of a Combinatorial Multigrid Solver (CMG) has proved very effective for difficult linear systems arising in optimization problems and remains one of the fastest available solvers for graph Laplacians. This led to a number of applied works, including algorithms for hypergraph partitioning, a fundamental problem in Electronic Design Automation. This thread of work has led to a best paper award at ACME/IEEE ICCAD 2022.

On a different front, I have introduced the general "Algebraic Fingerprints" method that has led to the design of faster exact and parameterized algorithms for a multitude of computationally hard problems, including the major breakthrough on the famous Hamiltonian Cycle problem by Andreas Björklund, after more than 50 years of stagnation. About 8 years after my original ICALP 2008 paper, algebraic fingerprints were featured by the ACM. A further collaboration with Andreas Björklund and Petteri Kaski led to more record-breaking algorithms and won the best paper award in ICALP 2017. While I have personally not worked on practical implementations of these algorithms, I was happy to see that they have been used to significantly push the frontier in subgraph detection problems.

At NJIT, I have been teaching Algorithms, Complexity, Machine Learning and Deep Learning. I teach both at the Newark campus and at the magnificent NJIT facility at Jersey City. In 2020, I received the Ying Wu College of Computing Excellence in Teaching Award.