In this talk I will give an overview of several different aspects of the "local-to-global phenomena" in large combinatorial objects. Such phenomena occur naturally in many contexts in computer science, including property testing, sublinear time algorithms, coding theory, probabilistically checkable proofs, hardness of approximations, big data, and more.
In the first part of the talk I will focus on "Property Testing", where a typical goal is to infer some global property of a given large object based only on a local view of the object. I will present several results in this context, including some results on "proximity oblivious" testing.
In the second part I will describe some applications of testing to hardness of approximation. In particular, I will present a recent result on hardness of approximating the maximum clique in a given graph in the setting of parameterized complexity.
Igor Shinkar is currently a Post-Doctoral Associate at Courant Institute of Mathematical Sciences, New York University. His host is Prof. Subhash Khot.
Igor's research interests are primarily related to theoretical computer science, combinatorics, probability, and the interplay between them.