![]() |
Udi Weider - TBD Friday, May 10, 2013 - 12:45pm to 3:45pm |
![]() |
The Correct Exponent for the Gotsman-Linial Conjecture Friday, May 3, 2013 - 12:45pm to 3:45pm A (degree-d) polynomial threshold function is a function of the form f(x) = sgn(p(x)) for some (degree-d) polynomial d. The noise sensitivity of a boolean function is the probability that a small change in the input will lead to a change in the output. |
![]() |
Analytical approach to parallel repetition Friday, April 26, 2013 - 12:45pm to 3:45pm We propose an "analytical" framework for studying parallel repetitions of one-round two-prover games. We define a new relaxation of the value of a game, val+, and prove that it is both multiplicative and a good approximation for the true value of the game. |
![]() |
Constant rate PCPs for circuit-SAT with sublinear query complexity Monday, April 29, 2013 - 4:00pm to 7:00pm The PCP theorem says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. |
![]() |
Efficient interactive coding against adversarial noise Friday, April 12, 2013 - 12:45pm to 3:45pm In this talk we will study the problem of constructing interactive |
![]() |
Low-degree testing over small fields Friday, April 5, 2013 - 12:30pm to 3:30pm Let F_q be the field with q elements. We will consider the |
![]() |
Why Laplacian Linear Systems Are Hard, and an Easy Way to Solve Them Quickly Friday, March 22, 2013 - 1:00pm to 4:15pm Fast algorithms for solving Laplacian linear systems have found broad applications across both the theory and practice of computer science, playing a foundational role in scientific computing, machine learning, random processes, image processing, network analysis, and computational biology, among |
![]() |
The Sum of Squares Algorithm: applications, connections, and questions Friday, March 15, 2013 - 1:15pm to 4:15pm The Sum of Squares (SoS) algorithm (Parrilo '00, Lasserre '01) is a semidefinite programming relaxation that has been proposed in various communities under varying names. |