Spatial Codes and the Hardness of String Folding Problems (Extended Abstract). - Ashwin Nayak 001; Alistair Sinclair; Uri Zwick (SODA, 1998)

Optimal Lower Bounds for Quantum Automata and Random Access Codes. - Ashwin Nayak 001 (FOCS, 1999)

Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. - Andris Ambainis; Ashwin Nayak 001; Amnon Ta-Shma; Umesh V. Vazirani (STOC, 1999)

The Quantum Query Complexity of Approximating the Median and Related Statistics. - Ashwin Nayak 001; Felix Wu (STOC, 1999)

Spatial Codes and the Hardness of String Folding Problems. - Ashwin Nayak 001; Alistair Sinclair; Uri Zwick (J. Comput. Biol., 1999)

Interaction in Quantum Communication Complexity - Ashwin Nayak 001; Amnon Ta-Shma; David Zuckerman (CoRR, 2000)

One-dimensional quantum walks. - Andris Ambainis; Eric Bach 001; Ashwin Nayak 001; Ashvin Vishwanath; John Watrous (STOC, 2001)

Interaction in quantum communication and the complexity of set disjointness. - Hartmut Klauck; Ashwin Nayak 001; Amnon Ta-Shma; David Zuckerman (STOC, 2001)

On communication over an entanglement-assisted quantum channel. - Ashwin Nayak 001; Julia Salzman (STOC, 2002)

Dense quantum coding and quantum finite automata. - Andris Ambainis; Ashwin Nayak 001; Amnon Ta-Shma; Umesh V. Vazirani (J. ACM, 2002)

Weak coin flipping with small bias. - Iordanis Kerenidis; Ashwin Nayak 001 (Inf. Process. Lett., 2004)

Limits on the ability of quantum states to convey classical messages. - Ashwin Nayak 001; Julia Salzman (J. ACM, 2006)

Quantum Complexity of Testing Group Commutativity. - Frédéric Magniez; Ashwin Nayak 001 (Algorithmica, 2007)

Direct Product Theorems for Communication Complexity via Subdistribution Bounds. - Rahul Jain 001; Hartmut Klauck; Ashwin Nayak 001 (Electron. Colloquium Comput. Complex., 2007)

Invertible quantum operations and perfect encryption of quantum states. - Ashwin Nayak 001; Pranab Sen (Quantum Inf. Comput., 2007)

Interaction in Quantum Communication. - Hartmut Klauck; Ashwin Nayak 001; Amnon Ta-Shma; David Zuckerman (IEEE Trans. Inf. Theory, 2007)

Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract. - Rahul Jain 001; Hartmut Klauck; Ashwin Nayak 001 (STOC, 2008)

Quantum Algorithm for Checking Matrix Identities. - Ashwin Nayak 001 (Encyclopedia of Algorithms, 2008)

Foreword from the Guest Editors. - Frédéric Magniez; Ashwin Nayak 001 (Algorithmica, 2009)

Special Section on Foundations of Computer Science. - Matthew Andrew; Ashwin Nayak 001; Rajmohan Rajaraman (SIAM J. Comput., 2009)

The space complexity of recognizing well-parenthesized expressions. - Rahul Jain 001; Ashwin Nayak 001 (Electron. Colloquium Comput. Complex., 2010)

Improved bounds for the randomized decision tree complexity of recursive majority. - Frédéric Magniez; Ashwin Nayak 001; Miklos Santha; David Xiao (Electron. Colloquium Comput. Complex., 2010)

Inverting a permutation is as hard as unordered search. - Ashwin Nayak 001 (Electron. Colloquium Comput. Complex., 2010)

A separation between divergence and Holevo information for ensembles. - Rahul Jain 001; Ashwin Nayak 001; Yi Su (Math. Struct. Comput. Sci., 2010)

A short proof of the Quantum Substate Theorem - Rahul Jain 001; Ashwin Nayak 001 (CoRR, 2011)

Search via Quantum Walk. - Frédéric Magniez; Ashwin Nayak 001; Jérémie Roland; Miklos Santha (SIAM J. Comput., 2011)

On the Hitting Times of Quantum Versus Random Walks. - Frédéric Magniez; Ashwin Nayak 001; Peter C. Richter; Miklos Santha (Algorithmica, 2012)

