Past Event! Note: this event has already taken place.

On local-to-global phenomena

February 15, 2018 at 2:00 PM to 3:30 PM

Location:5345 Herzberg Laboratories


I will give an overview of several aspects of the “local-to-global” phenomena in computer science. Such phenomena occur naturally in many different contexts, including sublinear-time algorithms, coding theory, probabilistically checkable proofs, hardness of approximations, and more.

In the talk we will focus on the field of “Property Testing”, the area concerned with the design of super-fast algorithms for massive datasets. These algorithms distinguish between objects that have some predetermined property and objects that are “far” from having the desired property, while making only a few queries to the given inputs. I will present several results in this area, and discuss their applications to probabilistically checkable proofs, hardness of approximation, and delegation of computation.

No prior knowledge will be assumed.

Short Bio:

Igor Shinkar is postdoctoral scholar in UC Berkeley. His research is in theoretical computer science, discrete mathematics probability, and the interplay between them.  Before coming to Berkeley he was a postdoctoral researcher in the Courant Institute of Mathematical Sciences, NYU.

Igor obtained his PhD from Weizmann Institute of Science, Israel.