Seminars Sorted by Series

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e.,\(P \not\subseteq NC_1\) ). This problem is interesting both because it is tightly related to understanding the...

We will discuss interactive coding in the setting where there are n parties attempting to compute a joint function of their inputs using error-prone pairwise communication channels. We will present a general protocol that allows one to achieve only...

Expanders are highly connected sparse graphs. Simplicial complexes are a natural generalization of graphs to higher dimension, and the notions of connectedness and expansion turn out to have interesting analogues, which relate to the homology and...

We will discuss space and parallel complexity, ranging from some classical results which motivated the study, to some recent results concerning combinatorial lower bounds in restricted settings. We will highlight some of their connections to boolean...

Expanders are highly connected sparse graphs. Simplicial complexes are a natural generalization of graphs to higher dimension, and the notions of connectedness and expansion turn out to have interesting analogues, which relate to the homology and...

Expanders are highly connected sparse graphs. Simplicial complexes are a natural generalization of graphs to higher dimension, and the notions of connectedness and expansion turn out to have interesting analogues, which relate to the homology and...

I will survey what is known about the complexity of arithmetic circuits computing polynomials and rational functions with non-commuting variables, focusing on recent results and open problems. Strangely enough, some elementary questions in...

I will continue last week's discussion of this model, this time giving sketches of proofs of some of the theorems. No technical background is necessary for this lecture, but for motivation and background it is good to consult the Tue Feb 11 talk...

How many arithmetic operations does it take to multiply two square matrices? This question has captured the imagination of computer scientists ever since Strassen showed in 1969 that \(O(n^{2.81})\) operations suffice. We survey the classical theory...

How many arithmetic operations does it take to multiply two square matrices? This question has captured the imagination of computer scientists ever since Strassen showed in 1969 that \(O(n^{2.81})\) operations suffice. We survey the classical theory...

The Martians built an amazingly fast computer and they run it to answer the great question of life, the universe and everything. They claim that the answer is 42. Will they be able to convince us that this is the right answer, assuming that we do...

In joint work with Ballard, Demmel, and Schwartz, we showed the communication cost of algorithms (also known as I/O-complexity) to be closely related to the small-set expansion properties of the corresponding computation graphs. This graph expansion...

The goal of computationally sound symbolic security is to create formal systems of cryptography which have a sound interpretation with respect to complexity-based notions of security. While there has been much progress in the development of such...

Byzantine agreement is a fundamental problem of distributed computing which involves coordination of players when a constant fraction are controlled by a malicious adversary. Each player starts with a bit, and the goal is for all good players to...

The P != NP conjecture doesn't tell us what runtime is needed to solve NP-hard problems like 3-SAT and Hamiltonian Path. While some clever algorithms are known, they all require exponential time, and some researchers suspect that this is unavoidable...

The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a...

I will survey recent results and open problems in several areas of quantum complexity theory, with emphasis on open problems which can be phrased in terms of classical complexity theory or mathematics but have implications for quantum computing: 1...

In the last few years, there has been a lot of activity in the area of structural analysis and derandomization of polynomial threshold functions. Tools from analysis and probability have played a significant role in many of these works. The focus of...

In this talk, we will continue, the proof of the Central Limit theorem from my last talk. We will show that that the law of "eigenregular" Gaussian polynomials is close to a Gaussian. The proof will be based on Stein's method and will be dependent...

Let \(G\) be a finite group, and let \(a\), \(b\), \(c\),... be independent random elements of \(G\), chosen at uniform distribution. What is the distribution of the element obtained by a fixed word in the letters \(a\), \(b\), \(c\),..., such as \...

Let \(G\) be a finite group, and let \(a\), \(b\), \(c\),... be independent random elements of \(G\), chosen at uniform distribution. What is the distribution of the element obtained by a fixed word in the letters \(a\), \(b\), \(c\),..., such as \...

Monotone submodular maximization over a matroid (MSMM) is a fundamental optimization problem generalizing Maximum Coverage and MAX-SAT. Maximum Coverage is NP-hard to approximate better than \(1-1/e\), an approximation ratio obtained by the greedy...

The polynomial Bogolyubov-Ruzsa conjecture which aims to quantify the amount of additive structure in dense subsets of abelian groups is one of the central conjectures in additive combinatorics which has recently been shown to have various...

In profoundly influential works, Shannon and Huffman show that if Alice wants to send a message \(X\) to Bob, it's sufficient for her to send roughly \(H(X)\) bits (in expectation), where \(H\) denotes Shannon's entropy function. In other words, the...

The signrank of an \(N \times N\) matrix \(A\) of signs is the minimum possible rank of a real matrix \(B\) in which every entry has the same sign as the corresponding entry of \(A\). The VC-dimension of \(A\) is the maximum cardinality of a set of...

In its simplest form, the central limit theorem states that a sum of n independent random variables can be approximated with error \(O(n^{-1/2})\) by a Gaussian with matching mean and second moment (given these variables are not too dissimilar). We...

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