Seminars Sorted by Series

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

The sensitivity conjecture is a major outstanding foundational problems about boolean functions is the sensitivity conjecture. In one of its many forms, it asserts that the degree of a boolean function (i.e. the minimum degree of a real polynomial...

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by...

The Ramsey number of a graph $G$ is the minimum integer $n$ for which every edge-coloring of the complete graph on $n$ vertices with two colors contains a monochromatic copy of $G$. A graph is $d$-degenerate if all its subgraphs have a vertex of...

Vapnik's fundamental theorem of statistical learning establishes a computational equivalence between optimization (empirical risk minimization) and learning in the statistical setting. Is the same true for learning in games? We give a precise answer...

In [kal89], Kaltofen proved the remarkable fact that multivariate polynomial factorization can be done efficiently, in randomized polynomial time. Still, more than twenty years after Kaltofen's work, many questions remain unanswered regarding the...

Suppose you have access to iid samples from an unknown probability distribution $p = (p_1, \ldots, p_d)$ on $[d]$, and you want to learn or test something about it. For example, if one wants to estimate $p$ itself, then the empirical distribution...

In his 1947 paper that inaugurated the probabilistic method, Erdős proved the existence of $2 \log(n)$-Ramsey graphs on $n$ vertices. Matching Erdős' result with a constructive proof is a central problem in combinatorics that has gained a...

Many polynomial-time solvable (combinatorial) optimization problems can be reduced to the feasibility problem and the intersection problem. In this talk, I will present the first nearly cubic time algorithm for both problems using a new cutting...

Solving the following problem is crucial when compiling for a quantum computer: given a finite set $G$ of elements of $SU(2)$, target element $U$ from $SU(2)$ and real number $\epsilon$ find $g_1,\dotsc, g_N$ from $G$ such that $\| g_1 \dotsm g_N -...

Ramsey theory refers to a large body of deep results in mathematics whose underlying philosophy is captured succinctly by the statement that "Every very large system contains a large well-organized subsystem." Ramsey numbers capture how very large...

We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image...

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb...

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as...

Interactive proofs have had a dramatic impact on Complexity Theory and Cryptography. In particular, the celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity...

We show that the bipartite perfect matching problem is in $\textrm{quasi-}\textsf{NC}^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such...