Seminars Sorted by Series

Algorithms spend time on performing arithmetic computations, but often more on moving data, between the levels of a memory hierarchy and between parallel computing entities. Judging by the hardware evolution of the last few decades, the fraction of...

I will be describing recent joint efforts with Tim Gowers to decompose a bounded function into a sum of polynomially structured phases and a uniform error, based on the recent inverse theorem for the U^k norms on F_p^n by Bergelson, Tao and Ziegler...

The Unique Games Conjecture (Khot, 2002) is a central open question about hardness of approximation. In recent years, a sequence of works showed that the truth of this conjecture would have profound implications: If the conjecture is true, then...

How many edges of the n-dimensional Boolean hypercube can be sliced by a degree-d polynomial surface? This question can be equivalently stated as "What is the maximum average sensitivity of any degree-d polynomial threshold function?" In 1994...

In this talk, I shall describe an ongoing project to develop a complexity theory for cryptographic (multi-party computations. Different kinds of cryptographic computations involve different constraints on how information is accessed. Our goal is to...

For four years now, we have been conducting "medium-scale" experiments in how human subjects behave in strategic and economic settings mediated by an underlying network structure. We have explored a wide range of networks inspired by generative...

In this survey I will present several extremal problems, and some solutions, concerning convex lattice polytopes. A typical example is to determine the smallest area that a convex lattice polygon can have if it has exactly n vertices.

Semidefinite programming bounds are widely used in combinatorial optimization, quantum computing and complexity theory. The first semidefinite programming bound to gain fame is the so-called theta number developed by Lov\'asz to compute the Shannon...

In this talk we will present a near-optimal compression scheme for bounded-round randomized 2-party communication protocols. Previously, such a scheme was only known for protocols where the inputs to the parties are independent. The results yield a...

The cover time of a graph is one of the most basic and well-studied properties of the simple random walk, and yet a number of fundamental questions concerning cover times have remained open. We show that there is a deep connection between cover...

*It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard for their own interest. Each participant in a competitive economy is led by an invisible hand to promote an end which was no...

We consider the following two questions: 1) Is the MAX-CUT problem hard on random geometric graphs of the type considered by Feige and Schechtman (2002)? 2) Is the value of a mathematical relaxation such as semi- definite programming (SDP) for a...

A beautiful conjecture of Erd\H{o}s-Simonovits and Sidorenko states that if $H$ is a bipartite graph, then the random graph with edge density $p$ has in expectation asymptotically the minimum number of copies of $H$ over all graphs of the same order...

The condition number of a matrix is at the heart of numerical linear algebra. In the 1940s von-Neumann and Goldstine, motivated by the problem of inverting, posed the following question: (1) What is the condition number of a random matrix ? During...

I will describe the proof of the following surprising result: the typical billiard paths form the family of the most uniformly distributed curves in the unit square. I will justify this vague claim with a precise statement. As a byproduct, we obtain...

I will talk about the computational complexity of computing the noncommutative determinant. In contrast to the case of commutative algebras, we know of (virtually) no efficient algorithms to compute the determinant over non-commutative domains. Our...

In a sequence of recent papers, Sudan and coauthors have investigated the relation between testability of properties of Boolean functions and the invariance of the properties with respect to transformations of the domain. Linear-invariance is...

In our work we study the structure of polynomials of degree three and four that have high bias or high Gowers norm, over arbitrary prime fields. In particular we obtain the following results. 1. We give a canonical representation for degree three or...

Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(n^h) copies of H can be made H-free by removing o(n^2) edges. We give a new proof which avoids Szemeredi's regularity lemma and gives a...

A perfect matching in a $k$-uniform hypergraph $H= (V, E)$ on $n$ vertices is a set of $n/k$ disjoint edges of $H$, while a fractional perfect matching in $H$ is a function $w:E \to [0,1]$ such that for each $v \in V$ we have $\sum_{e \ni v}w(e) = 1...

The famous theorem of Szemerédi says that for any natural number k and any a > 0 there exists n such that if N >= n then any subset A of the set [N] ={1,2,...,N} of size |A| >= a N contains an arithmetic progression of length k. We consider the...

In recent joint work with Alex Arkhipov, we proposed a quantum optics experiment, which would sample from a probability distribution that we believe cannot be sampled (even approximately) by any efficient classical algorithm, unless the polynomial...

