PublicationsManuscripts

We determine all $n$-ary Boolean functions $f_0,\ldots,f_m$ and $m$-ary Boolean functions $g_0,\ldots,g_n$ satisfying the equation
$f_0(g_1(z_{11},\ldots,z_{1m}),\ldots,g_n(z_{n1},\ldots,z_{nm})) =
g_0(f_1(z_{11},\ldots,z_{n1}),\ldots,f_m(z_{1m},\ldots,z_{nm}))$,
for all Boolean inputs ${ z_{ij} : i \in [n], j \in [m] }$. When the functions $f_0,\ldots,f_m,g_0,\ldots,g_n$ satisfy the above, we refer to them as a generalized polymorphism. This characterization generalizes a previously known characterization for polymorphisms, which are the special case of generalized polymorphisms formed by letting $g_1 = \dots = g_n$.

Our characterization not only captures the previously known characterization of polymorphisms, but also consolidates its case-wise characterization statement into a single consolidated expression. Indeed, this was made possible by viewing polymorphisms in the more general setting of generalized polymorphisms, which revealed a structure previously hidden due to degeneracies imposed by the assumption $g_1 = \dots = g_n$.

The characterization we obtain generalizes the previously known characterization of polymorphisms in two major aspects: first, we show that every generalized polymorphism is essentially composed of an evaluation of an arbitrary Boolean
function $h$ whose inputs are substituted with
$k$ polymorphisms, derived from $k$ disjoint
subsections of the input space. For polymorphisms, this partition degenerates into a singleton, and $h$ degenerates into simply returning the result of the polymorphism, up to sign. We show this aspect of our characterization in isolation, by restricting our inputs to include only functions of degree at least 2. The second aspect in which our characterization generalizes that of polymorphisms is the prevalence of arbitrary evaluations for certain subproblems involving degree 1 functions. For polymorphisms, this type of evaluation occurs in only two types of solutions. In contrast, in our characterization, it permeates throughout all solutions. We show this aspect after showing the first described above, by lifting the degree constraint imposed therein and generalizing the results achieved there using similar methods.

The complexity of Boolean functions on the Boolean cube can be measured in several ways, such as circuit complexity and decision tree complexity. Classical results show that many of these measures are polynomially related, such as decision tree complexity, certificate complexity, degree and sensitivity. Recently, the study of Boolean functions has been extended to functions on domains other than the Boolean cube, such as the slice, high-dimensional expanders and the Grassmann scheme. Can the study of different complexity measures can be generalized to some of these domains?

We begin with surveying recent work that generalizes the definitions of some of the classical complexity measures to domains other than the Boolean cube, including the symmetric group, which is our main focus. We then describe results regarding the relations between the different measures, generalizing the classical results and showing that polynomial relations exist between the considered measures for many other domains.

We then focus on functions with low sensitivity, with the goal of constructing efficient circuits for them. First, we generalize a result regarding the existence of small circuits for functions with low sensitivity on the Boolean cube, constructing a circuit of size $n^{O(s)}$, where $s$ is the sensitivity of $f$. Next, we generalize a result regarding the existence of low-depth circuits for functions with low sensitivity on the Boolean cube, and construct such circuits for functions over domains satisfying certain properties, including the symmetric group. Our construction results in an unbounded fan-in circuit of depth $O(s\log n)$ in the case of the symmetric group.

The last part of our work concerns intersecting families of permutations. A family of permutations is $t$-intersecting if any two permutations in the family agree on at least $t$ elements. It is known that for a large enough $n$, the maximal size of a $t$-intersecting family of permutations is $(n-t)!$, and a family of that size is a $t$-star, that is, the set of all permutations mapping some distinct $i_{1},\ldots,i_{t}$ to some distinct $j_{1},\ldots,j_{t}$ respectively. We generalize this result to the case of $t$-setwise-intersection, where any two permutations in the family agree on the image of a set of $t$ elements. We give an alternative proof to a known result stating that for a large enough $n$, the maximal size of a $t$-setwise-intersecting family of permutations is $t!(n-t)!$, and a family of that size is a $t$-setwise-star, that is, the set of all permutations mapping some set $S$ of size $t$ to some $T$ of size $t$. Our proof is much simpler than the known proof (which proves a stronger statement) and works for smaller values of $n$.

A basic combinatorial interpretation of Shannon’s entropy function is via the “20 questions” game. This cooperative game is played by two players, Alice and Bob: Alice picks a distribution $\pi$ over the numbers $\{1,\ldots,n\}$, and announces it to Bob. She then chooses a number $x$ according to $\pi$, and Bob attempts to identify $x$ using as few Yes/No queries as possible, on average.

An optimal strategy for the “20 questions” game is given by a Huffman code for $\pi$: Bob’s questions reveal the codeword for $x$ bit by bit. This strategy finds $x$ using fewer than $H(\pi)+1$ questions on average. However, the questions asked by Bob could be arbitrary. In this document, we investigate the following question: Are there restricted sets of questions that match the performance of Huffman codes, either exactly or approximately?

Our first main result shows that for every distribution $\pi$, Bob has a strategy that uses only questions of the form “$x < c$?” and “$x = c$?”, and uncovers $x$ using at most $H(\pi)+1$ questions on average, matching the performance of Huffman codes in this sense. We also give a natural set of $O(rn^{1/r})$ questions that achieve a performance of at most $H(\pi)+r$, and show that $\Omega(rn^{1/r})$ questions are required to achieve such a guarantee.

