English | Français     A A     Connect With Us

Ashwin Nayak

Ashwin Nayak's picture
Affiliate
University of Waterloo - Department of Combinatorics and Optimization

Area of Research:
Quantum Information
Website: http://www.math.uwaterloo.ca/~anayak
Email: anayak@math.uwaterloo.ca
Phone: x33601

Ashwin Nayak received his PhD in Computer Science from University of California, Berkeley, in 1999. Subsequently, he held positions at DIMACS Center (Rutgers University) and AT&T Labs-Research, at California Institute of Technology, and at Mathematical Sciences Research Institute, Berkeley. Ashwin is an associate professor in Department of Combinatorics and Optimization, a member of Institute for Quantum Computing at University of Waterloo, and a scholar of Canadian Institute for Advanced Research.

AFFILIATIONS

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

Awards

  • 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

Seminars

  • 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.
  • Recognizing well-parenthesized expressions in the streaming model. DIMACS Theoretical Computer Science seminar, Rutgers, New Brunswick, NJ, April 6, 2011.
  • Improved bounds for the randomized decision tree complexity of recursive majority. Computer Science and Discrete Mathematics seminar, IAS, Princeton, NJ, April 4, 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.