Seminars Sorted by Series

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

Combinatorial game theory is the study of combinations of two-player games with no hidden information and no chance elements. The subject has its roots in recreational mathematics, but in its modern form involves a rich interplay of ideas borrowed...

Combinatorial game theory is the study of combinations of two-player games with no hidden information and no chance elements. The subject has its roots in recreational mathematics, but in its modern form involves a rich interplay of ideas borrowed...

The main result of this work is an explicit disperser for two independent sources on $n$ bits, each of entropy $k=n^{o(1)}$. Put differently, setting $N=2^n$ and $K=2^k$, we construct explicit $N \times N$ Boolean matrices for which no $K \times K$...

We investigate the complexity of the following polynomial solvability problem---given a finite field $\mathbb F_q$ and a set of polynomials $f_1, f_2, \dotsc, f_m \in \mathbb F_q[x_1, x_2, \dotsc, x_n]$ of total degree at most $d$, determine the...

Cut problems are fundamental to combinatorial optimization, and they naturally arise as intermediate problems in algorithm design. The study of cut problems is inherently connected to the dual notion of flows. In particular, starting with the...

In this work we study the correlation between low-degree GF(2) polynomials and explicit functions, where the correlation between two functions f,p : {0,1}^n -> {+1,-1} is defined as Correlation(p,f) := | E_x [f(x) p(x)] | = | P_x[f(x) = p(x)] - P_x...

We consider the problem of bounding the absolute value of the correlation between parity and low-degree polynomials modulo q, for odd q >= 3. The boolean function corresponding to the polynomial is 0 on an input iff the polynomial evaluates to 0...

Let $G$ be a graph which contains no subgraphs isomorphic to fixed bipartite graph $H$. Using well known results from Extremal Graph theory, one can show that such $G$ has certain expansion properties, i.e., all small subsets of $G$ have large...

We prove that Cayley graphs of SL_2(Z/qZ) are expanders with respect to the projection of any fixed elements in SL_2(Z) generating a non-elementary subgroup. This expansion property plays crucial role in establishing almost prime version of "SL_2(Z)...

We describe a short and easy-to-analyze construction of constant-degree expanders. The construction relies on the replacement product, applied by Reingold et. al. [2002] to give an iterative construction of bounded-degree expanders. Here we give a...

Polynomial Identity Testing is the following problem: given an arithmetic circuit C, determine if the polynomial computed by it is the identically zero polynomial. This problem admits a randomized polynomial-time algorithm but no efficient...

Sipser and Gács, and independently Lautemann, proved in '83 that probabilistic polynomial time is contained in the second level of the polynomial-time hierarchy, i.e. BPP is in \Sigma_2 P. This is essentially the only non-trivial upper bound that we...

A Property P of functions is said to be testable if there exists a probabilistic algorithm that makes few (constant) queries for the value of f and accepts those satisfying P while rejecting functions that are far from any function satisfying P. In...

A classic functional analytic result by Johnson and Lindenstrauss from 1984 implies that any Euclidean metric on n points can be represented using only k=(log n)/epsilon^2 dimensions with distortion epsilon. In computer science, this result has been...

A Property P of functions is said to be locally testable if there exists a probabilistic algorithm that makes few (constant) queries for the value of f and accepts those satisfying P while rejecting functions that are far from any function...

If A is a subset of a free group with at least two non-Commuting elements, then |AAA| must be almost quadratic in |A|.

We will continue the proof of the following result: if A is a finite subset of a free group with at least two non-commuting elements then |AAA| is almost quadratic in |A|. Last week we reduced the problem to obtaining lower bounds on |ABC| when...

The "Design and Analysis of Algorithms" or "Introduction to Algorithms" is a basic undergraduate course in CS. In such courses, the organizational theme is often in terms of "basic algorithmic paradigms" such as greedy algorithms, dynamic...

In part I of this talk, we began a discussion of "simple algorithms" and restricted our attention to the priority algorithm model which models ``greedy-like'' algorithms. In Part II of this talk, we will extend the priority algorithm framework to...

Linear feedback shift registers (or, equivalently, linear recurrences) have been studied in one form or another for at least 75 years. They have found a Myriad of applications in communications, cryptography, random number generation, and other...

In the first talk I reviewed the basic properties of linear feedback shift registers and their analysis using generating functions and trace functions. I then defined feedback with carry shift registers (FCSRs) and began their analysis by N-adic...

In the past 2 years there has been considerable progress in the algorithmic problem of combining rankings (permutations on a ground set of "candidates") into a consensus ranking. This problem dates back to the 18th century, when the French...

Originally number theoretic methods were used to construct optimal (explicit) expanders. Recently combinatorial methods have been utalized in proving that certain number theoretic graphs are expanders. We will explain some uses of such expanders in...

Consensus clustering is the problem of aggregating a list of clusterings of ground data into one clustering. I will present new approximation algorithms for this problem, building on techniques used for ranking problems (described in my previous...

In this talk we study the one-way multi-party communication model, in which each of the k parties speaks exactly once in its turn. For every fixed k, we prove a tight lower bound of Omega(n^(1/(k-1))) on the probabilistic communication complexity of...

This is joint work with Philipp Hertel Satisfiability algorithms have become one of the most practical and successful approaches for solving a variety of real-world problems, including hardware verification, experimental design, planning and...

I will present Holenstein's (STOC 07) simplification of Raz's (STOC '95) proof of the parallel repetition theorem for two prover games. This theorem is a crucial component in many PCP constructions leading to tight hardness of approximation results...