Seminar by Dr. Igor Shinkar (UC Berkeley)

Speaker: Dr. Igor Shinkar (UC Berkeley)                                                                                                                

Title:  On Local-to-Global Phenomena

Date: Monday February 5th, 2018

Time: 10:30am-12pm

Room: EV 3.309

ABSTRACT

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.

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.