Papers:

Russell Impagliazzo, Sam McGuire.
Computational lowers bounds on dense model
theorems.
In submission.
[pdf (soon...)]
We show lower bounds on two different types of dense model theorems. When the dense model theorem says that "dense
subsets of pseudorandom sets have dense models", we show that this turns out to be false $\text{AC}^0$.
We can also frame this result as saying the commonlyused information theoretic lemma that most bits of a
dense subsets of the uniform distribution on $\{0, 1\}^n$ are unbiased is false when we replace 'uniform distribution'
with 'distribution pseudorandom for $\text{AC}^0$'.
When the dense model theorem says that "pseudodense subsets have dense models", we show that any proof of this fact
can be used to solve a variant of the coin problem, which can further be used to approximate majority. We then show that
this is tight in the sense that we give a proof of the dense model theorem that uses solutions to the coin problem
instead of majority.
A few other observations related to pseudoentropy, hardcore lemmas and boosting are made along the way.

Sam McGuire.
Model Checking Sparse Structures in Dynamic
Descriptive Complexity Theory.
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.
