Seminars Sorted by Series

Unique games were introduced by Uriel Feige and Laszlo Lovasz. We are given a graph G, a set of labels [k] = {1,...,k}, and permutations pi_{uv} on the set [k] (for all edges (u,v)). Our goal is to find an assignment of labels to variables x(u) (for...

A code is said to be locally testable if an algorithm can distinguish between a codeword and a vector being essentially far from the code using a number of queries that is independent of the code's length. The question of characterizing codes that...

We prove a general result bridging the fields of Secure Protocols and Game Theory. We show that ANY mediated game with incomplete information can be perfectly simulated by the players alone, essentially by means of an extensive-form game in which...

Biological networks have so many possible states that exhaustive sampling is impossible. Successful analysis thus depends on simplifying hypotheses, but experiments on many systems hint that complicated, higher order interactions among large groups...

Ramanujan complexes of type ${\tilde A}_n$ have been constructed by Lubotzky, Samuels and Vishne. In this talk I would like to propose a definition of Ramanujan complexes associated with buildings of any affine type. This involves defining...

Internal conflict is considered to be a fundamental psychological phenomenon, and many behaviors in both humans and animals have been attributed to it. However, from a biological standpoint, internal conflict is counterintuitive, in that it appears...

Perhaps the most appealing conjectures in asymptotic convex geometry are (i) slicing (or isotropic constant) and (ii) variance. Together, they imply that for a random point X from an isotropic convex body in \R^n, the variance of |X|^2 is O(n). We...

We present a novel tree representation for the hard-core lattice gas model (weighted independent sets) on a general graph. We use this representation to show that for any graph of maximum degree D, the Gibbs measure is unique (the influence of any...

Counting connected components and Betti numbers was a known technique in algebraic complexity theory in the late 1970's and early 1980's. Speculation arose as to whether such methods could attack lower bounds in Boolean complexity theory (e.g., P vs...

In this talk I will prove the following counterpoint to a result by Kashin and Szarek (cf. Theorem 1, C. R. Acad. Sci. Paris, Ser. I, 1336 (2003) 931-936)): There exists a map \phi from infinite-dimensional euclidean space into the space of...

A Hamilton cycle in a graph G is a cycle passing through all vertices of G. Hamiltonicity is one of the most central and appealing notions in Graph Theory, with a variety of known conditions and approaches to show the existence of a Hamilton cycle...

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