Seminars Sorted by Series

We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman [Bra13]. Previously, only a separation of communication complexity and internal...

We will start with presenting the basic notions of (co)homomology of simplical complexes (which requires only basic linear algebra over the field of order 2) and then we will indicate its relevance for several topics in computer science and...

Higher-order Fourier analysis is a powerful tool that can be used to analyse the densities of linear systems (such as arithmetic progressions) in subsets of Abelian groups. We are interested in the group $\mathbb{F}_p^n$, for fixed $p$ and large $n$...

Joint work with Oded Goldreich. We prove that random $n$-by-$n$ Toeplitz matrices over $GF(2)$ have rigidity $\Omega(n^3/(r^2 \log n))$ for rank $r > \sqrt{n}$, with high probability. This improves, for $r = o(n / \log n \log\log n)$, over the $...

Ramanujan graphs are optimal expander graphs, and their existence and construction have been the focus of much research during the last three decades. We prove that every bipartite Ramanujan graph has a $d$-covering which is also Ramanujan. This...

I will survey some characterization results on random walks which stick to a small region unusually long. In application we give a description of unitary matrices of large permanent.

Proof complexity studies the complexity of mathematical proofs, with the aim of exhibiting (true) statements whose proofs are always necessarily long. One well-known proof system is Hilbert's Nullstellensatz, which shows that if the family $F=\{f_1...

We will continue Monday's talk on constant-round interactive proofs, going into more details of the full construction and its proof. We will also briefly recap Monday's talk so that it will be beneficial to those who cannot attend on Monday.

