We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions. We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function $MAJ \circ XOR$ requires size $2^{0.18 n}$.
This completely answers an open question of Turán and Vatan. We also show that the spectral classes $PL_1, PL_\infty$, and the polynomial threshold function classes PT$_1, PT_1$, are incomparable to linear decision lists.

We study the arithmetic circuit complexity of some well-known families of polynomials through the lens of parameterized complexity. Our main focus is on the construction of explicit algebraic branching programs (ABPs) for the determinant and the permanent polynomials of the rectangular symbolic matrix in both commutative and noncommutative settings. The main results are:

1. We show an explicit $O^{*}({n\choose {\downarrow k/2}})$-size ABP construction for the noncommutative permanent polynomial of a $k\times n$ symbolic matrix. We obtain this via an explicit ABP construction of size $O^{*}({n\choose {\downarrow k/2}})$ for $S_{n,k}^*$, the noncommutative symmetrized version of the elementary symmetric polynomial $S_{n,k}$.
2. We obtain an explicit $O^{*}(2^k)$-size ABP construction for the commutative rectangular determinant polynomial of the $k\times n$ symbolic matrix.
3. In contrast, we show that evaluating the rectangular noncommutative determinant with rational matrix entries is $\#W[1]$-hard.

Set disjointness Disj is a central problem in communication complexity. Here Alice and Bob each receive a subset of an n-element universe, and they need to decide whether their inputs intersect or not. The communication complexity of this problem is relatively well understood, and in most models, including -- most famously -- interactive randomised communication with bounded error $\mathcal{R}$, the problem requires much communication.

In this work we were looking for a variation of Disj, as natural and simple as possible, for which the known lower bound methods would fail, and thus a new approach would be required in order to understand its $\mathcal{R}$-complexity. The problem that we have found is a relational one: each player receives a subset as input, and the goal is to find an element that belongs to both players. We call it inevitable intersection $\mathcal{II}$. The following list of its properties seem to let $\mathcal{II}$ resist the old lower bound techniques:

• the domain of $\mathcal{II}$ is $A\times B$, the product of the players' individual input spaces;
• $A\times B$ only contains intersecting pairs of subsets;
• the input comes from the uniform distribution over $A\times B$;
• $A\times B$ is chosen in a randomised fashion, both $A$ and $B$ being uniformly-random subsets of $2^{[n]}$ of size $2^{n^{\Theta(1)}}$.

In particular, complexity analysis of $\mathcal{II}$ cannot be based on the hardness of Disj (as no pair in $A\times B$ is disjoint); moreover, it cannot be based on any argument based on discrepancy (including corruption, smooth discrepancy and the like), as the problem allows for a cover of $A\times B$ by $n$ perfectly-monochromatic rectangles.

We are using an ad hoc technique to show that $\mathcal{II}$ is ultimately hard: it requires $\Omega(\log |A|)$ bits of interactive randomised communication. Besides its ability -- apparently unique -- to capture the complexity of the inevitable intersection, the new technique can also be applied to other ``search-like'' problems (including Disj), thus providing new insight into their communicational hardness.

• Coin Theorems and the Fourier Expansion by Rohit Agrawal
  August 31, 2020
  

  In this note we compare two measures of the complexity of a class $\mathcal{F}$ of Boolean functions studied in (unconditional) pseudorandomness: $\mathcal{F}$'s ability to distinguish between biased and uniform coins (the coin problem), and the norms of the different levels of the Fourier expansion of functions in $\mathcal{F}$ (the Fourier growth). We show that for coins with low bias $\epsilon = o(1/n)$, a function's distinguishing advantage in the coin problem is essentially equivalent to $\epsilon$ times the sum of its level $1$ Fourier coefficients, which in particular shows that known level $1$ and total influence bounds for some classes of interest (such as constant-width read-once branching programs) in fact follow as a black-box from the corresponding coin theorems, thereby simplifying the proofs of some known results in the literature. For higher levels, it is well-known that Fourier growth bounds on all levels of the Fourier spectrum imply coin theorems, even for large $\epsilon$, and we discuss here the possibility of a converse.