Avi Wigderson
Encyclopedia
Avi Wigderson is an Israeli mathematician
and computer scientist
, a professor of mathematics at the Institute for Advanced Study
in Princeton
. His research interests include complexity theory
, parallel algorithm
s, graph theory
, cryptography
, distributed computing
, and neural network
s.
, Israel
, graduating in 1980, and went on to graduate study at Princeton University
. He received his Ph.D. in 1983 for work in computational complexity
under the supervision of Richard Lipton. After short-term positions at the University of California, Berkeley
, the IBM Almaden Research Center in San Jose, California
, and the Mathematical Sciences Research Institute
in Berkeley, he joined the faculty of Hebrew University in 1986. In 1999 he also took a position at the Institute for Advanced Study, and in 2003 he gave up his Hebrew University position to take up full-time residence at the IAS.
in 1994 for his work on computational complexity
. Along with Omer Reingold
and Salil Vadhan
he won the 2009 Gödel Prize
for work on the zig-zag product of graphs, a method of combining smaller graphs to produce larger ones used in the construction of expander graph
s.
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
and computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
, a professor of mathematics at the Institute for Advanced Study
Institute for Advanced Study
The Institute for Advanced Study, located in Princeton, New Jersey, United States, is an independent postgraduate center for theoretical research and intellectual inquiry. It was founded in 1930 by Abraham Flexner...
in Princeton
Princeton, New Jersey
Princeton is a community located in Mercer County, New Jersey, United States. It is best known as the location of Princeton University, which has been sited in the community since 1756...
. His research interests include complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, parallel algorithm
Parallel algorithm
In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...
s, graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, distributed computing
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
, and neural network
Neural network
The term neural network was traditionally used to refer to a network or circuit of biological neurons. The modern usage of the term often refers to artificial neural networks, which are composed of artificial neurons or nodes...
s.
Biography
Wigderson did his undergraduate studies at the Technion in HaifaHaifa
Haifa is the largest city in northern Israel, and the third-largest city in the country, with a population of over 268,000. Another 300,000 people live in towns directly adjacent to the city including the cities of the Krayot, as well as, Tirat Carmel, Daliyat al-Karmel and Nesher...
, Israel
Israel
The State of Israel is a parliamentary republic located in the Middle East, along the eastern shore of the Mediterranean Sea...
, graduating in 1980, and went on to graduate study at Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
. He received his Ph.D. in 1983 for work in computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
under the supervision of Richard Lipton. After short-term positions at the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
, the IBM Almaden Research Center in San Jose, California
San Jose, California
San Jose is the third-largest city in California, the tenth-largest in the U.S., and the county seat of Santa Clara County which is located at the southern end of San Francisco Bay...
, and the Mathematical Sciences Research Institute
Mathematical Sciences Research Institute
The Mathematical Sciences Research Institute , founded in 1982, is an independent nonprofit mathematical research institution whose funding sources include the National Science Foundation, foundations, corporations, and more than 90 universities and institutions...
in Berkeley, he joined the faculty of Hebrew University in 1986. In 1999 he also took a position at the Institute for Advanced Study, and in 2003 he gave up his Hebrew University position to take up full-time residence at the IAS.
Awards and honors
Wigderson received the Nevanlinna PrizeNevanlinna Prize
The Rolf Nevanlinna Prize is awarded once every 4 years at the International Congress of Mathematicians, for outstanding contributions in Mathematical Aspects of Information Sciences including:...
in 1994 for his work on computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
. Along with Omer Reingold
Omer Reingold
Omer Reingold is a faculty member of the Foundations of Computer Science Group at the Weizmann Institute of Science, Israel. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs...
and Salil Vadhan
Salil Vadhan
Salil Vadhan is Vicky Joseph Professor of Computer Science and Applied Mathematics at Harvard University. He obtained his PhD in Applied Mathematics from Massachusetts Institute of Technology in 1999, where his advisor was Shafi Goldwasser. His research centers around the interface between...
he won the 2009 Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
for work on the zig-zag product of graphs, a method of combining smaller graphs to produce larger ones used in the construction of expander graph
Expander graph
In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below...
s.