Seminars Sorted by Series

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

Current constructions of cryptographic primitives typically involve a large multiplicative computational overhead that grows with the desired level of security. We explore the possibility of implementing cryptographic primitives (such as encryption...

I will present a recent result of Green and Tao showing the following. Let P:F^n --> F be a polynomial in n variables over F of degree at most d . We say that P is "equidistributed" if it takes on each of its |F| values close to equally often. We...

We give a probabilistic protocol that allows any two points in R^d to agree on a nearby integer lattice point in Z^d . The protocol uses shared randomness, but no communication. If the distance between the two points is delta, the probability of...

I will describe a lower bound for the rank of any real matrix in which all diagonal entries are significantly larger in absolute value than all other entries. This simple result has a surprising number of applications in Geometry, Coding Theory...

Moran, Naor and Segev have asked what is the minimal r = r(n, k) for which there exists an (n,k)-monotone encoding of length r , i.e., a monotone injective function from subsets of size up to k of {1, 2,...,n} to r bits. Monotone encodings are...

A 3-uniform hypergraph is hamiltonian if for some cyclic ordering of its vertex set, every 3 consecutive vertices form an edge. In 1952 Dirac proved that if the minimum degree in an n-vertex graph is at least n/2 then the graph is hamiltonian. We...

We consider several natural problems related to the design of approximation algorithms and the analysis of their error bounds. We define a set of sufficient conditions on a function $f:D --> R^+$ and its domain $D$ , so that we can construct good...

Abstract: Studying dynamical systems is key to understanding a wide range of phenomena ranging from planets' movement to climate patterns to market dynamics. Various numerical tools have been developed to address specific questions about dynamical...

Pseudo-random generators that are secure against constant depth polynomial size circuits have been known since the seminal paper by Ajtai and Wigderson (1985). All available constructions of such generators, however, appear to be somewhat special...

Nisan and Wigderson defined the model of multilinear circuits as a natural model for computing multilinear polynomials (such as matrix product and the Permanent). We will go over several results regarding such circuits -- a few structural results...

Nisan and Wigderson defined the model of multilinear circuits as a natural model for computing multilinear polynomials (such as matrix product and the Permanent). We will go over several results regarding such circuits -- a few structural results...

One natural strategy for proving a time lower bound for a problem is proof-by-contradiction: assume that there is a great algorithm for the problem, and apply this algorithm as a subroutine to solve other problems until the algorithms get so great...

A celebrated theorem of Razborov/Smolensky says that constant depth circuits comprising AND/OR/MOD_{p^k} gates of unbounded fan-in, require exponential size to compute the MAJORITY function if p is a fixed prime and k is a fixed integer. Extending...

A celebrated theorem of Razborov/Smolensky says that constant depth circuits comprising AND/OR/MOD_{p^k} gates of unbounded fan-in, require exponential size to compute the MAJORITY function if p is a fixed prime and k is a fixed integer. Extending...

In the lecture we will explain how various fundamental structures from group representation theory appear naturally in the context of discrete harmonic analysis and can be applied to solve concrete problems from digital signal processing. We will...

The dichotomy conjecture asks if every Constraint Satisfaction Problem is either in P or NP-complete. We will study the basic algorithms and reductions for such problems. We will see many (equivalent) stronger versions of this conjecture actually...

The dichotomy conjecture asks if every Constraint Satisfaction Problem is either in P or NP-complete. We will study the basic algorithms and reductions for such problems. We will see many (equivalent) stronger versions of this conjecture actually...

I will outline the general area of proof complexity, and its traditional problems. I will focus on less traditional ones, namely the complexity of proving identities over certain algebraic structures. The paradigmatic example is a system intended to...

I will outline the general area of proof complexity, and its traditional problems. I will focus on less traditional ones, namely the complexity of proving identities over certain algebraic structures. The paradigmatic example is a system intended to...

Combinatorial arguments have played a crucial role in the investigation of several surprising phenomena in Information Theory. After a brief discussion of some of these results I will describe a recent example, based on joint work with Hassidim...

In this work we study the task of randomness extraction from sources which are distributed uniformly on an unknown algebraic variety. In other words, we are interested in constructing a function (an extractor) whose output is close to uniform even...

In this work we study the task of randomness extraction from sources which are distributed uniformly on an unknown algebraic variety. In other words, we are interested in constructing a function (an extractor) whose output is close to uniform even...

Mechanism design is not robust. It traditionally guarantees a desired property "at equilibrium", but an equilibrium is by definition very fragile: it only guarantees that no INDIVIDUAL player can profitably deviate from his envisaged strategy. Two...

Amplifying the difficulty of a somewhat hard function is a central technique in complexity, cryptography and pseudorandomness. By far the most common method of amplification is by repetition - asking to compute the original function in many...

We will describe the recent proof of the 1990 Linial-Nisan conjecture. The conjecture states that bounded-depth boolean circuits cannot distinguish poly-logarithmically independent distributions from the uniform one. The talk will be almost...