2004-2005 seminars

Given a set of variables, and a set of local constraints over them (e.g. a 3CNF formula) define the "satisfiability-gap" of the system as the smallest fraction of unsatisfiable constraints. We will describe a new proof for the PCP theorem of [AS...

There has been some recent excitement and progress in the long-stalled topic of efficient algorithms for finding equilibria in games and other economic contexts. We discuss some of these developments.

Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is...

Many algorithms can intuitively be classified into one of a few basic paradigms of algorithms, such as greedy algorithms, dynamic programming, LP rounding, local search, etc. It is natural to ask which problems can be solved using these paradigms...

There has been substantial work in learning theory and game theory on adaptive "no-regret" algorithms for problems of repeated decision-making. For example, one could use such an algorithm to choose a path to drive to work each day so that no matter...

Undirected st-connectivity (USTCONN) is the problem of checking whether two given vertices of an undirected graph are connected by a path. Solving USTCONN in space O(log n), and even o(log2 n), is a challenging task. A randomized logspace algorithm...

An Extremal Erdos-Szekeres permutation is a permutation of the numbers 1,2,...,N^2 that has no monotone subsequence of length N+1 (and is therefore extremal with respect to the Erdos-Szekeres theorem). If an EES permutation is drawn uniformly at...

For an undirected graph G=(V,E), let G^n denote the graph whose vertex set is V^n in which two distinct vertices (u_1, u_2, ... ,u_n) and (v_1, v_2, ... ,v_n) are adjacent iff for all i between 1 and n, u_i and v_i are either equal or adjacent. The...

One of the simplest and fundamental distributed computing problems involving noise is the ``noisy broadcast problem'': There are n processors each holding a bit, and there is a special processor called receiver. Processors act according to a...

We study the multicommodity buy-at-bulk network design problem where the goal is to buy capacity on edges of a network so as to enable the demands between a given set of source-sink pairs to be routed - the objective is to minimize the cost of such...