Seminars Sorted by Series

Suppose we have n players who wish to jointly perform a quantum computation, but some of them are faulty and are trying to learn privileged information and/or sabotage the computation. How many cheaters can we tolerate and still have a secure...

We consider biased positional games, played on the edge set of a complete graph Kn on n vertices. These games are played by two players, called Maker and Breaker, who take turns in claiming previously unoccupied edges of Kn. Maker claims a single...

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are...

We say a problem is tractable on average if it can be solved on a "good" fraction of instances by an efficient algorithm. To make this definition precise, we need to make two choices: First, what is a "good" fraction of instances - is it 1%, 51%, 99...

Algorithms based on convex optimization, especially linear and semidefinite programming, are ubiquitous in Computer Science. While there are polynomial time algorithms known to solve such problems, quite often the running time of these algorithms is...

A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a network and a collection of source-destination pairs in the network. The goal is to maximize the number of pairs that can be connected by...

The Internet is an indispensable part of our information society, and yet its basic foundations remain vulnerable to simple attacks, and one area that remains especially susceptible to attack is routing. There have been increasing efforts in the...

We present approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (MAX k-CSP). Given a (1-epsilon) satisfiable 2CSP our first algorithm finds an assignment of variables satisfying a 1 - O(sqrt...

Traditional algorithm design is being challenged by the remarkable technological advances in data acquisition of recent years. Today's algorithms must often cope with data that is massive, noisy, uncertain, high-dimensional, nonuniformly priced...

In 1951 Nash proved that every game has a Nash equilibrium. The proof is non-constructive, reducing the existence of Nash equilibria to that of Brouwer fixpoints. Whether Nash equilibria can be computed efficiently had remained open. I shall outline...

We develop a framework for obtaining (deterministic) Fully Polynomial Time Approximation Schemes (FPTASs) for stochastic univariate dynamic problems with either convex or monotone single-period cost functions. Using our framework, we give the first...

Program checking, program self-correcting and program self-testing were pioneered by [Blum and Kannan] and [Blum, Luby and Rubinfeld] in the mid eighties as a new way to gain confidence in software, by considering program correctness on an input by...

This subject began in the late 1940s with the opus of Shannon [1948] and the short papers of Hamming [1950] and Golay [1949], followed a decade later by the powerful constructions of Bose-Chaudhuri-Hocquenghem and Reed-Solomon. A variety of...

We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since * reachability on grid graphs is logspace-equivalent to reachability in general...

Buy-at-bulk network design problems arise in telecommunication networks and related fields where economies of scale result in concave cost functions for purchasing bandwidth. A basic problem in this area is the following. We are given a graph G=(V,E...

This talk is devoted to linear subspaces of $R^N$ on which $\ell_1$ and $\ell_2$-norms are closed to each other (up to the obvious normalizing factor $N^{1/2}$). Such ``sections'' are important e.g. in the theory of metric embeddings, and for many...

The Fast Johnson-Lindenstrauss Transorm was recently discovered by Ailon and Chazelle as a technique for performing fast dimension reduction from $\ell_2^d$ to $\ell_2^k$ in time $O(\max\{d\log d, k^3\})$, where $k$ is the target lower dimension...

Any proof of P!=NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers...

Is it possible for two intelligent players to communicate meaningfully with each other, without any prior common background? What does it even mean for the two players to understand each other? In addition to being an intriguing question in its own...

In a breakthrough result, Razborov (2003) gave optimal lower bounds on the communication complexity of every function f of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in the bounded-error quantum model with and without prior...

In their great 1960 paper "On the Evolution of Random Graphs" Paul Erdos and Alfred Renyi expresses a special interest in the behavior of the random graph G(n,p) when np was near one. Today we view it through the prism of Percolation Theory. Write c...

In this work we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine...

A theorem of Green, Tao and Ziegler can be stated (roughly) as follows: if R is a pseudorandom set, and X is a dense subset of R, then there is a "model" Y for X such that Y is a dense set and X and Y are indistinguishable. (The precise statement...

The notion of a ``market'' has undergone a paradigm shift with the Internet -- totally new and highly successful markets have been defined and launched by companies such as Google, Yahoo!, Amazon, MSN and Ebay. These markets are computationally...

Valiant's theory of holographic algorithms is a new design method to produce polynomial time algorithms. Information is represented in a superposition of linear vectors in a holographic mix. This mixture creates the possibility for exponential sized...

A network creation game abstracts a network construction by selfish agent who build a network by buying links to each other. Each player pays a fixed cost per link, and suffers an additional communication cost (which is the sum of distances to the...

I will present a result that shows hardness of weak PAC-learning intersection of two halfspaces using a hypothesis which is an intersection of k halfspaces for any (fixed) integer k. Specifically, for every integer k and an arbitrarily small...

A graph separator is a set of edges whose deletion partitions the graph into two (or more) pieces. Finding small graph separators is a fundamental combinatorial problem with numerous applications. Interest in it also derives from its theoretical...

We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: 1. Each comparison can be erroneous with some probability 1 - p. 2. At each stage k comparisons can be performed in parallel and a noisy answer...

Hardness amplification is a major line of research that mainly seeks to transform a given lower bound (e.g. a function that has correlation at most 99% with small circuits) into a strongly average-case one (i.e. a function that has negligible...

Avoider-Enforcer games are a misere version of somewhat more popular Maker-Breaker games. An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph H=(V,E) (typically the vertices of H are the edges of the...

A given function f(x) is "hard on average" with respect to an algorithm A , if A(x) disagrees with f(x) on "many" inputs x. Applications in cryptography and derandomization require functions that are "very hard on average" (essentially unpredictable...

We prove strong lower bounds for Sherali-Adams relaxations of the MAX CUT, Vertex Cover and Sparsest Cut problems. Specifically, we show that the integrality gap of MAX CUT and Vertex Cover relaxations is 2-$\epsilon$ after n^delta rounds (where...

In this work we re-visit the question of building cryptographic primitives that remain secure even when queried on inputs that depend on the secret key. This was investigated by Black, Rogaway, and Shrimpton in the context of randomized encryption...

The disjointness function---determining if a number of sets share a common element---is a notorious example in communication complexity of a function which is hard, but it is hard to show it is hard. Determining both the randomized and quantum...

A Freiman isomorphism is a fundamental object in additive combinatorics that allows one to move an additive problem from one group to another, all while preserving the salient additive properties. In this talk, we will discuss a new mapping result...

We introduce the notion of a Canonical Tester for a class of properties on distributions, that is, a tester strong and general enough that ``a distribution property in the class is testable if and only if the Canonical Tester tests it''. We...

Learning theory, and in particular PAC learning, was introduced by Valiant in 1984 and has since become a major area of research in theoretical and applied computer science. One natural question that was posed at the very inception of the field is...

We prove that every key exchange protocol in the random oracle model in which the honest users make at most $n$ queries to the oracle can be broken by an adversary making $O(n^2)$ queries to the oracle. This improves on the previous $\Tilde{O}(n^6)$...

Let G be a finitely generated group equipped with the word metric. Assume that G does not admit a bi-Lipschitz embedding into Hilbert space. How can we quantify the extent to which G is non-Hilbertian? A natural approach is to consider the Hilbert...

In this work we re-visit the question of building cryptographic primitives that remain secure even when queried on inputs that depend on the secret key. This was investigated by Black, Rogaway, and Shrimpton in the context of randomized encryption...

Recently, algebraic codes which achieve the optimal trade-off between rate and (list) error-correction radius were constructed by a careful "folding" of the Reed-Solomon code. The "low-degree'' nature of this folding operation was crucial to the...

A Kakeya set in F^n , where F is a finite field, is a set containing a line in every direction. The finite field Kakeya conjecture states that the size of such sets is bounded from below by C_n*|F|^n , where C_n depends only on the dimension n . I...

In 1982 Linial and Berge conjectured that there is some form of duality between partitioning the vertices of a directed graph to disjoint paths and finding a big set of vertices in it with a small chromatic number. In the talk I will discuss the...