Mixing in non-quasirandom groups
summary
Paper proves concrete communication bounds for the three-party product=1 problem in three non-quasirandom, non-almost-abelian families: affine groups get theta(log |G|) communication, finite lamplighter groups get theta(log log |G|), and product groups H^N (constant nonabelian H) get an omega(log N) lower bound. Mixing is defined via a distribution over functions f and constructed explicitly: affine f sets the top-right entry to a uniform field element, lamplighter f re-randomizes bits preserving parity, H^N mixes by picking a random coordinate and replacing it by a uniform conjugate; proofs use nonabelian Fourier analysis and truncation of low-dimension irreps, giving an inherent error of 1/n.
AI-written summary · about