The University of Arizona

Events & News

CS Colloquium

DateTuesday, September 22, 2015
Time11:00 am
Concludes12:15 pm
LocationGould-Simpson 906
DetailsPlease join us for coffee and light refreshments at 11am, Gould-Simpson, 9th Floor Atrium.

Faculty Host: Alon Efrat
SpeakerMicha Sharir
AffiliationTel-Aviv University

Algebraic Techniques in Geometry: the New Revolution

I will survey the immense progress in combinatorial and computational geometry in the past seven years, triggered by the infusion of techniques from algebraic geometry and algebra, as introduced by Guth and Katz and further developed by the community at large. This has led to solutions of very hard problems, with the crown jewel being a nearly complete solution to Erdos's 1946 problem on distinct distances in the plane.

In this talk I will survey the recent developments. They include new bounds for other variants of the distinct distances problem, new bounds for incidences between points and lines or other geometric entities in various contexts, and re-examination of the theory of Elekes, Ronyai, and Szabo on polynomials vanishing on grids, and numerous applications thereof.

In the (short) time that I will have I will only highlight some of the key developments, and demonstrate the new approach by a few examples.
The talk might assume some basic knowledge in algebra and geometry. Passion for geometric problems
is always a plus.


Micha Sharir received his Ph.D. in Mathematics from Tel Aviv University in 1976, and then switched to Computer Science, doing his postdoctoral studies at the Courant Institute of New York University. He returned to Tel Aviv University in 1980, and has been there, at the School of Computer Science, ever since. He is also a visiting research professor at the Courant Institute, where he has been the deputy head of the Robotics Lab (1985-89). He has served as the head of the Computer Science Department (twice) and as the head of the School of Mathematics (1997-99). He is one of the co-founders of the Minerva Center for Geometry at Tel Aviv University.

His research interests are in computational and combinatorial geometry and their applications. He has pioneered (with Jack Schwartz) the study of algorithmic motion planning in robotics during the early 1980s, and has been involved in many fundamental research studies that have helped to shape the fields of computational and combinatorial geometry. Among his major achievements, in addition to his earlier work on robotics, are the study of Davenport-Schinzel sequences and their numerous geometric applications, the study of geometric arrangements and their applications, efficient algorithms in geometric optimization (including the introduction and analysis of generalized linear programming), and the study of combinatorial problems involving point configurations.

His work won him several prizes, including a Max-Planck research prize (1992, jointly with Emo Welzl), the Feher Prize (1999), the Mif'al Hapais' Landau Prize (2002), and the EMET Prize (2007). He is the incumbent of the Nizri Chair in computational geometry and robotics, a Fellow of the Association for Computing Machinery (since 1997), and has an honorary doctorate degree from the University of Utrecht (1996). He has supervised more than 25 Ph.D. students, many of which are now at various stages of an academic career, in Israel and abroad.