The classical Dvoretzky theorem asserts that for every integer k>1 and every target distortion D>1 there exists an integer n=n(k,D) such that any n-dimensional normed space contains a subspace of dimension k that embeds into Hilbert space with...

A ``tournament'' is a digraph obtained from a complete graph by directing its edges, and ``colouring'' a tournament means partitioning its vertex set into acyclic subsets (``acyclic'' means the subdigraph induced on the subset has no directed cycles...

A popular practical method of obtaining a good estimate of the error rate of a learning algorithm is k-fold cross-validation. Here, the set of examples is first partitioned into k equal-sized folds. Each fold acts as a test set for evaluating the...

This paper revisits the construction of Universally One-Way Hash Functions (UOWHFs) from any one-way function due to Rompel (STOC 1990). We give a simpler construction of UOWHFs which also obtains better efficiency and security. The construction...

The Johnson-Lindenstrauss lemma states that for any n points in Euclidean space and error parameter 0

The Johnson-Lindenstrauss lemma (also known as Random Projections) states that any set of n points in Euclidian space can be embedded almost isometrically into another Euclidian space of dimension O(log(n)). The talk will focus on the efficiency of...

Recently there has been much interest in polynomial threshold functions in the context of learning theory, structural results and pseudorandomness. A crucial ingredient in these works is the understanding of the distribution of low-degree...

The INDEX problem is one of a handful of fundamental problems in communication complexity: Alice has an n-bit string x, Bob has an index k in [n], and the players wish to determine the k-th bit of x. It is easy to show that the problem is "hard"...

We prove completeness results for certain class of functions which have implications for automatic proving of universally-composable security theorems for ideal and real functionalities composed of if-then-else programs with (uniform) random number...

Property testing considers the following general question: how many queries to some combinatorial object (e.g., a boolean function or a graph) do we need to determine whether the object has some property P or whether it is "far" from having the...

We show a (3/2-\epsilon)-approximation algorithm for the graphical traveling salesman problem where the goal is to find a shortest tour in an unweighted graph G. This is a special case of the metric traveling salesman problem when the underlying...

It is well-known that any Boolean function f:{-1,+1}^n \to {-1,+1} can be written uniquely as a polynomial f(x) = \sum_{S subset [n]} f_s \prod_{i in S} x_i. The collection of coefficients (f_S's) this expression are referred to (with good reason)...

Consider an optimization problem with n binary variables and d+1 linear objective functions. Each valid solution x in {0,1}^n gives rise to an objective vector in R^{d+1}, and one often wants to enumerate the Pareto optima among these. In the worst...

We prove a complexity dichotomy theorem for all non-negatively weighted counting Constraint Satisfaction Problems (#CSP). This caps a long series of important results on counting problems including unweighted and weighted graph homomorphisms and the...

Recursive Majority-of-three (3-Maj) is a deceptively simple problem in the study of randomized decision tree complexity. The precise complexity of this problem is unknown, while that of the similarly defined Recursive NAND tree is completely...

A "sparsifier" of a graph is a weighted subgraph for which every cut has approximately the same value as the original graph, up to a factor of (1 +/- eps). Sparsifiers were first studied by Benczur and Karger (1996). They have wide-ranging...

In a joint work with Tsuyoshi Ito we have constructed a fingerprinting scheme (i.e., hashing) that leaks significantly less than log(1/epsilon) bits about the preimage, where epsilon is the error ("collision") probability. It is easy to see that...

A k-modal probability distribution over the domain {1,...,N} is one whose histogram has at most k "peaks" and "valleys". Such distributions are a natural generalization of the well-studied class of monotone increasing (or monotone decreasing)...

More than twenty years ago, Manickam, Miklos, and Singhi conjectured that for any integers $n \geq 4k$, every set of $n$ real numbers with nonnegative sum has at least $\binom{n-1}{k-1}$ $k$-element subsets whose sum is also nonnegative.

In this...

In settings of incomplete information, we put forward (1) a very conservative ---indeed, purely set-theoretic--- model of the beliefs (including totally wrong ones) that each player may have about the payoff types of his opponents, and (2) a new and...

Proving superpolylogarithmic lower bounds for dynamic data structures has remained an open problem despite years of research. Recently, Patrascu proposed an exciting new approach for breaking this barrier via a two player communication model in...

A pseudo-random graph is a graph G resembling a typical random graph of the same edge density. Pseudo-random graphs are expected naturally to share many properties of their random counterparts. In particular, many of their enumerative properties...