Seminars Sorted by Series

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

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Tao and Ziegler showed some general conditions...

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Tao and Ziegler showed some general conditions...

Affine extractors are maps over F^n that are balanced on every affine subspace of large enough dimension. A random map is, with high probability, a good affine extractor. However so far we do not know how to build explicit affine extractors that are...

Does computing n copies of a function require n times the computational effort? In this work, we give the first non-trivial answer to this question for the model of randomized communication complexity. We show that: 1. Computing n copies of a...

The Parallel Repetition Theorem by Raz is used to amplify the soundness of PCP's, and is one of the ingredients to prove strong inapproximability results. Unfortunately, Raz's proof was very complicated. In these two talks, I will present the...

Planarity is a central theme in graph theory and combinatorial geometry, dating back to Euler. There are many beautiful characterizations of planar graphs such as Kuratowski's forbidden minor theorem and Koebe's circle packing theorem from the 1930s...