## Expositions

Yuval Filmus,

Harper's isoperimetric inequality An exposition of Harper’s proof of his edge isoperimetric inequality for the hypercube, following his book *Global methods for combinatorial isoperimetric problems*.

The proof uses a generalization of shifting that Harper calls *compression*.

Compared to Harper’s original proof (also reproduced in the book), the compression proof includes only one simple calculation.

Yuval Filmus,

Reckhow's theorem We given an exposition of Reckhow’s theorem from his thesis, which extends Spira’s formula balancing to Frege proofs. This balancing theorem, which doesn’t appear explicitly in the thesis, is essential for showing that all Frege proofs are p-equivalent, one of the main results of the thesis.

An alternative exposition can be found in Krajíček’s monograph Bounded Arithmetic, Propositional Logic and Complexity Theory.

Yuval Filmus,

Smolensky's polynomial method We give an exposition of Smolensky’s fundamental paper on the polynomial method, a lower bound method in circuit complexity. Books usually contain a simpler argument which works only for parity, whereas Smolensky’s argument also works for majority (directly). Our exposition omits the step of approximating a constant depth circuit by a low-degree polynomial.

## TSS Lectures

Yuval Filmus,

Submodular maximization We survey several recent algorithmic results on submodular maximization:

We also briefly survey some lower bounds:

This talk was given at the Toronto Student Seminar on 31/1/2013.

Yuval Filmus,

Permanent is hard to compute even on a good day Cai, Pavan and Sivakumar showed that it is hard to compute the permanent even with an inversely polynomial success probability, assuming the *worst-case* hardness of computing the permanent. Their proof combines the LFKN protocol with Sudan’s list-decoding algorithm for Reed-Solomon codes. We given an exposition of their result, as well as several results leading to it.

This talk was given at the Toronto Student Seminar on 17/9/2012.

Yuval Filmus,

Matrix multiplication An exposition on algorithms for matrix multiplication, in two parts:

- Part 1:
- The arithmetic model.
- Bilinear normal form for matrix multiplication.
- Tensor notation and tensor rank.
- Border rank.
- Schönhage’s $\tau$ theorem (the asymptotic sum inequality).
- Coppersmith’s $\tilde{O}(n^2)$ algorithm for multiplying rectangular matrices.

- Part 2:
- The laser method.
- The Coppersmith–Winograd algorithms.
- Capacity: the fundamental combinatorial underpinning of the Coppersmith–Winograd method.

These talks were given in the Toronto Student Seminar on 2/2/2012 and 9/2/2012, though the second one has been significantly updated since.

The talks were given again in the IAS theory seminar, on 25/2/2014 and 4/3/2014. The second part has been significantly updated: the combinatorial construction has been simplified following Davie and Stothers, and the general presentation follows Le Gall’s recent paper.

Yuval Filmus,

Two proofs of the central limit theorem We provide two proofs of the central limit theorem (up to Lévy’s continuity theorem), one using cumulants and the other using moments. As a bonus, we also prove the asymptotic normality of the number of distinct prime factors of a ‘random’ integer. Our account follows the exposition in the book The semicircle law, free random variables and entropy.

This talk was given at the Toronto Student Seminar on 20/1/2010.

Yuval Filmus,

Modern integer factorization methods We survey several modern integer factorization methods, including Pollard’s $\rho$, Pollard’s $p-1$, Williams’ $p+1$, the elliptic curve method, Shanks’ continued fractions algorithm, the quadratic sieve (including MPQS and Dixon’s provable variant) and the number-field sieve (which is only sketched).

Originally given as a talk in the Toronto Student Seminar on 25/11/2009, this talk proved popular and I have given it several more times.

Yuval Filmus,

Seven trees in one Andreas Blass explained how the type-theoretic identity $T=1+T^2$ for binary trees leads to a “finitistic” identity $T^7=T$ (the solution to the former equation is a primitive sixth root of unity). More generally, he proved that two polynomials in *$T$* are “equal” (under his finitistic interpretation) if and only if they agree on a primitive sixth root of unity and in terms of cardinalities. We give an exposition of this result (using work by Fiore and Leinster), using a more intuitive definition of “strong” equality, as equality given by an algorithm which also works for infinite binary trees.

This talk was given at the Toronto Student Seminar on 16/9/2009.

## Short Notes

Yuval Filmus and Nathan Lindzey,

Murali's basis for the slice The slice consists of all vectors $(x_1,\ldots,x_n) \in \{0,1\}^n$ of Hamming weight $k$. We usually assume that $k \leq n/2$.

My paper constructs an explicit orthogonal basis for functions on the slice. The basis is canonical in a sense made clear by Murali K. Srinivasan, who had given an inductive construction for the same basis in his own paper.

In this short note, we first show how Murali’s inductive construction gives rise to the explicit formula appearing in my paper. Then, we briefly give yet another construction of the basis, using the Gram–Schmidt process.

Yuval Filmus,

Information complexity of AND We show that the information complexity of the AND function with respect to the distribution $\mu(0,0)=\mu(0,1)=\mu(1,0)=1/3$ is strictly positive for any worst-case error rate (strictly less than $1/2$).

Using this, a simple (but tricky) argument using the chain rule shows that the information complexity of set disjointness is $\Omega(n)$ for any worst-case error rate, which implies that the randomized communication complexity of set disjointness is $\Omega(n)$.

Yuval Filmus,

