NU CS Dept. Welcomes Dr. Konstantin Makarychev

The aim of my research is to introduce new core techniques and design general principles for developing and analyzing approximation algorithms.

Dr. Konstantin (Kostya) Makarychev

The Computer Science Department at Northwestern University welcomes new tenure-track faculty member Dr. Konstantin (Kostya) Makarychev as an Associate Professor, beginning immediately. Dr. Makarychev’s position is one of the ten new EECS faculty lines in CS which, were announced in June.

"Northwestern CS is thrilled that Kostya Makarychev has joined our faculty. Going beyond traditional worst-case analysis to really understand why certain problems seem much easier in practice than in worst-case has been a long-standing challenge in Computer Science, and one that has proven very difficult to make progress on. Kostya is one of the people who is now beginning to get real results in this critical area.  We¹re delighted to have him as a colleague." said Prof. Larry Birnbaum, CS Division Head & Professor.

Dr. Makarychev’s broad research interest areas are in theoretical computer science, and more specifically he’s interested in approximation algorithms, beyond worst-case analysis, applications of high-dimension geometry to computer science, and combinatorial optimization for designing efficient algorithms for computationally hard problems.

Dr. Makarychev’s explained interest in approximation algorithms and combinatorial optimization, "Optimization algorithms are widely used in business, engineering, and applied sciences. In the past decades, a variety of algorithmic techniques have been developed for solving complex optimization problems. However, despite the enormous success, there are still many challenges in the field. The aim of my research is to introduce new core techniques and design general principles for developing and analyzing approximation algorithms."

Before joining Northwestern, Dr. Makarychev was a researcher beginning in 2012 at Microsoft Research in Redmond, WA and at IBM Research Labs in Yorktown Heights, NY from 2007 to 2012. He obtained his PhD in Computer Science from Princeton University in 2007 (Advisor: Moses Charikar) and BS in Mechanics and Mathematics and MS in M.S. in Pure and Applied Mathematics from the Department of Mechanics and Mathematics at Moscow State University in 2007 (Alexander Shen and  Nikolai Vereshchagin).

Dr. Makarychev is also very interested in applying theory to practice, participating in interdisciplinary research, and developing mathematical methods necessary for designing approximation algorithms.

"I have contributed to the development of combinatorial optimization techniques and devised new ways of algorithm analysis, interpolating between the worst and average cases. I have introduced novel rounding techniques, proposed new types of relaxations (C-SDPs), and studied new SDP constraints. I have designed algorithms for such problems as Balanced Cut, Correlation Clustering, Unique Games, Directed Sparsest Cut, Min Max k–Partitioning, Max Integer Quadratic Programming, Max Quadratic Assignment, Min 2– CNF Deletion, and Max k–CSP", stated Dr. Makarychev.

Read more of Konstantin Makarychev's background on his website.