One of the major open problems in communication complexity is to show interesting lower bounds for the Arthur-Merlin (AM) communication complexity of some natural problems (i.e., lower bounds of the form $\omega(\log n)$ for problems where the input strings have length $n$) .

High-level question: why is showing lower bounds for AM communication complexity difficult? Are there concrete barriers or obstacles that make certain proof techniques fail? Would there be any surprising or strong implications if we were to establish good AM lower bounds?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.