The polylogarithmic-party interleaved group-product hardness conjecture

The conjecture asks whether computing an interleaved product for $k=\log^c t$ parties necessarily requires more than $\log^c t$ communication over a non-abelian simple group. Gowers and Viola formulated the broader hardness challenge in 2018; neither their paper nor later sources resolves this exact formulation.

Known results

• Gowers and Viola (2018): for $G=\mathrm{SL}(2,q)$, a lower bound of roughly $(t\log |G|)/b^{2^k}$, becoming $\Omega(t\log |G|)$ for fixed $k$ and sufficiently large $t$.
• Gowers and Viola (2018): conjectured improving the party dependence from $b^{2^k}$ to $b^k$, and identified hardness with more than logarithmically many parties as open.
• The literature reports no known non-trivial protocol for the related iterated-product candidate.

2024 related bounds

A 2024 paper gives improved lower bounds of the form $(t\log H)/c^k$ for certain quasirandom groups and calls the broader many-party problem a major open question, but it neither proves nor refutes the stated $k=\log^c t$, communication-$\log^c t$ conjecture.

Current status (as of August 2026): The conjecture remains open; partial lower bounds are known, but no proof, counterexample, or protocol settling the stated polylogarithmic-party regime has been reported.