Are Typical Instances of Combinatorial Optimization Problems Hard to Solve?

When: Friday, March 23, 2018
Where: PGH 232
Time: 11:00 AM

Speaker: Prof. Prasad Tetali, Georgia Tech

Host: Prof. Gopal Pandurangan

During the past decade, there has been a flurry of research activity at the interface of several fields, including applied probability, combinatorics, statistical physics and theory of computing, in attempts to understand the sources of hardness of solving random instances of many important combinatorial optimization problems. The problems include (random instances of) k-SAT, MAX-CUT, maximum independent set and coloring in graphs, hypergraph 2-coloring etc. Thanks to exciting interdisciplinary collaborations, there is now a much better understanding of the geometric structure of the solution space, thresholds for the existence of solutions versus potential limits of local algorithms to find solutions etc., for several of these problems.

The speaker will attempt to review the state of the art on some of the problems from this exciting field.

Bio:

Prasad Tetali holds a Regents' Professor position in the Schools of Mathematics and Computer Science at Georgia Tech. Most recently he served as the Associate Chair for Research in the School of Mathematics, after serving as the Interim Chair of the School for two years (2015-16). He got his Ph.D. from the Courant Institute of Mathematical Sciences (NYU) in 1991. Following a postdoctoral study as the Member of Technical Staff at AT & T Bell Labs in Murray Hill (NJ), he joined Georgia Tech in 1994. His research interests span discrete mathematics, probability and theory of computing.

Tetali served as the Editor-in-Chief of the SIAM Journal of Discrete Mathematics (2009-2011), and as the Director of Georgia Tech’s interdisciplinary research Think-Tank, Algorithms & Randomness Center (ARC) during 2011-2014. He is recognized as an inaugural SIAM Fellow (2009) and an inaugural AMS Fellow (2012).