We survey recent work on the communication complexity of functions $F : \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}$ of the form $f (x \circ y)$ where $f : \{0, 1\}^n → \{0, 1\}$ is a total boolean function and $\circ$ represents either bit-wise XOR or bit-wise AND. This naturally leads to the study of models of computation that are, in a sense, 'between' communication complexity and decision tree complexity. These classes of functions capture a rich class of communication problems while simultaneously being amenable to analysis with minimal assumptions about the structure of $f$. This flexibility has shed new light on central topics in communication complexity, including restricted cases of the log-rank conjecture and the query-to-communication lifting methodology.

Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land (x, y) = f(x \land y)$ denote the AND-function of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_\land$ and show that, up to a $\log n$ factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of $f_\land$. This comes within a $\log n$ factor of establishing the log-rank conjecturefor AND-functions with no assumptions on $f$. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on $f$ such as monotonicity or low $\mathbb{F}_2$-degree. Our techniques can also be used to prove (within a $\log n$ factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of $f_\land$ is polynomially-related to the AND-decision tree complexity of $f$.

The results rely on a new structural result regarding boolean functions $f:\{0, 1\}^n \to \{0, 1\}$ with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing $f$ has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials $f:\{0,1\}^n \to \mathbb{R}$ with a larger range.

Computational pseudorandomness studies the extent to which a random variable $\mathbf{Z}$ looks like the uniform distribution according to a class of tests $\mathcal{F}$. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a high entropy distribution. There are different formal definitions of computational entropy with different advantages for different applications. Because of this, it is of interest to understand when these definitions are equivalent.

We consider three notions of computational entropy which are known to be equivalent when the test class $\mathcal{F}$ is closed under taking majorities. This equivalence constitutes (essentially) the so-called dense model theorem of Green and Tao (and later made explicit by Tao-Zeigler, Reingold et al., and Gowers). The dense model theorem plays a key role in Green and Tao's proof that the primes contain arbitrarily long arithmetic progressions and has since been connected to a surprisingly wide range of topics in mathematics and computer science, including cryptography, computational complexity, combinatorics and machine learning. We show that, in different situations where $\mathcal{F}$ is not closed under majority, this equivalence fails. This in turn provides the first examples to appear in the literature in which the dense model theorem is false.

Dynamic descriptive complexity seeks to characterize the complexity of queries in terms of the logical language required to express update programs that maintain them. It is a natural notion in the study of relational databases: the database is subject to change and the total re-computation of a query may not be feasible due to both the rate of change, the static complexity of the query, or simply the size of the database in question.

Here, we present a $\text{Dyn-QF}$ algorithm for model-checking $\text{FO}$ properties on bounded-degree structures. The main technical tool is an algorithm for maintaining the neighborhoods of elements in bounded-degree structures, which can be then be applied to perform model checking on particular logics admitting local normal forms. As applications of the methodology, we show algorithms for maintaining the number of witnesses to a first-order property and model checking the counting logic $\text{FOCN}(\textbf{P})$ recently introduced by Kuske and Schweikardt. This in turn establishes $\text{Dyn-QF}$ algorithms for simulating $\text{FO}(COUNT)$ properties on bounded-degree structures, making partial progress towards the conjecture that $\text{FO}(COUNT) \subseteq \text{Dyn-FO}$, originally made by Patnaik and Immerman in the '90s.