Iterated Sub-Permutation Matrix Multiplication is the problem of computing the product of kn-
by-n Boolean matrices with at most a single 1 in each row and column. For all d≤ log k, this …

In 1981, Neil Immerman described a two-player game, which he called the" separability
game"\cite {Immerman81}, that captures the number of quantifiers needed to describe a …

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth
δ+ 1 to one of product-depth δ in the multilinear setting. We show that for every positive δ= δ …

We give the best known pseudorandom generators for two touchstone classes in
unconditional derandomization: an $\varepsilon $-PRG for the class of size-$ M $ depth-$ d …

We study the complexity of computing symmetric and threshold functions by constant-depth
circuits with Parity gates, also known as AC^ 0 [oplus] circuits. Razborov [Alexander A …

How can the result of a query be updated after changing a database? This is a fundamental
task for database management systems which ideally takes previously computed …

Previous work of the author [Rossman 2008a] showed that the Homomorphism Preservation
Theorem of classical model theory remains valid when its statement is restricted to finite …

Consider a random sequence of n bits that has entropy at least n− k, where k ≪ nk≪ n. A
commonly used observation is that an average coordinate of this random sequence is close …

Whether a changing string is member of a certain regular language can be maintained in the
DynFO framework of Patnaik and Immerman: after changing the symbol at one position of …

In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-
order formulas after inserting or deleting single edges. Later, in 2018, this was extended for …