Complete Classifications for the Communication Complexity of Regular Languages

摘要

We show that every regular language L has either constant, logarithmic or linear two-party communication complexity (in a worst-case partition sense). We prove a similar trichotomy for simultaneous communication complexity and a "quadrichotomy" for probabilistic communication complexity.