Anurag Anshu: Separations in communication complexity using cheat sheets and information complexity

Channel:
Microsoft Research
Subscribers:
345,000
Published on ● Video Link: https://www.youtube.com/watch?v=1TSdQRiQAKE


Category:
Guide
Duration: 24:46
1,078 views
22

"While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power 2.5 gap. We further present a 1.5 power separation between exact quantum and randomized communication complexity, improving on the previous ~1.15 separation by Ambainis (STOC 2013). Finally, we present a nearly optimal quadratic separation between randomized communication complexity and the logarithm of the partition number, improving upon the previous best power 1.5 separation due to G\""o\""os, Jayram, Pitassi, and Watson.

Our results are the communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). Our main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat sheet framework to communication complexity."



Other Videos By Microsoft Research


2017-01-31Fernando Brandao: Quantum speed-ups for semidefinite programming
2017-01-31Joseph M. Renes: Belief propagation decoding of quantum channels by passing quantum messages
2017-01-31Anupam Prakash: Quantum recommendation systems
2017-01-31Garnet Chan: Simulating quantum systems on classical computers
2017-01-31Rigetti Computing Software Demo: Forest
2017-01-31Frank Verstraete: The entanglement of distillation for gauge theories
2017-01-31Aram Harrow: Sequential measurements, disturbance and property testing
2017-01-31Carlo Sparaciari: A resource theory for work and heat
2017-01-31Mark Howard: Application of a resource theory for magic states to fault-tolerant quantum computing
2017-01-31John Preskill: Quantum information and spacetime (II)
2017-01-31Anurag Anshu: Separations in communication complexity using cheat sheets and information complexity
2017-01-31Florian Speelman: Quantum homomorphic encryption for polynomial-sized circuits (Best Student Paper)
2017-01-31John Preskill: Quantum information and spacetime (I)
2017-01-31Earl Campbell: Unifying gate-synthesis and magic state distillation
2017-01-31Zhengfeng Ji: Compression of quantum multi-prover interactive proofs
2017-01-31Fang Song: Zero-knowledge proof systems for QMA
2017-01-31Norbert Schuch: Matrix product states and tensor networks (I)
2017-01-31Norbert Schuch: Matrix product states and tensor networks (II)
2017-01-31Steve Flammia: Debugging the next generation of quantum devices (I)
2017-01-31Steve Flammia: Debugging the next generation of quantum devices (II)
2017-01-31Lídia del Rio: Quantum thermodynamics (I)


Tags:
microsoft research