Seminars Sorted by Series

A number of recent results on optimization problems involving submodular functions have made use of the "multilinear relaxation" of the problem. I will show a general approach to deriving inapproximability results in the value oracle model, based on...

This work attempts to broaden the foundations of public-key cryptography. We construct a new public key encryption based on two “hardness on average” assumptions: (1) it is hard to “learn parity with noise” for random sparse equations; and (2) it is...

A halfspace (a.k.a. threshold) is a boolean function h : {-1,1}^n --> {-1,1} of the form h(x) = sign(w_0 + w_1 x_1 + ... + w_n x_n), where the weights w_i are arbitrary real numbers. Halfspaces are studied extensively in the theories of complexity...

I will discuss a lower bound of $\omega(n^(k/4))$ on the size of constant-depth $(AC_0)$ circuits solving the k-clique problem on n-vertex graphs. This bound follows from a stronger result that $AC_0$ circuits of size $O(n^(k/4))$ almost surely fail...

Via four applications: distribution modeling, probability estimation, data compression, and classification, we argue that when learning from data, discrete values should be ignored except for just their appearance-order pattern. Along the way, we...

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula F is a propositional formula in which each variable appears exactly once. Such a formula...

I will present a construction of an n-point negative type metric such that every t-point sub-metric is isometrically L1-embeddable, but embedding the whole metric into L1 incurs distortion at least k, where both t and k are (\log\log\log n)^{\Omega...

On Feb. 1, in his blog, Tim Gowers proposed an open collaboration on a math problem. Specifically, he suggested working on a combinatorial proof of the Density Hales-Jewett Theorem. This theorem states that for every delta > 0, if n is sufficiently...

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We...

Ideally, one would want to base the security of standard cryptographic primitives (such as pseudorandom generators) on widely believed worst-case complexity assumptions like P does not equal NP. However, it is currently not known if this is possible...

I will talk about a recent work describing a deterministic polynomial time algorithm for blackbox identity testing for depth three circuits with bounded top fanin over the field of rational numbers. This resolves a question posed by Klivans and...

Constraint Satisfaction Problems appear everywhere. The study of their quantum analogues (in which the constraints no longer commute), has become a lively area of study, and various recent results provide interesting insights into quantum physics...

A PCP is a proof system in which the proofs that can be verified by a verifier that reads only a very small part of the proof. One line of research concerning PCPs is trying to reduce their soundness error (i.e., the probability of accepting false...

An XOR game is a very simple model of evaluating a distributed function f(x,y) . With probability p(x,y) a Verifier sends questions x, y to Alice and Bob, respectively. Without communicating, Alice and Bob then output a, b in {-1,+1} in the hope...

Sex has been called "the queen of problems in evolutionary biology" since it is pervasive in nature yet its functional significance has not been known. It has often been assumed that the shuffling of genes due to sex is an adaptation that...

Research in the area of privacy of data analysis has been flourishing recently, with a rigorous notion such as differential privacy regarding the desired level of privacy and sanitizing algorithms matching the definition for many problems. Most of...

We give new results on the number-on-the-forhead (NOF) communication complexity of the multiparty pointer jumping problem. The origional motivation for this problem comes from circuit complexity. Specifically, there is no explicit function known to...

The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential...

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