2008-2009 Seminars

We give a (1+eps)-speed Theta(1/eps^2)-competitive nonclairvoyant algorithm for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of total response time.

The dichotomy conjecture asks if every Constraint Satisfaction Problem is either in P or NP-complete. We will study the basic algorithms and reductions for such problems. We will see many (equivalent) stronger versions of this conjecture actually...

Razborov and Rudich have shown that so-called natural proofs are not useful for separating P from NP unless hard pseudorandom number generators do not exist. This famous result is widely regarded as a serious barrier to proving strong lower bounds...

The dichotomy conjecture asks if every Constraint Satisfaction Problem is either in P or NP-complete. We will study the basic algorithms and reductions for such problems. We will see many (equivalent) stronger versions of this conjecture actually...

We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Denoting by val(G) the value of a two-prover unique game G, and by sdp(G) the value of a natural semidefinite program to...

In the lecture we will explain how various fundamental structures from group representation theory appear naturally in the context of discrete harmonic analysis and can be applied to solve concrete problems from digital signal processing. We will...

We study the limits of efficient computation in the context of constructing random-looking graph distributions that can be used to emulate huge random graphs over N=2^n vertices. In particular we study k-wise independent graphs where (as in the...

This talk describes new explicit constructions of dispersers for affine sources of dimension below the notorious n/2 threshold. The main novelty in our construction lies in the method of proof which relies (solely) on elementary properties of...