Seminars Sorted by Series

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

Solving a system of linear equations is a fundamental algorithmic task arising in numerous applications. It is possible to tell in polynomial time, by Gaussian elimination, if a given system admits a solution, and if so to find one. But what if the...

The sign-rank of a real matrix M is the least rank of a matrix R in which every entry has the same sign as the Corresponding entry of M. We determine the sign-rank of every matrix of the form M=[ D(|x AND y|) ]_{x,y}, where D:{0,1,...,n}->{-1,+1} is...

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many...

Let ||.|| be any norm on R^d. We consider the question of estimating the minimum over all possible sign sequences e_i=+/-1 of ||e_1 x_1 + e_2 x_2 + ... + e_n x_n||, where the x_i are independent Gaussian vectors on R^d (here d is viewed as fixed and...

A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only k bits of the codeword C(x), even after some constant fraction of...

An extension of Szemeredi's Regularity Lemma for hypergraphs, was proved in 2005 by Gowers and independently by Rodl, Schacht, Skokan, and Nagle. More recently, Tao gave another proof for the lemma. A special case, the Removal Lemma is an important...

In this talk, we discuss a new technique which shows how to find a copy of a sparse bipartite graph in a graph of positive density. Our results imply several new bounds for classical problems in Ramsey theory and improve and generalize earlier...

The computation of Nash equilibria has been a problem that spanned half a century that has attracted Economists, Operations Researchers, and most Recently, Computer Scientists. Intuitively, the complexity of a game grows along a few axes: the number...

An important task in systematic biology is the reconstruction of phylogenies: The evolutionary history of a family of organisms, represented by an evolutionary tree, needs to be reconstructed from the genetic data of the extant species, which...

Error correcting codes encode messages in a way that allows recovery of the original message even in the presence of noise. We study Multiplication codes (Akavia-Goldwasser-Safra FOCS'03), extending them in different ways to allow polynomial...

I plan to survey a number of results, some very old and some very new, mainly proving lower bounds on arithmetic circuits. Common to all is the (often surprising, at least till you get used to it) demonstration of the power of partial derivatives.

I will continue with demonstrations of the power of partial drivatives in Arithmetic Complexity and beyond. No background from the previous talk will be needed.

In this talk we will examine some computational problems related to polynomials, namely: (i) Given a polynomial, can we make a linear transformation on the variables and write it as the sum of two independent polynomials. (ii) Is a given set of...

In the past few years there has been much excitement, and many positive and negative results, regarding the computation of equilibria in games. The problem of finding Nash equilibria in games was shown intractable, there is an on-going race of...

We present a tradeoff between the length of a 3-query probabilistically checkable proof of proximity (PCPP) and the best possible soundness obtained by querying it. Consider the task of distinguishing between "good" inputs w \in {0,1}^n that are...

The sign-rank of a real matrix M is the smallest rank of any real matrix whose entries have the same sign as the entries of M . We exhibit a 2^n x 2^n matrix computable by depth 2 circuits of polynomial size whose sign-rank is exponential in n . Our...

The lecture will be a continuation of the previous week (March 4, 2008).