Title : Understanding Parallel Repetition Requires Understanding Foams.
Speaker: Ryan O’Donnell
When : March 8th, 4:30-5:30pm
Where : PPB 300
Abstract:
Motivated by important problems in complexity theory (the Unique Games Conjecture) and the foundations of quantum mechanics (QM vs. local hidden variable theories), we investigate the best parameters obtainable in the Parallel Repetition Theorem.
Unfortunately, we don’t get very far.
But, it’s because we get blocked by the following seemingly very hard question from the geometry of “foams”: What is the least surface area of a cell that tiles R^d by the lattice Z^d?
Very little about this foam problem is known. It is so vexing that I will offer monetary rewards for baby steps of progress.
This is joint work with Uri Feige (Microsoft Research/Weizmann) and Guy Kindler (Weizmann).
FRIDAY MARCH 9th, 2007
3:30pm
WEH 7220
Every linear threshold function has a low-weight approximator
Rocco Servedio
Columbia University
A linear threshold function, or halfspace, is defined by a hyperplane w•x=θ through n-dimensional Euclidean space; it assigns a binary label to each input point according to which side of the hyperplane the point lies on. Linear threshold functions are well studied in areas such as learning theory and complexity theory; in particular, linear threshold functions with small integer weights are often of special interest.
Given any linear threshold function f on n Boolean variables, we construct a linear threshold function g which disagrees with f on at most an ε fraction of inputs and has integer weights each of magnitude at most n½ • 2^{Õ(1/ε2)}. The construction is optimal in terms of its dependence on n.
We give two applications. The first is a deterministic algorithm for approximately counting the fraction of satisfying assignments to zero-one knapsack problems to within an additive ±ε. The algorithm runs in time polynomial in n for any constant ε. In our second application, we show that any linear threshold function f is specified to within error ε by estimates of its Chow parameters (degree 0 and 1 Fourier coefficients) which are accurate to within an additive ±1/(n • 2^{Õ(1/ε2)}). This is the first such accuracy bound which is inverse polynomial in n, and gives the first polynomial bound (in terms of n) on the number of examples required for learning linear threshold functions in the “restricted focus of attention” framework.
