Bornes inférieures strictes pour la Communication Algébrique et Applications

Communication complexity studies how much information must be exchanged to solve a problem whose input is split among two or more parties. The classical setting deals with Boolean inputs split between two parties. In this work, we study an algebraic variant, where the inputs are vectors over a field F ∈ {R, C}. There are two players, Alice and Bob, with inputs X ∈ F n and Y ∈ F n , respectively. We consider two kinds of tasks. In the polynomial evaluation problem, the goal is to compute the value of a polynomial g ∈ F[X, Y ] on the given input. In the set-recognition problem, the goal is to decide whether (X, Y ) ∈ S, for a given set S ⊆ F n × F n . In both settings, Alice and Bob send evaluations of polynomials depending only on their own inputs. In the polynomial evaluation problem, these messages are combined to compute the evaluation g(X, Y ). In the set-recognition problem, a referee receives the messages and may apply polynomial tests to the messages received so far; the outcomes of these tests determine acceptance or rejection. The protocols may be deterministic or probabilistic. This algebraic communication viewpoint, initiated by Abelson (JACM, 1980) and later developed by Grigoriev (Computational Complexity, 2008), has remained comparatively unexplored. In this work, we revisit this model and demonstrate that it continues to offer a rich framework for new lower bound questions. We present three sets of results.