Ashwin Nayak

According to our database, Ashwin Nayak authored at least 50 papers between 1998 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Lower Bounds for Learning Quantum States with Single-Copy Measurements.

Ashwin Nayak, Angus Lowe

ACM Trans. Comput. Theory, March, 2025

2024

Optimal Lower Bounds for Quantum Learning via Information Theory.

Shima Bab Hadiashar, Ashwin Nayak, Pulkit Sinha

IEEE Trans. Inf. Theory, 2024

Proper vs Improper Quantum PAC learning.

Ashwin Nayak, Pulkit Sinha

CoRR, 2024

2023

Mutually Unbiased Measurements, Hadamard Matrices, and Superdense Coding.

Máté Farkas, Jedrzej Kaniewski, Ashwin Nayak

IEEE Trans. Inf. Theory, June, 2023

2022

Deterministic algorithms for the hidden subgroup problem.

Ashwin Nayak

Quantum Inf. Comput., 2022

2021

Capacity Approaching Coding for Low Noise Interactive Quantum Communication Part I: Large Alphabets.

Debbie W. Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu

IEEE Trans. Inf. Theory, 2021

One-Shot Quantum State Redistribution and Quantum Markov Chains.

Anurag Anshu, Shima Bab Hadiashar, Rahul Jain, Ashwin Nayak, Dave Touchette

Proceedings of the IEEE International Symposium on Information Theory, 2021

2020

On the Entanglement Cost of One-Shot Compression.

Shima Bab Hadiashar, Ashwin Nayak

Quantum, 2020

Quantum Distributed Complexity of Set Disjointness on a Line.

Frédéric Magniez, Ashwin Nayak

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2018

Communication Complexity of One-Shot Remote State Preparation.

Shima Bab Hadiashar, Ashwin Nayak, Renato Renner

IEEE Trans. Inf. Theory, 2018

Online Learning of Quantum States.

Scott Aaronson, Xinyi Chen, Elad Hazan, Ashwin Nayak

CoRR, 2018

Capacity approaching coding for low noise interactive quantum communication.

Debbie W. Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Online Learning of Quantum States.

Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, Ashwin Nayak

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017

Augmented Index and Quantum Streaming Algorithms for DYCK(2).

Ashwin Nayak, Dave Touchette

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Quantum Analogues of Markov Chains.

Ashwin Nayak, Peter C. Richter, Mario Szegedy

Encyclopedia of Algorithms, 2016

Quantum Algorithms for Matrix Multiplication and Product Verification.

Robin Kothari, Ashwin Nayak

Encyclopedia of Algorithms, 2016

Improved bounds for the randomized decision tree Complexity of recursive majority.

Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao

Random Struct. Algorithms, 2016

A search for quantum coin-flipping protocols using optimization techniques.

Ashwin Nayak, Jamie Sikora, Levent Tunçel

Math. Program., 2016

2015

Quantum and classical coin-flipping protocols based on bit-commitment and their point games.

Ashwin Nayak, Jamie Sikora, Levent Tunçel

CoRR, 2015

2014

The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited.

Rahul Jain, Ashwin Nayak

IEEE Trans. Inf. Theory, 2014

Noisy Interactive Quantum Communication.

Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, Falk Unger

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2012

Short Proofs of the Quantum Substate Theorem.

Rahul Jain, Ashwin Nayak

IEEE Trans. Inf. Theory, 2012

2011

A short proof of the Quantum Substate Theorem

Rahul Jain, Ashwin Nayak

CoRR, 2011

Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority.

Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Inverting a permutation is as hard as unordered search.

Ashwin Nayak

Electron. Colloquium Comput. Complex., 2010

The space complexity of recognizing well-parenthesized expressions.

Rahul Jain, Ashwin Nayak

Electron. Colloquium Comput. Complex., 2010

Recognizing well-parenthesized expressions in the streaming model.

Frédéric Magniez, Claire Mathieu, Ashwin Nayak

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2009

Special Section on Foundations of Computer Science.

Matthew Andrew, Ashwin Nayak, Rajmohan Rajaraman

SIAM J. Comput., 2009

Foreword from the Guest Editors.

Frédéric Magniez, Ashwin Nayak

Algorithmica, 2009

On the hitting times of quantum versus random walks.

Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Quantum Algorithm for Checking Matrix Identities.

Ashwin Nayak

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

A Separation between Divergence and Holevo Information for Ensembles.

Rahul Jain, Ashwin Nayak, Yi Su

Proceedings of the Theory and Applications of Models of Computation, 2008

Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract.

Rahul Jain, Hartmut Klauck, Ashwin Nayak

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

Interaction in Quantum Communication.

Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman

IEEE Trans. Inf. Theory, 2007

Invertible quantum operations and perfect encryption of quantum states.

Ashwin Nayak, Pranab Sen

Quantum Inf. Comput., 2007

Direct Product Theorems for Communication Complexity via Subdistribution Bounds.

Rahul Jain, Hartmut Klauck, Ashwin Nayak

Electron. Colloquium Comput. Complex., 2007

Search via quantum walk.

Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Limits on the ability of quantum states to convey classical messages.

Ashwin Nayak, Julia Salzman

J. ACM, 2006

2005

Quantum Complexity of Testing Group Commutativity.

Frédéric Magniez, Ashwin Nayak

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004

Weak coin flipping with small bias.

Iordanis Kerenidis, Ashwin Nayak

Inf. Process. Lett., 2004

2002

Dense quantum coding and quantum finite automata.

Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani

J. ACM, 2002

On Communication over an Entanglement-Assisted Quantum Channel.

Ashwin Nayak, Julia Salzman

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Interaction in quantum communication and the complexity of set disjointness.

Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

One-dimensional quantum walks.

Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000

Interaction in Quantum Communication Complexity

Ashwin Nayak, Amnon Ta-Shma, David Zuckerman

CoRR, 2000

1999

Spatial Codes and the Hardness of String Folding Problems.

Ashwin Nayak, Alistair Sinclair, Uri Zwick

J. Comput. Biol., 1999

The Quantum Query Complexity of Approximating the Median and Related Statistics.

Ashwin Nayak, Felix Wu

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata.

Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Optimal Lower Bounds for Quantum Automata and Random Access Codes.

Ashwin Nayak

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Spatial Codes and the Hardness of String Folding Problems (Extended Abstract).

Ashwin Nayak, Alistair Sinclair, Uri Zwick

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998