Seminars Sorted by Series

We propose an “analytical” framework for studying parallel repetitions of one-round two-prover games. We define a new relaxation of the value of a game, val+, and prove that it is both multiplicative and a good approximation for the true value of...

We study some problems relating to polynomials evaluated either at random Gaussian or random Bernoulli inputs. We present some new work on a structure theorem for degree-d polynomials with Gaussian inputs. In particular, if p is a given degree-d...

We present practically efficient methods for proving correctness of announced results of a computation while keeping input and intermediate values information theoretically secret. These methods are applied to solve the long standing problem of...

In many distributed systems, the cost of computation is dominated by the cost of communication between the machines participating in the computation. Communication complexity is therefore a very useful tool in understanding distributed computation...

In this talk I will describe nondeterministic reductions which yield new direct product theorems (DPTs) for Boolean circuits. In our theorems one assumes that a function F is "mildly hard" against *nondeterministic* circuits of some size s(n) , and...

Finding cliques in random graphs and the closely related "planted" clique variant, where a clique of size k is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known...

The Depth First Search (DFS) algorithm is one of the most standard graph exploration algorithms, used normally to find the connected components of an input graph. Though perhaps less popular than its sister algorithm, Breadth First Search (BFS), the...

Deep learning, a modern version of neural nets, is increasingly seen as a promising way to implement AI tasks such as speech recognition and image recognition. Most current algorithms are heuristic and have no provable guarantees. This talk will...

For a permutation \(p\), let \(S_n(p)\) be the number of permutations on \(n\) letters avoiding \(p\). Stanley and Wilf conjectured that, for each permutation \(p\), \(S_n(p)^{1/n}\) tends to a finite limit \(L(p)\). Marcus and Tardos proved the...

The goal of (general-purpose) program obfuscation is to make an arbitrary computer program "unintelligible" while preserving its functionality. The problem of program obfuscation is well studied both in theory and in practice. Though despite its...

Let \(K\) and \(T\) be convex bodies in the \(n\)-dimensional Euclidean space. The covering number of \(K\) by \(T\) is the minimal number of translates of \(T\) required to cover \(K\) entirely. One open question regarding this classical notion is...

Given data stream \(D = \{p_1,p_2,...,p_m\}\) of size \(m\) of numbers from \(\{1,..., n\}\), the frequency of \(i\) is defined as \(f_i = |\{j: p_j = i\}|\). The \(k\)-th frequency moment of \(D\) is defined as \(F_k = \sum_{i=1}^n f_i^k\). We...

We use critical block sensitivity, a new complexity measure introduced by Huynh and Nordstrom (STOC 2012) to study the communication complexity of search problems. Our main result is a simple proof that if \(S\) is a search problem with high...

Machine learning is often employed as one step in a larger application, serving to perform information extraction or data mining for example. The rules obtained by such learning are then used as inputs to a further analysis. As a consequence of the...

Algebraic geometry and representation theory have played an important role in obtaining lower bounds in algebraic complexity theory. After giving an overview of the general set-up, I will present very recent results that indicate a possible role for...

We will outline the proof that gives a positive solution of to Weaver's conjecture \(KS_2\). That is, we will show that any isotropic collection of vectors whose outer products sum to twice the identity can be partitioned into two parts such that...

Most of the cryptosystems we currently use are highly secure, and cannot be broken with reasonable complexity by mathematical cryptanalysis. However, over the last fifteen years researchers have developed many types of physical attacks on their...

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even \(n\), there exists an explicit bijection \(f\) from the \(n\)-dimensional Boolean cube to the Hamming ball of...

In this talk, I'll describe connections between the unique games conjecture (or more precisely, the closely relatedly problem of small-set expansion) and the quantum separability problem. Remarkably, not only are the problems related, but the...

An error-correcting code is called locally decodable if there exists a decoding algorithm that can recover any symbol of the message with high probability by reading only a small number of symbols of the corrupted codeword. There is a fundamental...

One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also known as the Excluded Grid Theorem). The theorem states that any graph of treewidth at least \(k\) contains a grid minor of size \(f(k)\)...

The Geometric Complexity Theory (GCT) Program is an approach towards P versus NP and other lower bounds using algebraic geometry and representation theory. In this talk, we discuss how essentially all known algebraic circuit lower bounds and...

