Seminars Sorted by Series

One-way functions (i.e., polynomial-time computable functions that are hard to invert on the average case) are the cornerstone of modern cryptography. The hardness condition on the task of inverting a one-way function is an *average-case* complexity...

A RED/BLUE coloring of a graph is called $C$-relaxed if the RED vertices form an independent set, while the BLUE vertices induce connected components of order at most $C$. We show that there exists a smallest integer $C$ such that every cubic graph...

We give asymptotically precise estimates for the expected time taken for a random walk to visit all vertices of a graph, viz. the cover time. We do this for several models of random graphs viz. $G_{n,p}$ when $p$ is above the connectivity threshold...

We propose a new approach to designing a strongly polynomial algorithm for linear programming. We show that linear programming on any polytope can be reduced to linear programming on an arrangement polytope. The graphs of arrangement polytopes have...

In this talk, we will sketch the theory of simultaneous optimization for concave profit functions, and point out connections to fairness. More precisely, suppose we would like to simultaneously approximate all symmetric utility functions over a...

We'll begin with the following theorem, which proves a conjecture of S\'ark\"ozy, Selkow and Szemer\'edi, and try to use it as an excuse to talk about other things (perhaps including Br\'egman's Theorem, entropy, the ``incremental random method,"...

Let $F$ be a family of graphs. A graph $H$ is *$F$-universal* if every $G\in F$ is isomorphic to a subgraph of $H$. Besides being of theoretical interest, universal graphs have applications in chip design and network simulation. For any two positive...

We show new connections between derandomization, worst-case hardness and average-case hardness. Specifically, we show that a mild derandomization assumption together with the worst-case hardness of NP implies the average-case hardness of a language...

Consider the minimum cost spanning tree problem under the restriction that all degrees must be at most a given value $k$. The main result I will present is that one can efficiently find a spanning tree of maximum degree at most $k+2$ whose cost is...

We uncover the structure of those languages that have bounded (by a constant) k-party communication complexity in the input on the forehead model, no matter how we partition the input bits into k disjoint sets. This generalizes an earlier result of...

It is now well-known that a random walk on an expander graph is a very good "sampler", and this has been used to prove a variety of important results in complexity theory, cryptography and algorithms. On the surface, however, taking a walk on an...

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 by N Boolean matrices for which no K by K submatrix is...

We propose and discuss two conjectures on the nature of errors in highly correlated noisy physical stochastic systems. The first asserts that errors for a pair of substantially correlated elements are themselves substantially correlated. The second...

Decomposition and modularity are fundamental issues in many fields, including mathematics, biology, engineering, and management. How can large systems be broken into subsystems which interact enough to meet the overall system goals, but not so much...

A q-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 q bits of the codeword C(x), even after some constant fraction of...

Achieving correlated equilibrium is a problem at the intersection of game theory, cryptography and efficient algorithms. Thus far, however, perfectly rational solutions have been lacking, and the problem has been formulated with somewhat limited...

In combinatorial allocation, m items are to be assigned to n players so that their total utility is maximized. This problem has many variants depending on the utility functions involved and possible additional constraints. We consider two variants...

In 1950, Nash showed that every non-cooperative game has an equilibrium. Before his work, the result was known only for two-player zero-sum games. While von Neumann's minimax theorem was the mathematical foundation of the two-player zero-sum game...

Suppose you ran a chess tournament, everybody played everybody, and you wanted to use the results to rank everybody. Unless you were really lucky, the results would not be acyclic, so you could not just sort the players by who beat whom. A natural...

Let $M$ be an arbitrary $n$ by $n$ matrix. We study the condition number a random perturbation $M+N_n$ of $M$, where $N_n$ is a random matrix, motivated by a problem raised by Spielman and Teng. It is shown that, under very general conditions on $M$...

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