2004-2005 seminars

In a paper from 1981 Sanders and Witten introduced the (2-Dim) DLA process --- a stochastic growth model, in which a "Discrete fractal" subset of $Z^2$ is grown from the origin in an inductive process, where in each step a particle, starting at...

In this talk we will consider settings where multiple agents each pursue their own selfish interests, each represented by his own objective function. Traditional algorithms design assumes that the problem is described by a single objective function...

We describe four theorems from Combinatorial Number Theory, and sketch their proofs (as time permits). These theorems were important to the recent extractors and Ramsey graphs obtained in [Barak-Impagliazzo-Wigderson] and [Barak-Kindler-Sudakov...

Given a polytope P with a real-valued objective function f on its vertices, we consider the problem of finding a minima of f. Arguably the simplest randomized approach is the simplex algorithm RANDOMEDGE. Sitting at a vertex of P, RANDOMEDGE chooses...

Excited random walk is a process on Z^d which behaves like a regular balanced random walk when it reaches a vertex it already visited, but when it reaches a new vertex it has a drift to the right. We shall review a number of new results about this...

Counting homomorphisms between graphs has a surprising number of applications. Many models in statistical mechanics and many questions in extremal graph theory can be phrased in these terms. We introduce a matrix, which we call the connection matrix...

In this talk, we will discuss additional details of the `SL=L' result, not covered by the first talk. We will focus, however, on the possibility of extending our techniques towards resolving the general RL vs. L question. In this direction we obtain...

We present a deterministic algorithm for graph connectivity that uses the minimal amount of memory possible, up to a constant factor. Specifically, the algorithm's memory is comparable to that needed to store only a single node of the graph (i.e...

We introduce a new graph parameter, called the rothendieck constant of a graph. This parameter is a generalization of the classical Grothendieck constant; and it is equal to an integrality gap of a certain SDP problem, which has various algorithmic...

We study the parallel time-complexity of basic cryptographic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we consider the possibility of computing instances of these primitives by NC0 circuits, in...