A A   
Connect with us:      
Le contenu de cette page n’est pas disponible en français. Veuillez nous en excuser.

Ashwin Nayak

Portrait de Ashwin Nayak
University of Waterloo - Department of Combinatorics and Optimization

Area of Research:
Email: anayak@uwaterloo.ca
Phone: x33601

Ashwin Nayak is a professor in the Department of Combinatorics and Optimization. He studied theoretical computer science at Indian Institute of Technology, Kanpur (BTech, 1995) and at University of California, Berkeley (PhD, 1999). After holding post-doctoral positions at DIMACS Center (Rutgers University) and AT&T Labs-Research (2000) and California Institute of Technology (2001-02), he joined the University of Waterloo in 2002. He was Associate Faculty, Perimeter Institute for Theoretical Physics, Waterloo, from 2003--11.


Department of Combinatorics and Optimization, and Institute for Quantum Computing, University of Waterloo.

Research Interests

The use of quantum-physical properties of matter in computation leads
to extraordinary applications, including efficient algorithms for hard
computational problems, and cryptographic schemes previously thought
impossible. Ashwin Nayak's research focuses on the study of information
in quantum states, and its applications to computing, communication, and

Ashwin Nayak has studied the encoding of classical information into
quantum states, resource requirements for communication using such
states, limits on the efficiency of quantum computers, and algorithmic
techniques such as quantum walks. His current research is directed
towards developing stronger and more robust methods for proving lower
bounds for quantum computation and communication, and faster
quantum algorithms for computational problems such as those arising
in physics.


  • Discovery Accelerator Supplement (award), NSERC Canada
  • Early Researcher Award, Province of Ontario
  • Scholar (honour), Quantum Information Processing, Canadian Institute for Advanced Research

Recent Publications

  • Frederic Magniez, Ashwin Nayak, Jeremie Roland, and Miklos Santha. Search via Quantum Walk. SIAM Journal on Computing 40(1):142--164, 2011.
  • Frederic Magniez, Claire Mathieu, and Ashwin Nayak. Recognizing Well-Parenthesized Expressions in the Streaming Model. In Proceedings of the Forty-second Annual ACM Symposium on the Theory of Computing, pp. 261--270, 2010. arXiv: 0911.3291
  • Rahul Jain, Hartmut Klauck, and Ashwin Nayak. Direct Product Theorems for Communication Complexity via Subdistribution Bounds. In Proceedings of the Fortieth Annual ACM Symposium on the Theory of Computing, pages 599--608, 2008
  • Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, and David Zuckerman. Interaction in Quantum Communication. IEEE Transactions on Information Theory, 53(6), pages 1970--1982, Jun. 2007. arXiv: quant-ph/0506265
  • The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: the Index Function Revisited. Rahul Jain and Ashwin Nayak. arXiv: 1004.3165
  • A Short Proof of the Quantum Substate Theorem. Rahul Jain and Ashwin Nayak. arXiv: 1103.6067


  • The index function and the streaming complexity of Dyck languages. Centre for Quantum Techologies, National University of Singapore, Singapore, January 28, 2011.
  • The Quantum Substate Theorem. Institute for Quantum Information seminar, Caltech, Pasadena, CA, June 28, 2011.
  • Improved bounds for the randomized decision tree complexity of recursive majority. Computer Science and Discrete Mathematics seminar, IAS, Princeton, NJ, April 4, 2011.
  • Recognizing well-parenthesized expressions in the streaming model. DIMACS Theoretical Computer Science seminar, Rutgers, New Brunswick, NJ, April 6, 2011.
  • Fault-tolerant quantum communication with constant overhead. Quantum Computation seminar, MIT, Cambridge, MA, USA. October 13, 2009.
  • Quantum information and complexity I, II. The Boulder School in Condensed Matter and Materials Physics: Computational and Conceptual Approaches to Quantum Many-Body Systems, University of Colorado, Boulder, CO, July 22--23, 2010.
  • Fault-tolerant quantum communication with constant overhead. DIMACS seminar on Theoretical Computer Science, Rutgers, Piscataway, NJ, USA. September 30, 2009.
  • Cryptography through Quantum Mechanics. Certicom Corporation, Mississauga, ON, Canada. April 17, 2008.
  • On Divergence Information I, II. Laboratoire de Recherche en Informatique (LRI), Centre National de la Recherche Scientifique (CNRS), Orsay, France. February, 2008.
  • Search via quantum walk. The Tenth Workshop on Quantum Information Processing, Brisbane, QLD, Australia. February, 2007.