Abstract: In the first half of this talk, I will talk about the halting problem and show that there are well defined functions f:N->N that no computable function can dominate.
Abstract: The VERTEX GUARD (VG) problem is defined as follows: Given a polygon P (with holes allowed) with n vertices, find a smallest subset S of the set of vertices of P such that every point in the polygon P can be
Abstract: We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. We use information theoretic techniques in our proof.
