Professor Charikar works on designing algorithms that compute approximate solutions. These are important for hard optimization problems where algorithms that compute exact solutions are not known and considered unlikely. Also in a host of “big data” settings, the massive size of data makes traditional algorithms impractical and one must resort to approximate solutions. His work advances these notions of approximation and makes connection between them.
He has earned a number of distinctions during his career including the best paper award at FOCS 2003 for his work on dimension reduction. In 2012, he was awarded the Paris Kanellakis Theory and Practice Award for his work on Locality Sensitive Hashing. He was also named Simons Investigator in Theoretical Computer Science in 2014 at the University of California, Berkeley.