Prasad Raghavendra is an Indian-American theoretical computer scientist and mathematician, working in

optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

, complexity theory,

approximation algorithms In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solut ...

hardness of approximation In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. Scope Hardness of approximation complements the study of approximation algorithms by pro ...

and statistics. He is a professor of computer science at the

University of California at Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant uni ...

Education

After completing a BSc at

IIT Madras Indian Institute of Technology Madras (IIT Madras) is a public technical university located in Chennai, Tamil Nadu, India. As one of the Indian Institutes of Technology (IITs), it is recognized as an Institute of National Importance and has ...

in 2005, he obtained an MSc (2007) and PhD (2009) at the

University of Washington The University of Washington (UW, simply Washington, or informally U-Dub) is a public research university in Seattle, Washington. Founded in 1861, Washington is one of the oldest universities on the West Coast; it was established in Seat ...

under the supervision of

Venkatesan Guruswami Venkatesan Guruswami (born 1976) is a senior scientist at the Simons Institute for the Theory of Computing and Professor of EECS and Mathematics at the University of California, Berkeley. He did his high schooling at Padma Seshadri Bala Bhavan ...

. After a postdoctoral position at

Microsoft Research New England Microsoft Research (MSR) is the research subsidiary of Microsoft. It was created in 1991 by Richard Rashid, Bill Gates and Nathan Myhrvold with the intent to advance state-of-the-art computing and solve difficult world problems through technologi ...

, he became faculty at the

Career

Raghavendra showed that assuming the

unique games conjecture In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate ''value'' of a certain type of ga ...

semidefinite programming Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positiv ...

is the optimal algorithm for solving constraint satisfaction problems. Together with

David Steurer David Steurer is a German theoretical computer scientist, working in approximation algorithms, hardness of approximation, sum of squares, and high-dimensional statistics. He is an associate professor of computer science at ETH Zurich. Biography ...

, he developed the

small set expansion hypothesis The small set expansion hypothesis or small set expansion conjecture in computational complexity theory is an unproven computational hardness assumption. Under the small set expansion hypothesis it is assumed to be computationally infeasible to d ...

, for which they won the Michael and Shiela Held Prize in 2018. He developed

sum of squares In mathematics, statistics and elsewhere, sums of squares occur in a number of contexts: Statistics * For partitioning of variance, see Partition of sums of squares * For the "sum of squared deviations", see Least squares * For the "sum of squar ...

as a versatile algorithmic technique. Together with David Steurer, he gave an invited talk on the topic at the 2018 ICM.

References

{{DEFAULTSORT:Raghavendra, Prasad Indian computer scientists Indian mathematicians Living people University of Washington alumni Year of birth missing (living people) 20th-century American mathematicians 21st-century American mathematicians