We consider the query complexity of testing whether a bounded-degree graph is expanding, regardless of whether or not it is connected.

Whereas prior work studied testing the property of being an expander (equiv., testing the set of expander graphs), here we study testing the set of graphs that consist of ... more >>>

We first extend the results of CKSV22 by showing that the degree $d$ elementary symmetric polynomials in $n$ variables have formula lower bounds of $\Omega(d(n-d))$ over fields of positive characteristic.
Then, we show that the results of the universality of the symmetric model from Shp02 and the results about border ... more >>>

Several proof systems for model counting have been introduced in recent years, mainly in an attempt to model #SAT solving and to allow proof logging of solvers. We reexamine these different approaches and show that: (i) with slight adaptations, the conceptually quite different proof models of the dynamic system MICE ... more >>>