2007-2008 seminars

In the past few years there has been much excitement, and many positive and negative results, regarding the computation of equilibria in games. The problem of finding Nash equilibria in games was shown intractable, there is an on-going race of...

We prove strong lower bounds for Sherali-Adams relaxations of the MAX CUT, Vertex Cover and Sparsest Cut problems. Specifically, we show that the integrality gap of MAX CUT and Vertex Cover relaxations is 2-$\epsilon$ after n^delta rounds (where...

In this talk we will examine some computational problems related to polynomials, namely: (i) Given a polynomial, can we make a linear transformation on the variables and write it as the sum of two independent polynomials. (ii) Is a given set of...

A given function f(x) is "hard on average" with respect to an algorithm A , if A(x) disagrees with f(x) on "many" inputs x. Applications in cryptography and derandomization require functions that are "very hard on average" (essentially unpredictable...

I will continue with demonstrations of the power of partial drivatives in Arithmetic Complexity and beyond. No background from the previous talk will be needed.

Avoider-Enforcer games are a misere version of somewhat more popular Maker-Breaker games. An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph H=(V,E) (typically the vertices of H are the edges of the...

I plan to survey a number of results, some very old and some very new, mainly proving lower bounds on arithmetic circuits. Common to all is the (often surprising, at least till you get used to it) demonstration of the power of partial derivatives.

Hardness amplification is a major line of research that mainly seeks to transform a given lower bound (e.g. a function that has correlation at most 99% with small circuits) into a strongly average-case one (i.e. a function that has negligible...

Error correcting codes encode messages in a way that allows recovery of the original message even in the presence of noise. We study Multiplication codes (Akavia-Goldwasser-Safra FOCS'03), extending them in different ways to allow polynomial...

We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: 1. Each comparison can be erroneous with some probability 1 - p. 2. At each stage k comparisons can be performed in parallel and a noisy answer...