Articles
BY OUR STUDENT CONTRIBUTORS
Malhar Rajpal In my last article, I talked about László Lovász, one of this year’s winners of the prestigious Abel Prize. In this article, I will talk about the background and accomplishments of this year's other recipient, Avi Wigderson.
On 9th September 1956, Avi Wigderson was born in Haifa, Israel. He graduated with a B.Sc. in Computer Science from the Technion (The Israeli Institute of Technology) in 1980. He then went to Princeton University in the USA for his graduate studies, where he completed his PhD in computational complexity under Richard Lipton. Wigderson's major contributions are in the field of computational complexity, which is the study of how quickly computer problems can be solved. You may have heard of the P=NP problem, which is the fundamental question of computational complexity. Computer problems are designated as P (meaning they can be easily solved in polynomial time) or NP (meaning it would take a very long time to solve the problem with known algorithms, but the answer can be verified quickly). Computational complexity is thus founded on the question of whether all the hard to solve problems in the NP set can be reduced to problems that are easy to solve and are in the set P, and thus whether P = NP. This is an unsolved and hotly debated question in mathematics. Wigderson made remarkable developments in this field. One of his biggest achievements is researching how randomness can be used to solve computational problems in a quicker period of time. He showed that if a computer can “flip coins” during the computational process, rather than if the computer chooses each decision, then a solution to a computational problem can be reached in a quicker period of time. This was massive, and it showed that randomness could be used to facilitate a great deal of tasks in the computational world. Dealing with randomness, however, increases the chance of an error in the solution, and therefore Wigderson, with Noam Nisan and Russell Impagliazzo, showed that for any algorithm that uses coin flipping to solve a difficult problem, there is another algorithm that is nearly as fast that uses deterministic (non-random) methods to reach the same solution, under certain conditions. This finding was a huge accomplishment, as it proved that the problem class known as “BPP” in the computer science world was actually the same as the complexity class P, revolutionising the way random algorithms were perceived. Perhaps what Wigderson is most famous for is his co-discovery of the zig-zag product in 2000. The zig-zag product is an innovative finding that links several different fields such as group theory, graph theory, and complexity theory. Very simply put, the zig-zag product of regular graphs is when one takes a large graph and a smaller graph and produces a new graph with the approximate size of the large graph but the degree of the smaller one. According to Wikipedia, it is “a method of combining smaller graphs to produce larger ones used in the construction of expander graphs”. There are, of course, several intricacies to this finding, however they are beyond the scope of this article. The zig-zag product is extremely powerful and carries a huge number of applications, such as finding the optimal way to solve a maze problem. Although he has co-authored over 100 research papers, it would be impossible to cover all of his brilliant ideas in one article. Nonetheless, these achievements alone are truly extraordinary.
8 Comments
26/7/2022 05:02:29 am
https://www.kriptoseyir.com/category/bitcoin-nasil-alinir/
Reply
1/8/2022 05:30:23 pm
Takipçi satın almak artık çok pratik bir işlem oldu. Hızlı bir şekilde takipçi satın al işlemi için hemen sayfamızı ziyaret etmelisiniz.
Reply
19/12/2022 11:43:14 pm
İnstagram takipçi satın almak istiyorsan tıkla.
Reply
5/1/2023 02:00:30 am
100 tl deneme bonusu veren siteleri öğrenmek istiyorsan tıkla.
Reply
27/1/2023 02:40:46 pm
This blog is very informative and helpful
Reply
Leave a Reply. |
Our AuthorsWe are high school and college students from around the world who are passionate about maths, and want to share that passion with others. Categories
All
|