Dave Touchette

Dave Touchette's picture

Area of Research:
Email: dtouchette@perimeterinstitute.ca

Research Interests

My main area of research lies at the intersection of the Theories of Computation and Quantum Information. My previous projects have served to establish the field of interactive quantum information theory on solid foundations, proving interactive and quantum analogues to Shannon"s classical coding theorems. Studying interactive rather than only unidirectional information theory is of particular value due to the interactive nature of most communication. Moreover, this field has drawn attention in both the classical and quantum settings because problems of interest in other concrete models of computation (e.g., circuits, data structures and streaming algorithms) can be reduced to problems in this area.

Awards

  • NSERC PDF, Jan 2018-Dec 2019

Recent Publications

  • Dave Touchette, Benjamin Lovitz, Norbert Lütkenhaus, Practical Quantum Appointment Scheduling, Phys. Rev. A 97, 042320, April 2018, Editor's suggestion; arXiv: 1801.02771.
  • Mario Berta, Matthias Christandl, Dave Touchette, Smooth Entropy Bounds on One-Shot Quantum State Redistribution, IEEE Transactions on Information Theory, 62 (3) March 2016; 1425-1439, arXiv: 1409.4338.
  • Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette, Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity, SIAM Journal on Computing, Invited to special issue on FOCS'15, accepted for publication in June 2017, arXiv: 1505.03110
  • Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, Falk Unger, Noisy Interactive Quantum Communication, submitted April 2018, arXiv: 1309.2643
  • Juan Miguel Arrazola, Dave Touchette, Quantum Advantage on Information Leakage for Equality, submitted October 2016, arXiv: 1607.07516
  • Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu, Capacity Approaching Coding for Low Noise Interactive Quantum Communication, STOC'18, Theoretical Computer Science.
  • Ashwin Nayak, Dave Touchette, Augmented Index and Quantum Streaming Algorithms for DYCK(2), CCC'17, Computational Complexity, arXiv: 1610.04937
  • Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu, Exponential Separation of Quantum Communication and Classical Information, STOC'17, Theoretical Computer Science, arXiv: 1611.08946
  • Mathieu Lauriere, Dave Touchette, The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting, ITCS'17, Theoretical Computer Science, arXiv: 1701.02062
  • Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette, Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity, FOCS'15, Theoretical Computer Science, arXiv: 1505.03110
  • Dave Touchette, Interactive Quantum Information Theory, PhD thesis, Universite de Montreal, final version submitted August 2015

Seminars

  • Interactive Quantum Information Theory. INTRIQ Spring 2018 Meeting, Bromont, Canada
  • Capacity Approaching Coding for Low Noise Interactive Quantum Communication. Conference on Quantum Information Theory, Institut Henri-Poincaré, Paris, France
  • Practical Quantum Appointment Scheduling. IRIF-IQC Workshop on Quantum Information Processing, Université Paris-Diderot, Paris, France
  • Practical Quantum Appointment Scheduling. QuICS Seminars, University of Maryland, College Park, MD
  • Quantum Information Complexity. QCrypt 2017 invited talk, University of Cambridge, Cambridge, UK
  • Augmented Index and Quantum Streaming Algorithms for DYCK(2), CCC'17, Riga, Latvia
  • Information-Theoretic Tools for Interactive Quantum Protocols, and Applications, 20th Conference on Quantum Information Processing (QIP"17), Seattle, WA
  • Exponential Separation of Information and Quantum Communication (plenary talk), 20th Conference on Quantum Information Processing (QIP"17), Seattle, WA
  • Exponential Separation of Information and Quantum Communication, iQuISE Seminars, Massachusetts Institute of Technology (MIT), Boston, MA