Pravesh Kothari, Ph.D.

Pravesh Kothari obtained his bachelor’s degree from the Indian Institute of Technology, Kanpur, and has been a Ph.D. student at the University of Texas at Austin since 2011. His research is focused on hardness of approximation, pseudorandomness and computational learning theory. His papers have appeared in major conferences such as STOC, SODA, CCC, COLT, NIPS and RANDOM. In a recent result with Boaz Barak and Siu On Chan, he proved an exponential lower bound on a large class of constraint satisfaction problems in the sum-of-squares SDP hierarchy. In another recent result, with Raghu Meka, he constructed almost optimal pseudorandom generators for spherical caps. In the past, in a paper with Adam Klivans and Igor Oliveira, he proved a tight relationship between proving circuit lower bounds and designing learning algorithms.