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 >>>

The Stepanov-Bombieri proof of the Hasse-Weil bound also gives non-trivial bounds on the bias of character sums over curves with small genus, for any low-degree function $f$ that is not completely biased. For high genus curves, and in particular for curves used in AG codes over constant size fields, the ... more >>>