Seminars Sorted by Series

Graph Min-Bisection is the following problem: Given a graph, partition it into two equal parts so as to minimize the number of crossing edges. The problem arises as a subroutine in many graph algorithms that rely on divide-and-conquer strategy...

Graph Min-Bisection is the following problem: Given a graph, partition it into two equal parts so as to minimize the number of crossing edges. The problem arises as a subroutine in many graph algorithms that rely on divide-and-conquer strategy...

A celebrated 1976 theorem of Aumann asserts that honest, rational Bayesian agents will never "agree to disagree": if their opinions about any topic are common knowledge, then those opinions must be equal. Economists have written numerous papers...

A classical theorem of Edmonds provides a min-max formula relating the maximal size of a set in the intersection of two matroids to a ``covering" parameter. In this talk we generalize this theorem, replacing one of the matroids by a general...

The main goal of this talk will be to present a proof of the following theorem. Theorem 1: For every fixed \delta >0 here is a polynomial time (in n = log N) computable function(s) f:[N]x[N]-->{0,1}, for which the following hold. For every two sets...

We consider "local-update" Markov chains for sampling from independent sets and proper 3-colourings of a graph. An example of such a chain is the well-known Glauber dynamics, which updates the state of at most one vertex of the graph at each step...

We consider "local-update" Markov chains for sampling from independent sets and proper 3-colourings of a graph. An example of such a chain is the well-known Glauber dynamics, which updates the state of at most one vertex of the graph at each step...

We consider the complexity of properly learning concept classes, i.e. when the learner must output a hypothesis of the same form as the unknown concept. We present the following new upper and lower bounds on well-known concept classes: 1. We show...

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