Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols

Lijie Chen, Ruosong Wang

The polynomial method from circuit complexity has been applied to several fundamental problems and obtains the state-of-the-art running times. As observed in [Alman and Williams, S…