NPN equivalence classes of Boolean functions Two Boolean functions are NPN-equivalent if they can be reached from one another by permuting the inputs, negating some of the inputs, and possibly negating the output. The number of different equivalence classes for a given number of variables forms the sequence A000370, which starts 2, 4, 14, 222, 616126, for functions of 1 to 5 variables, respectively.

For $n$ up to 5, we have compiled a list of all NPN-equivalence classes of Boolean functions on $n$ variables. Each such function is given as a hexadecimal integer in which bit $i$ is the value at the $i$th input.

Yuval Filmus,

Antichains on the Boolean lattice of dimension 6 We provide a list of all inequivalent non-trival antichains on the Boolean lattice of dimension 6, excluding the empty antichain and the one containing the empty set. Alternatively, this is a list containing all inequivalent non-constant monotone Boolean functions on six inputs, given by their minterms.

Antichains depending of dimension $n$ are given in terms of the points $1,\ldots,n$. The number of antichains of given dimension (including the two trivial cases) forms the sequence A003182.

Yuval Filmus,

Triangle-intersecting families of graphs on eight vertices We given a Katona-like proof that a triangle-intersecting family of graphs contains at most 1/8 of the graphs. Unfortunately, our proof works only on up to eight vertices. We discuss several other methods which also cannot give a general proof.

Parts of this note are summarized in my thesis.

Yuval Filmus,

Regular languages closed under Kleene plus Vincenzo Ciancia asked on cstheory.stackexchange about the class of regular languages satisfying the following property: whenever a word $w$ belongs to the language, all of its positive powers $w^k$ also belong to the language. He termed these languages ‘circular languages’. Answering his question, we have shown the following:

- Every circular language can be written as the union of expressions $r^+$. We exhibit a language where this union cannot be disjoint.
- Given a DFA for a regular language, it is PSPACE-complete to decide whether the language is circular.

The normal form appears in a paper by Calbrix and Nivat, and the PSPACE-completeness result follows quite easily from a paper by Kozen, as I detail in my answer. My proofs appear below.

Yuval Filmus,

Range of symmetric matrices mod 2 We show that the range of a symmetric matrix over $\mathit{GF}(2)$ always contains its diagonal. We present both our algorithmic proof and a simple proof by Noga Alon. A simplification of our proof has been given by Soltys (Lemma 9).

Yuval Filmus,

On the sequence $n$ mod $x$ Avinoam Braverman considered the sequence $n \bmod x$, where $1 \leq x \leq \sqrt{n}$, took its local minima, and plotted the results. When $n$ is large, a curious pattern composed out of what seem to be triangles appears. We explain this phenomenon heuristically, given formulas for the envelope of the “triangles” (which turn out to be quadratic functions). We go on to describe the envelope of the plot when an arbitrary number of the local minima and local maxima operations are composed.

Yuval Filmus,

Permutations avoiding patterns of length 3 We provide a bijective proof for the well-known fact that the number of 123-avoiding permutations and the number of 132-avoiding permutations are both counted by Catalan numbers. Simion and Schmidt came up with a direct bijection between the two sets of permutations, and their proof is recommended over mine.

Yuval Filmus,

Examples of the GCD proof system If $(x,y)=1$ then $(x+y,xy)=1$. The first part shows how to prove this using standard arguments and using the characterization of GCD as the minimal positive value obtained as an integer combination of the operands. The second part generalizes the argument to a lemma involving $n$ variables.

Yuval Filmus,

Orthogonal matrices with optimal $L_2$ norm Question 8 in Chapter 2 of *The Probabilistic Method* asks us to show that for every $n\times n$ orthogonal matrix and $1\leq k\leq n$, there is a column such that the squared $L_2$ norm of its first $k$ entries is at least $k/n$, or at most $k/n$. It also asks for an example in which this is tight. We exhibit such an example which works simultaneously for all $k$.

Yuval Filmus,

Largest adjacent segments on the unit circle Suppose $n$ points are thrown on the circumference of a unit-circumference circle, partitioning the circumference into $n$ segments. What is the expected length of the $k$th smallest segment? There is a well-known formula for this expectation.

We consider the expected length of $k$th smallest two adjacent segments. We develop a method for computing them exactly, and compute the expectations for several small $n,k$. The results do not seem to fit into a nice pattern.

Yuval Filmus,

A positive proof of Dehn's theorem Dehn proved that if a rectangle can be tiled by rectangles whose sides are commensurable, then the tiled rectangle is also commensurable. His proof, as described in *Proofs from the book*, applies a homomorphism which results in possibly negative side lengths. We modify his proof so that all side lengths are positive.

The crucial ingredient is the following lemma: for each finite set of positive reals there is a basis (over the rationals) of positive reals such that every element in the set is a non-negative integral combination of base elements. We provide two proofs of this lemma, one due to us and one due to Avinoam Braverman.

Yuval Filmus,

Riddle concerning $\pm1$ vectors A big sheet of paper contains $2^n$ rows consisting of all possible vectors of length $n$ whose entries are $+1$ or $-1$. Someone changes some of the entries to zero. Show that there must be a non-empty subset of the rows summing to zero.

Probably much harder than you think it is!

## Classics

Alex Wilkie,

Wilkie's proof of the switching lemma Excerpt from *Modèles non-standard en arithmétique et théorie des ensembles*, Jean-Pierre Ressayre & Alec J. Wilkie.

Joseph-Louis Lagrange,

Lagrange's proof of Wilson's theorem Démonstration d’un Théorème nouveau concernant les Nombres premiers, *Nouveaux Mémoires de l’Académie royale des Science et Belles-Lettres de Berlin*, année 1771.