Seminars Sorted by Series

Many algorithms can intuitively be classified into one of a few basic paradigms of algorithms, such as greedy algorithms, dynamic programming, LP rounding, local search, etc. It is natural to ask which problems can be solved using these paradigms...

Given a set of variables, and a set of local constraints over them (e.g. a 3CNF formula) define the "satisfiability-gap" of the system as the smallest fraction of unsatisfiable constraints. We will describe a new proof for the PCP theorem of [AS...

In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the...

I will talk about a family of graphs which originally arose in cryptography, in studying the difficulty of the discrete logarithm problem on elliptic curves. These graphs can be shown to be expanders, assuming the generalized Riemann hypothesis (GRH...

Szemeredi's regularity lemma asserts, roughly speaking, that any large dense graph can be approximated to any specified accuracy by a much simpler "finite complexity" object; it has had many applications in graph theory, combinatorial number theory...

We construct an extractor that can extract from a constant number of independent sources of length $n$, each of which have min-entropy $n^\gamma$ for an arbitrarily small constant $\gamma > 0$. Our constructions are different from recent extractor...

Earthmover metrics are popular similarity measures in computer vision, and they are also used in the design of approximation algorithms for classification problems. Motivated by the existing nearest neighbor search databases for L_1 metrics, it was...

I will discuss the following two results. I will assume no prior knowledge of quantum information or the PCP theorem. 1) The membership of $x$ in $SAT$ (for $x$ of length $n$) can be proved by a logarithmic-size quantum state $\Psi$, together with a...

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