Prasad Raghavendra is an Indian-American

theoretical computer scientist Theoretical computer science is a subfield of computer science and mathematics that focuses on the abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The ACM's Special Inter ...

and mathematician, working in

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

, 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 sol ...

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 Statistics (from German language, German: ', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a s ...

. 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, United States. Founded in 1868 and named after the Anglo-Irish philosopher George Berkele ...

Education

After completing a BTech at

IIT Madras The Indian Institute of Technology Madras (IIT Madras or IIT-M) is a public technical university located in Chennai, Tamil Nadu, India. It is one of the eight public Institutes of Eminence of India. As an Indian Institute of Technology (IIT), ...

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

University of Washington The University of Washington (UW and informally U-Dub or U Dub) is a public research university in Seattle, Washington, United States. Founded in 1861, the University of Washington is one of the oldest universities on the West Coast of the Uni ...

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 Bhav ...

. 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 g ...

semidefinite programming Semidefinite programming (SDP) is a subfield of mathematical programming 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 po ...

is the optimal algorithm for solving

constraint satisfaction problems Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite const ...

. 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 as a versatile algorithmic technique. Together with David Steurer, he gave an invited talk on the topic at the 2018

ICM ICM may refer to: Organizations * Irish Church Missions, an Anglican mission * Institut du Cerveau, the Paris Brain Institute, a research center * Interdisciplinary Centre for Mathematical and Computational Modelling, University of Warsaw * Interna ...

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