New answers tagged

2

It is big open problem to prove lower bounds. This would imply lower bounds for BP.PP communication protocols (e.g., Tarui's Theorem in communication complexity), which would then imply lower bounds on matrix rigidity (over the real numbers). For inner product, there is $O(1)$-bit public coin protocol for $\epsilon=1/n^{O(1)}$. Let me simplify by assuming ...


Top 50 recent answers are included