Seminars Sorted by Series

A folded symplectic form on a manifold is a closed 2-form with the mildest possible degeneracy along a hypersurface. A special class of folded symplectic manifolds are the origami manifolds. In the classical case, toric symplectic manifolds can...

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

For a finitely presented group, the Word Problem asks for an algorithm which declares whether or not words on the generators represent the identity. The Dehn function is the time-complexity of a direct attack on the Word Problem by applying the...

While this talk is a continuation of the one I gave on Tue Nov 25, it will be planned as an independent one. I will not assume knowledge from that talk, and will reintroduce that is needed. (That first lecture gave plenty of background material, and...

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. Our proofs also extend to the high value regime (value close to 1) and...

Expander graphs are sparse graphs with good connectivity properties and they have become ubiquitous in theoretical computer science. Dimension expanders are a linear-algebraic variant where we ask for a constant number of linear maps that expand...

Given a $k$-dimensional linear subspace, consider the problem of approximating it (with respect to the spectral norm) in terms of another subspace spanned by the indicators of a $k$-partition of the coordinates. This is known as the spectral...

The log-concavity conjecture predicts that the coefficients of the chromatic (characteristic) polynomial of a matroid form a log-concave sequence. The known proof for realizable matroids uses algebraic geometry in an essential way, and the...

We compare methods of computing inverses of matrices over division rings. The most direct way is via Cohn's theory of full matrices, which was improved by Malcolmson, Schofield, and Westreich. But it is simpler to work with finite dimensional...

We provide a simple proof of the Rota--Heron--Welsh conjecture for matroids realizable as c-arrangements in the sense of Goresky--MacPherson: we prove that the coefficients of the characteristic polynomial of the associated matroids form log-concave...

Expander walk sampling is an important tool for derandomization. For any bounded function, sampling inputs from a random walk on an expander graph yields a sample average which is quite close to the true mean, and moreover the deviations obtained...

We give an explicit example for a Boolean function $f : \{0,1\}^n \to \{0,1\}$, such that every Boolean formula of size at most $n^{2.999}$, with gates AND, OR and NOT, computes $f$ correctly on at most $1/2 + \epsilon$ fraction of the inputs, where...

Given a collection of constraints over a collection of variables consider the following generic constraint satisfaction algorithm: start with a random assignment of values to the variables; while violated constraints exist, select a random such...

A square matrix $V$ is called rigid if every matrix obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to...

Let $S$ and $T$ be two dense subsets of $G^n$, where $G$ is the special linear group $\mathrm{SL}(2,q)$ for a prime power $q$. If you sample uniformly a tuple $(s_1,\ldots,s_n)$ from $S$ and a tuple $(t_1,\ldots,t_n)$ from $T$ then their interleaved...

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

A knot is a closed curve embedded in the three-dimensional space, like a rope whose two ends are joined together. As usual in Topology, two knots are equivalent if one can be deformed into the other by continuous moves, where stretching and...

I will describe several old and new applications of topological and algebraic methods in the derivation of combinatorial results. In all of them the proofs provide no efficient solutions for the corresponding algorithmic problems. Finding such...

For a collection of events on a probability space with specified dependencies, the Lovasz Local Lemma ("LLL") gives a sufficient condition for the existence of a point avoiding all the events. Following Moser's discovery of an efficient algorithm...

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

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