Seminars Sorted by Series

We study properties of random Bernoulli matrices. In particular, we determine the typical value of the determinant. We also obtain a new bound on the probability that the matrix is singular. Joint work with T. Tao.

The Glauber dynamics is a simple Markov chain algorithm for sampling from distributions that arise in models from statistical physics. In each step of this dynamics the value (or spin) of a random site is updated according to some rule which is...

The Glauber dynamics is a simple Markov chain algorithm for sampling from distributions that arise in models from statistical physics. In each step of this dynamics the value (or spin) of a random site is updated according to some rule which is...

Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity with error' problem to higher moduli. It can also be viewed...

I want to show proofs for two things: (1) what kind of complicated structures can a player build in a "generalized Tic-Tac-Toe game", and (2) how to get the "exact solutions" of infinitely many games. I'll try to illustrate the ideas on simple...

A classical method for proving geometric inequalities in which the Euclidean ball is the extremal case, is that of symmetrization. The idea is basically to perform a simple operation on a given convex body in n-dimensional space, which makes it more...

The links between propositional proof systems and bounded arithmetic (a generic name for a collection of first-order theories of arithmetic) have many facets but informally one can view them as two sides of the same thing: The former is a non...

In a sequence of preprints M. Gromov introduced a new model of a random quotient of a finitely generated group and indicated that under favourable conditions the quotient groups should be non-trivial and satisfy Kazhdan's Property (T), both with...

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...

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...

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...

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...

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...

We present the Controlled Linear Programming Problem (CLPP), a new combinatorial optimization problem nicely merging linear programming with games. In a system of linear monotone constraints of the form $x_i\leq p_i^j(\bar x)+w_i^j$, where $p_i^j$...

A graph is called {\em even-hole-free} if no induced subgraph of it is a cycle with an even number of vertices. A vertex of a graph is {\em bisimplicial} if the vertex set of its neighborhood can be partitioned into two cliques. Bruce Reed...

We study the following problem regarding quadratic programs: Given a quadratic polynomial \sum a_{xy} xy, where all a_{xx} = 0, find a -1,+1 assignment to its variables that maximizes it. This problem recently attracted attention due to its...

I will sketch a proof that for any monotone graph property P and any $\epsilon >0$ one can approximate efficiently the minimum number of edges that have to be deleted from an n-vertex input graph to get a graph that satisfies P, up to an additive...

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...

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...

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...

The product replacement algorithm is a commonly used algorithm to generate a random element in a finite group. While its performance is quite outstanding, its theretical understanding is quite poor. We will present a joint work with Igor Pak (JAMS...

I will describe in some detail several different applications of expander graphs, which illuminate the need for explicit constructions of expanders with different properties.

I will present a recent result by Martin Kassabov, which answers affirmatively a 20 year-old open question: Do the symmetric groups S_n contain bounded-size generating sets U_n such that the Cayley graphs C(S_n,U_n) are (bounded-degree) expander...

I will present a recent result by Martin Kassabov, which answers affirmatively a 20 year-old open question: Do the symmetric groups S_n contain bounded-size generating sets U_n such that the Cayley graphs C(S_n,U_n) are (bounded-degree) expander...

Bi-lipschitz embeddings of finite metric spaces into Hilbert space have become an increasingly important tool in discrete mathematics and theoretical computer science. For example, this theory is intimately related to the algorithmic problem of...

We give three different analytic interpretations of Szemeredi's famous Regularity Lemma. The first one is a general statement about Hilbert spaces. The second one presents the Regularity Lemma as the compactness of a certain metric space. The third...

Coding theory emerged in the late 1940's, thanks to the works of Shannon and Hamming, as the theory supporting "reliable transmission of information (in the presence (fear?) of noise)". More than fifty years since, enormous progress has been made...

The Probabilistic Method is a powerful tool in tackling many problems in Combinatorics and it belongs to those areas of mathematical research that have experienced a most impressive growth in recent years. One of the parts of discrete mathematics...

We introduce a metric space which is the closure of the isomorphism classes of graphs in a natural topology. It turns out that the regularity lemma is equivalent with the compactness of this space. We present applications, open questions, and...

Random matrices is a large area in mathematics, with connections to many other areas, such as mathematical physics, combinatorics, and theoretical computer sience, to mention a few. There are, by and large, two kinds of random matrices. The first...

A fundamental question in cryptography is whether the existence of hard on average problems can be based solely on the assumption that P not equal to NP (more precisely, NP not in BPP). The commonly held belief that average-case hardness requires...

We shall discuss Quantum Computing, and the so called Hidden Subgroup Problem, which in the abelian case was the basis for Shor's celebrated factorization algorithm. The solution for non-abelian groups, and symmetric groups in particular, is one of...

Let $G$ be a graph with maximum degree $\Delta$ whose vertex set is partitioned into $r$ parts $V(G)=V_1 \cup \ldots \cup V_r$. An independent transversal is an independent set in $G$ which contains exactly one vertex from each $V_i$. The problem of...

Random covers of graphs, and random group actions on rooted trees, are different languages, that describe the same phenomenon. The former were studied by Amit, Linial. Matousek, Bilu. The latter were studied by Abert and Virag. Let T(n) be a binary...

In 1969 Strassen discovered the surprising fact that it is possible to multiply two 2x2 matrices by using only 7 multiplications. This leads to an algorithm which multiplies two nxn matrices with n^(2.81+o(1)) field operations. Coppersmith and...

The Grothendieck constant of a graph is an invariant whose study, which is motivated by algorithmic applications, leads to several extensions of a classical inequality of Grothendieck. This invariant was introduced in a joint paper with Makarychev...

We consider periodic orbits of multiparameter diagonalizable actions. A simple example of such an action is the action generated by the maps x -> 2x mod 1 and x -> 3x mod 1 on R/Z. There are strong parallels between the study of these orbits and...

We introduce a new algorithm and a new analysis technique that is applicable to a variety of online optimization scenarios, including regret minimization for Lipschitz regret functions, universal portfolio management, online convex optimization and...

I will survey a number of settings withing theoretical computer sceince in which certain computations are abstracted by "black boxes", namely devices for which we can observe the input-output behavior, but not the actual "guts" of the computation. I...

Given the edge density $\rho$ of an undirected graph, what is the minimal possible density $g(\rho)$ of triangles in this graph? This is the quantitative version of the classical Turan theorem (41) that in the asymptotical form can be re-stated as...

Given the edge density $\rho$ of an undirected graph, what is the minimal possible density $g(\rho)$ of triangles in this graph? This is the quantitative version of the classical Turan theorem (41) that in the asymptotical form can be re-stated as...

I will describe some recent results joint with V. Milman in which we take the computer science approach to derandomization and apply it in questions from asymptotic geometric analysis. The special type of questions requires an adaptation of the...

About two years ago Bourgain, Katz and Tao proved that in every finite field, a set which does not grow "much" when we add all pairs of elements, and when we multiply all pairs of elements, must be very "close" to a subfield. This theorem revealed...

While a continuation of last week's lecture, I'll try to make it self contained. I will describe some of the ideas and tools used in the proof of the Sum-Product theorem. I will describe a statistical version, and its use in extractor construction.

In this talk, I shall present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to...