Our second main result gives a set $\mathcal{Q}$ of $1.25^{n+o(n)}$ questions such that for every distribution $\pi$, Bob can implement an optimal strategy for $\pi$ using only questions from $\mathcal{Q}$. We also show that $1.25^{n-o(n)}$ questions are needed, for infinitely many $n$.

If we allow a small slack of $r$ over the optimal strategy, then roughly $(rn)^{\Theta(1/r)}$ questions are necessary and sufficient.

An exposition of Feige’s hardness proof for Maximum Cover, in its version due to Dana Moshkovitz.

This supplements an older exposition of Feige’s hardness proof for Set Cover, which uses Feige’s original construction.

We give an exposition of the recent proof of the Kahn–Kalai conjecture due to Jinyoung Park and Huy Tuan Pham.

Our goal in this sketch is to give an exposition of Independent sets in graph powers are almost contained in juntas by Dinur, Friedgut and Regev, as applied to intersecting families by Dinur and Friedgut in Intersecting families are essentially contained in juntas.

Berge (A theorem related to the Chvátal conjecture) showed that if $\mathcal{F}$ is a downwards-closed family of sets, then either $\mathcal{F}$ or $\mathcal{F} \setminus \{\emptyset\}$ can be partitioned into pairs of disjoint sets.

We reproduce a proof here. For another account, see Section 2.1 of Embla Klingberg, A note on Chvátal’s conjecture.

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.

An exposition of parts of Jan Krajíček’s book Forcing with random variables and proof complexity, concentrating on lower bounds for constant depth proof systems.

Parts of this exposition has been given as talks in a reading group on the book on 13/6/2013 and 20/6/2013.

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.

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.

We survey several recent algorithmic results on submodular maximization:

• The greedy algorithm for monotone submodular maximization over uniform matroids.
• The continuous greedy algorithm for monotone submodular maximization over arbitrary matroids (Calinescu, Chekuri, Pál and Vondrák).
• The non-oblivious local search algorithm for monotone submodular maximization over arbitrary matroids (Filmus and Ward).
• Uncostrained non-monotone submodular maximization (Buchbinder, Feldman, Naor and Schwartz).

We also briefly survey some lower bounds:

• $1-1/e$ NP-hardness for maximum coverage (Feige).
• $1-1/e$ value oracle hardness for monotone submodular maximization over a uniform matroid (Nemhauser and Wolsey).
• $1/2$ value oracle hardness for unconstrained submodular maximization (Feige, Mirrokni and Vondrák).
• The symmetry gap method (Vondrák, Dobzinski and Vondrák).

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

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.

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.

An exposition of Feige’s celebrated result on the hardness of approximating set cover.

This talk was given as part of the PCP reading group on 23/1/2010.

See also an exposition of the hardness of maximum coverage, the dual problem, which uses the modern proof due to Dana Moshkovitz.

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.

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.

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.

We give a complete list of all Boolean degree 2 functions on the Boolean cube.

We give a new proof of the Kindler–Safra theorem, using the invariance principle.

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.

Cryan, Guo and Moussa, Modified log-Sobolev inequalities for strongly log-concave distributions, proved a log-Sobolev inequality for high-dimensional expanders.

We give a simplified proof for the complete complex.

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

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.

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.

Latała and Oleszkiewicz proved the special $L_1$ case of the Khintchine–Kahane inequality. We reformulate their proof using Fourier analysis.

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.

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.

Katona gave a simple proof of the Erdős–Ko–Rado theorem. We adapt his proof to the $\mu_p$ setting. We are also able to prove uniqueness, but not stability.

Stan Wagon gave fourteen proofs of the following result about tiling a rectangle: if a rectangle can be tiled using rectangles with at least one integral side, then the tiled rectangle also has at least one integral side. We paraphrase his 13th proof.

Yaroslav Bulatov asked on mathoverflow what is the asymptotic number of self-avoiding integer walks of length $n$ in which adjacent positions are either 1 or 2 apart. We obtain a formula for the exact number of such walks, and deduce that it is $\tilde{O}(\mu^n)$, where $\mu \approx 2.20556943040059$.

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

We solve the following puzzle: given an arbitrary supply of AND gates and OR gates, invert $n$ inputs using as few NOT gates as possible.

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.

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.

We prove that several equivalent definitions of the Sprague–Grundy function coincide (an exercise given in a course on combinatorial games given by Aviezri Fraenkel).

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.

It is well-known that the until operator in linear temporal logic (LTL) cannot be expressed using next, always and eventually. We provide a simple proof of this fact.

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

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.

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.

We give a combinatorial proof of the identity $\frac{1}{1-x} \cdot \frac{1}{1-y} = \frac{1}{1-x-y+xy}$.

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!

Excerpt from Modèles non-standard en arithmétique et théorie des ensembles, Jean-Pierre Ressayre & Alec J. Wilkie.

Another proof of Cauchy’s theorem, American Mathematical Monthly, Vol. 66 (February 1959), p. 119.

Über die Komposition der quadratischen Formen von beliebig vielen Variablen, Nachrichten von der k. Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-physikalische Klasse, 1898, S. 309–316.

Beweis der Transzendenz der Zahl $e$, Mathematische Annalen, Bd. 43, 1893, S. 220–221.

Translation from Herstein’s Topics in Algebra, p. 176–178.

Transcendenz von $e$ und $\pi$, Mathematische Annalen, Bd. 43, 1893, S. 222–224.

Über die Transzendenz der Zahlen $e$ und $pi$, Mathematische Annalen, Bd. 43, 1893, S. 216–219.

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.

Démonstration d’un Théorème d’Arithmétique, Nouveaux Mémoires de l’Académie royale des Science et Belles-Lettres de Berlin, année 1770.