Papers. Sorted in decreasing chronological order.
Authors listed alphabetically, per TCS tradition.

Models of computation between decision trees and communication.
Alexander Knop, Shachar Lovett, SM, Weiqiang Yuan.
SIGACT Complexity Column, June 2021.
[pdf]
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 bitwise XOR or bitwise 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 logrank conjecture and the querytocommunication lifting methodology.

Logrank and lifting
for ANDfunctions.
Alexander Knop, Shachar Lovett, SM, Weiqiang Yuan.
STOC 2021.
[pdf]
[slides]
[poster]
[video@STOC]
Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let
$f_\land (x, y) = f(x \land y)$ denote the ANDfunction
of $f$,
where $x \land y$ denotes bitwise 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 logrank conjecturefor ANDfunctions with no assumptions on $f$.
Our result stands in contrast with previous results on special cases of the logrank
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 ANDfunctions, stating that the deterministic communication
complexity of $f_\land$ is polynomiallyrelated to the ANDdecision 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 polylogarithmic in its sparsity.
We also establish extensions of this result to multilinear polynomials
$f:\{0,1\}^n \to \mathbb{R}$
with a larger range.

Comparing computational entropies below majority (or: When is the dense model theorem false?)
Russell Impagliazzo, SM.
ITCS 2021.
[pdf]
[slides]
[video@ITCS]
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 socalled dense model
theorem of Green and Tao (and later made explicit by TaoZeigler, 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.

Model Checking Sparse Structures in Dynamic
Descriptive Complexity Theory.
SM.
Undergraduate thesis.
[pdf]
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 recomputation 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{DynQF}$ algorithm for modelchecking $\text{FO}$ properties on boundeddegree structures. The main technical tool is an algorithm for maintaining the neighborhoods of elements in boundeddegree 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 firstorder property and model checking the counting logic $\text{FOCN}(\textbf{P})$ recently introduced by Kuske and Schweikardt. This in turn establishes $\text{DynQF}$ algorithms for simulating $\text{FO}(COUNT)$ properties on boundeddegree structures, making partial progress towards the conjecture that $\text{FO}(COUNT) \subseteq \text{DynFO}$, originally made by Patnaik and Immerman in the '90s.

On exactitude in science. Jorge Luis Borges.
...In that Empire, the Art of Cartography attained such Perfection that the map of a
single Province occupied the entirety of a City, and the map of the Empire, the entirety
of a Province. In time, those Unconscionable Maps no longer satisfied, and the
Cartographers Guilds struck a Map of the Empire whose size was that of the Empire, and
which coincided point for point with it. The following Generations, who were not so
fond of the Study of Cartography as their Forebears had been, saw that that vast Map
was Useless, and not without some Pitilessness was it, that they delivered it up to the
Inclemencies of Sun and Winters. In the Deserts of the West, still today, there are
Tattered Ruins of that Map, inhabited by Animals and Beggars; in all the Land there is
no other Relic of the Disciplines of Geography.
 Suarez Miranda, Viajes devarones prudentes, Libro IV, Cap. XLV, Lerida, 1658