The main object of study of this talk are matrices whose entries are linear forms in a set of formal variables (over some field). The main problem is determining if a given such matrix is invertible or singular (over the appropriate field of...

While this lecture is a continuation of the lecture from last Tuesday, I will make it self contained. The main object of study of this talk are matrices whose entries are linear forms in a set of formal variables (over some field). The main problem...

I want to sketch some algebraic and geometric tools to solve a variety of extremal problems surrounding Minkowski sums of polytopes and colorful simplicial depth.

The algorithm indicated in the title builds on Luks's classical framework and introduces new group theoretic and combinatorial tools. In the first talk we outline the algorithm and state the core group theoretic and algorithmic ingredients. Some of...

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large...

Proof systems pervade all areas of mathematics (often in disguise: e.g. Reidemeister moves is a sound and complete proof system for proving the equivalence of knots given by their diagrams). Proof complexity seeks to to understand the minimal...

The Resolution proof system is perhaps the simplest and most universally used in verification system and automated theorem proving. It was introduced by Davis and Putnam in 1960. The study of its efficiency, both in terms of proof length of natural...

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every $d \geq 2$, there is an explicit $n$-variable Boolean function $f$, computed by a...

We characterize all complex-valued (Lebesgue) integrable functions $f$ on $[0,1]^m$ such that $f$ vanishes when integrated over the product of $m$ measurable sets which partition $[0,1]$ and have prescribed Lebesgue measures $\\alpha_1,\\ldots,\...

Reed-Muller codes encode an $m$-variate polynomial of degree $r$ by evaluating it on all points in $\{0,1\}^m$. Its distance is $2^{m-r}$ and so it cannot correct more than that many errors/erasures in the worst case. For random errors one may hope...

The discrete Fourier transform is a widely used tool in the analysis of Boolean functions. One can view the Fourier transform of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ as a distribution over sets $S \subseteq [n]$. The Fourier-tail at level $k...

In 1975 Goppa suggested a general method for constructing error correcting codes based on algebraic geometry. In a long line of research such codes were constructed, constituting as a precious example of a construction that beats the probabilistic...

I will introduce two notions that generalize the idea of real rootedness to multivariate polynomials: real stability and hyperbolicity. I will then show two applications of these types of polynomials that will (hopefully) be of interest to the CS...

The sum-of-squares (SOS) method is a conceptually simple algorithmic technique for polynomial optimization that---quite surprisingly---captures and generalizes the best known efficient algorithms for a wide range of NP-hard optimization problems...

We prove that there exists a constant $\epsilon > 0$ such that, assuming the Exponential Time Hypothesis for PPAD, computing an $\epsilon$-approximate Nash equilibrium in a two-player ($n \times n$) game requires quasi-polynomial time, $n^{\log^{1-o...

In the matrix completion problem, we have a matrix $M$ where we are only given a small number of its entries and our goal is to fill in the rest of the entries. While this problem is impossible to solve for general matrices, it can be solved if $M$...

Seeded and seedless non-malleable extractors are non-trivial generalizations of the more commonly studied seeded and seedless extractors. The original motivation for constructing such non-malleable extractors are from applications to cryptography...

In this talk I will show how to derive the fastest coordinate descent method [1] and the fastest stochastic gradient descent method [2], both from the linear-coupling framework [3]. I will relate them to linear system solving, conjugate gradient...

In this talk I will review some of the classical (and fundamental) results in the theory of graph rigidity.

We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as $n^{\Omega(1)}$-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, we obtain sub-exponential size...

Let $P:\{0,1\}^k \to \{0,1\}$ be a $k$-ary predicate. A random instance of a constraint satisfaction problem (CSP(P)) where each of the $\Delta n$ constraints is $P$ applied to $k$ literals on $n$ variables chosen at random is unsatisfiable with...

This will be a bit of a "grab bag" talk where I discuss some results and open questions in combinatorial geometry which are either approachable by the polynomial method or which I hope are approachable by the polynomial method! I will talk about...

The sensitivity conjecture is a famous open problem in the theory of boolean functions. Let $f$ be a boolean function defined on the hypercube. The sensitivity of a node $x$ is the number of its neighbours in the hypercube, for which $f$ give the...

Sketching for distance estimation is the problem where we need to design a possibly randomized function $F$ from a metric space to short strings, such that for any points $x,y$ from the metric space, the "sketches" $F(x)$ and $F(y)$ are sufficient...

In recent years, there has been a surge of exciting research activity at the interface of optimization (in particular polynomial, semidefinite, and sum of squares optimization) and the theory of dynamical systems. In this talk, we focus on two...

We provide a duality framework for Bayesian Mechanism Design. Specifically, we show that the dual problem to revenue maximization is a search over virtual transformations. This approach yields a unified view of several recent breakthroughs in...

This talk will survey recent progress on program obfuscation from feasibility results to applications in cryptography and complexity theory. We will also describe a simple obfuscation construction based on cryptographic multi-linear maps and give a...

The celebrated Brascamp-Lieb (BL) inequalities are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory, with many used in computer science. I will survey the well...

Invariant theory deals with properties of symmetries - actions of groups on sets of objects.It has been slower to join its sibling mathematical theories in the computer science party, but we now see it more and more in studies of computational...

Indistinguishability obfuscation has turned out to be an outstanding notion with strong implications not only to cryptography, but also other areas such as complexity theory, and differential privacy. Nevertheless, our understanding of how to...

Recently, a certain "monotone" version of the constraint satisfaction problem has proved an extremely useful tool for attacking problems in circuit, communication, and proof complexity theory. In this talk we discuss this version of the constraint...

We will give a high-level overview of computable analysis---an area studying the computational properties of continuous objects such as functions and measures on $\mathbb R^d$. We will then discuss some applications to the computability and...

I will give an introduction to computational techniques in noncommutative probability for people (like myself) that are less interested in the details of the theory and more interested using results in the theory to help understand the behavior of...

I will discuss methods for deriving bounds on the roots of polynomials, and how one can use such bounds to assert the existence of combinatorial structures with certain spectral properties. This will include introducing the "method of interlacing...

Communication complexity studies the minimal amount of information two parties need to exchange to compute a joint function of their inputs. Results, especially lower bounds in this basic model found applications in many other areas of computer...

I will survey some elementary (to state!) problems on groups, matrices, and tensors, and discuss their motivations arising from several major problems in computational complexity theory. On each problem there was some exciting recent progress which...

Invariant theory studies the actions of groups on vector spaces and what polynomial functions remain invariant under these actions. An important object related to a group action is the null cone, which is the set of common zeroes of all homogeneous...

Joint work with Daniel Kane (UCSD) and Shachar Lovett (UCSD)We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.For example, for any constant $k$, we construct linear decision...

A cap set in $(F_q)^n$ is a set not containing a three term arithmetic progression. Last year, in a surprising breakthrough, Croot-Lev-Pach and a follow up paper of Ellenberg-Gijswijt showed that such sets have to be of size at most $c^n$ with $c q...