In this talk, I will describe a new framework for approximately solving flow problems in capacitated, undirected graphs, and I will apply it to find approximately maximum s-t flows in almost-linear time, improving on the best previous bound of \(...

The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. In this talk, I will explain the ideas of the proof and discuss our recent simplifications. One of the main ingredients in the proof is a...

In this talk we will present two structural results concerning low degree polynomials over \(GF(2)\). The first states that for any degree d polynomial \(f\) in \(n\) variables over \(GF(2)\), there exists a subspace of \(GF(2)^n\) with dimension \(...

A popular method in combinatorial optimization is to express polytopes \(P\), which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial...

We consider the problem of the list-decodability of error correcting codes. The well-known Johnson bound implies that any code with good distance has good list-decodability, but we do not know many structural conditions on a code which guarantee...

We prove a \(\tilde{\Omega}(n^{1/5})\) lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown n-variable Boolean function is monotone versus constant-far from monotone. This gives an...

There has been substantial progress on algorithmic versions and generalizations of the Lovasz Local Lemma recently, with some of the main ideas getting simplified as well. I will survey some of the main ideas of Moser & Tardos, Pegden, and David...

An error-correcting code is called locally decodable if there exists a decoding algorithm that can recover any symbol of the message with high probability by reading only a small number of symbols of the corrupted codeword. There is a fundamental...

How can we produce randomness of almost perfect quality, in large quantities, and under minimal assumptions? This question is fundamental not only to modern day information processing but also to physics. Yet a satisfactory answer is still elusive...

A planar set that contains a unit segment in every direction is called a Kakeya set. These sets have been studied intensively in geometric measure theory and harmonic analysis since the work of Besicovich (1919); we find a new connection to game...

The chromatic number \(k(G)\) of a graph \(G\) is always at least the size of its largest clique (denoted by \(w(G)\)), and there are graphs with \(w(G)=2\) and \(k(G)\) arbitrarily large. On the other hand, the perfect graph theorem asserts that if...

Two important breakthroughs on the permanent had been accomplished in 1998: A. Schrijver proved Schrijver-Valiant Conjecture on the minimal exponential growth of the number of perfect matchings in k-regular bipartite graphs with multiple edges; N...

In distributed systems, communication between the participants in the computation is usually the most expensive part of the computation. Theoretical models of distributed systems usually reflect this by neglecting the cost of local computation, and...

Computing the volume of a convex body in n-dimensional space is an ancient, basic and difficult problem (#P-hard for explicit polytopes and exponential lower bounds for deterministic algorithms in the oracle model). We present a new algorithm, whose...

Geometric questions for discrete objects (e.g. isoperimetry, integrality gaps, embeddings) are often easier to understand by first considering an appropriate continuous analogue, using additional structure that is available in the continuous setting...

We introduce a new method of obtaining sharp estimates on mixing for Glauber dynamics for the Ising model, which, in particular, establishes cutoff in three dimensions up to criticality. The new framework, which considers ``information percolation''...

Consider an image with two colors--black and white--and where only 1% of the pixels are white. If we apply a Gaussian blur, can it be that the non-black pixels of the (now greyscale) image are largely concentrated on a single shade of grey? Sure, if...

The computational worldview is relevant to multiple fields of investigation beyond computer science, including evolutionary theory. Evolution is a creative process that generates organisms as well as behavioral programs, which can be thought of as...

I will present an exciting new interaction between computer science and fair division theory, with the goal of giving the audience a taste of different fair division challenges and the role computational thinking plays in addressing them. Among...

The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games -- "fortification" -- and...

One of the great challenges posed by the laws of quantum mechanics is that the number of parameters required to describe a quantum state in general grows exponentially in the number of particles. This complexity is directly related to the phenomenon...

One of the great challenges posed by the laws of quantum mechanics is that the number of parameters required to describe a quantum state in general grows exponentially in the number of particles. This complexity is directly related to the phenomenon...

We construct publicly verifiable non-interactive arguments that can be used to delegate polynomial time computations. These computationally sound proof systems are completely non-interactive in the common reference string model. The verifier’s...

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function $f:\{0,1\}^n...

We introduce an abstract model of computation corresponding to an experiment in which identical, non-interacting bosons are sent through a non-adaptive linear circuit before being measured. We show that despite the very limited nature of the model...

We introduce an abstract model of computation corresponding to an experiment in which identical, non-interacting bosons are sent through a non-adaptive linear circuit before being measured. We show that despite the very limited nature of the model...