- Home »
- Ashwin Nayak

University of Waterloo - Department of Combinatorics and Optimization

Area of Research:

Website: http://www.math.uwaterloo.ca/~anayak

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.

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

cryptography.

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

- 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.

©2012 Perimeter Institute for Theoretical Physics