Propositional proof complexity deals with the lengths of polynomial-time verifiable proofs for Boolean tautologies. An abundance of proof systems is known, including algebraic and semialgebraic systems, which work with polynomial equations and inequalities, respectively. The most basic algebraic proof system is based on Hilbert's Nullstellensatz (Beame et al., 1996). Tropical ... more >>>

Lifting theorems are theorems that bound the communication complexity
of a composed function $f\circ g^{n}$ in terms of the query complexity
of $f$ and the communication complexity of $g$. Such theorems
constitute a powerful generalization of direct-sum theorems for $g$,
and have seen numerous applications in recent years.

We prove ... more >>>

The notion of query-to-communication lifting theorems is a generic framework to convert query lower bounds into two-party communication lower bounds. Though this framework is very generic and beautiful, it has some inherent limitations such as it only applies to lifted functions. In order to address this issue, we propose gadgetless ... more >>>