Tight Lower Bounds for Algebraic Communication and Applications
A general framework for proving lower bounds for algebraic set-recognition problems and several probabilistic lower bounds for natural problems are proved, giving tight or near-tight characterizations of their algebraic communication.