Short Proofs of the Quantum Substate Theorem. - Rahul Jain 001; Ashwin Nayak 001 (IEEE Trans. Inf. Theory, 2012)

Recognizing Well-Parenthesized Expressions in the Streaming Model. - Frédéric Magniez; Claire Mathieu; Ashwin Nayak 001 (SIAM J. Comput., 2014)

The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited. - Rahul Jain 001; Ashwin Nayak 001 (IEEE Trans. Inf. Theory, 2014)

Quantum and classical coin-flipping protocols based on bit-commitment and their point games. - Ashwin Nayak 001; Jamie Sikora; Levent Tunçel (CoRR, 2015)

A search for quantum coin-flipping protocols using optimization techniques. - Ashwin Nayak 001; Jamie Sikora; Levent Tunçel (Math. Program., 2016)

Improved bounds for the randomized decision tree Complexity of recursive majority. - Frédéric Magniez; Ashwin Nayak 001; Miklos Santha; Jonah Sherman; Gábor Tardos; David Xiao (Random Struct. Algorithms, 2016)

Quantum Algorithms for Matrix Multiplication and Product Verification. - Robin Kothari; Ashwin Nayak 001 (Encyclopedia of Algorithms, 2016)

Quantum Analogues of Markov Chains. - Ashwin Nayak 001; Peter C. Richter; Mario Szegedy (Encyclopedia of Algorithms, 2016)

Augmented Index and Quantum Streaming Algorithms for DYCK(2). - Ashwin Nayak 001; Dave Touchette (CCC, 2017)

Online Learning of Quantum States. - Scott Aaronson; Xinyi Chen 001; Elad Hazan; Satyen Kale; Ashwin Nayak 001 (NeurIPS, 2018)

Capacity approaching coding for low noise interactive quantum communication. - Debbie W. Leung; Ashwin Nayak 001; Ala Shayeghi; Dave Touchette; Penghui Yao; Nengkun Yu (STOC, 2018)

Online Learning of Quantum States. - Scott Aaronson; Xinyi Chen 001; Elad Hazan; Ashwin Nayak 001 (CoRR, 2018)

Communication Complexity of One-Shot Remote State Preparation. - Shima Bab Hadiashar; Ashwin Nayak 001; Renato Renner (IEEE Trans. Inf. Theory, 2018)

Noisy Interactive Quantum Communication. - Gilles Brassard; Ashwin Nayak 001; Alain Tapp; Dave Touchette; Falk Unger (SIAM J. Comput., 2019)

On the Entanglement Cost of One-Shot Compression. - Shima Bab Hadiashar; Ashwin Nayak 001 (Quantum, 2020)

Capacity Approaching Coding for Low Noise Interactive Quantum Communication Part I: Large Alphabets. - Debbie W. Leung; Ashwin Nayak 001; Ala Shayeghi; Dave Touchette; Penghui Yao; Nengkun Yu (IEEE Trans. Inf. Theory, 2021)

Deterministic algorithms for the hidden subgroup problem. - Ashwin Nayak 001 (Quantum Inf. Comput., 2022)

Quantum Distributed Complexity of Set Disjointness on a Line. - Frédéric Magniez; Ashwin Nayak 001 (ACM Trans. Comput. Theory, 2022)

Mutually Unbiased Measurements, Hadamard Matrices, and Superdense Coding. - Máté Farkas; Jedrzej Kaniewski; Ashwin Nayak 001 (IEEE Trans. Inf. Theory, 2023)

One-Shot Quantum State Redistribution and Quantum Markov Chains. - Anurag Anshu; Shima Bab Hadiashar; Rahul Jain 001; Ashwin Nayak 001; Dave Touchette (IEEE Trans. Inf. Theory, 2023)

Proper vs Improper Quantum PAC learning. - Ashwin Nayak 001; Pulkit Sinha (CoRR, 2024)

Optimal Lower Bounds for Quantum Learning via Information Theory. - Shima Bab Hadiashar; Ashwin Nayak 001; Pulkit Sinha (IEEE Trans. Inf. Theory, 2024)

Lower Bounds for Learning Quantum States with Single-Copy Measurements. - Ashwin Nayak 001; Angus Lowe (ACM Trans. Comput. Theory, 2025)