Seminars Sorted by Series

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

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the $i$'th bit of an $n$-bit database replicated among two servers (which do not communicate) while not revealing any information about $i$ to either server. The privacy...

We prove an $\omega(\log n)$ lower bound on the conondeterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies superpolynomial lower bounds for the...

Given a $k$-edge-connected graph $G = (V,E)$, a spanning tree $T$ is $\alpha$-thin w.r.t. $G$, if for any $S \subset V$, $|T(S,V - S)| \leq \alpha.|E(S,V - S)|$. The thin tree conjecture asserts that for a sufficiently large $k$ (independent of size...

Various motivations recently led Mendel and Naor, Hatami and Kalai to study functions in tail spaces - i.e. function all of whose low level Fourier coefficients vanish. I will discuss the questions and conjectures that they posed and our recent work...

We prove that for any $\epsilon > 0$ it is NP-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \epsilon$, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof...

At the heart of every local search algorithm is a directed graph on candidate solutions (states) such that every unsatisfactory state has at least one outgoing arc. In stochastic local search the hope is that a random walk will reach a satisfactory...

During last fifty years a strong machine learning theory has been developed. This theory includes: 1. The necessary and sufficient conditions for consistency of learning processes. 2. The bounds on the rate of convergence which in general cannot be...

In the last few years, there has been a significant interest in the computational abilities of Physarum Polycephalum (a slime mold). This drew from a remarkable experiment which showed that this organism can compute shortest paths in a maze...