We show that for any unsatisfiable CNF formula $\varphi$ that requires resolution refutation width at least $w$, and for any $1$-stifling gadget $g$ (for example, $g=MAJ_3$), (1) every resolution-over-parities (Res($\oplus$)) refutation of the lifted formula $\varphi \circ g$ of size at most $S$ has depth at least $\Omega(w^2/\log S)$; (2) ... more >>>

We study query-to-communication lifting. The major open problem in this area is to prove a lifting theorem for gadgets of constant size. The recent paper (Beame, Koroth, 2023) introduces semi-structured communication complexity, in which one of the players can only send parities of their input bits. They have shown that ... more >>>

We reduce the best-known upper bound on the length of a program that enumerates a set in terms of the probability of it being enumerated by a random program. We prove a general result that any linear upper bound for finite sets implies the same linear bound for infinite sets.

... more >>>