default search action
Ashwin Nayak 0001
Person information
- affiliation: University of Waterloo, Waterloo, ON, Canada
Other persons with the same name
- Ashwin Nayak 0002
— Stanford University, CA, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Journal Articles
- 2024
- [j27]Shima Bab Hadiashar
Optimal Lower Bounds for Quantum Learning via Information Theory. IEEE Trans. Inf. Theory 70(3): 1876-1896 (2024) - 2023
- [j26]Máté Farkas
Mutually Unbiased Measurements, Hadamard Matrices, and Superdense Coding. IEEE Trans. Inf. Theory 69(6): 3814-3824 (2023) - [j25]Anurag Anshu
One-Shot Quantum State Redistribution and Quantum Markov Chains. IEEE Trans. Inf. Theory 69(9): 5788-5804 (2023) - 2022
- [j24]Ashwin Nayak:
Deterministic algorithms for the hidden subgroup problem. Quantum Inf. Comput. 22(9&10): 755-769 (2022) - [j23]Frédéric Magniez
Quantum Distributed Complexity of Set Disjointness on a Line. ACM Trans. Comput. Theory 14(1): 5:1-5:22 (2022) - 2021
- [j22]Debbie W. Leung, Ashwin Nayak
Capacity Approaching Coding for Low Noise Interactive Quantum Communication Part I: Large Alphabets. IEEE Trans. Inf. Theory 67(8): 5443-5490 (2021) - 2020
- [j21]Shima Bab Hadiashar, Ashwin Nayak:
On the Entanglement Cost of One-Shot Compression. Quantum 4: 286 (2020) - 2019
- [j20]Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, Falk Unger:
Noisy Interactive Quantum Communication. SIAM J. Comput. 48(4): 1147-1195 (2019) - 2018
- [j19]Shima Bab Hadiashar
Communication Complexity of One-Shot Remote State Preparation. IEEE Trans. Inf. Theory 64(7): 4709-4728 (2018) - 2016
- [j18]Ashwin Nayak, Jamie Sikora
A search for quantum coin-flipping protocols using optimization techniques. Math. Program. 156(1-2): 581-613 (2016) - [j17]Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos
Improved bounds for the randomized decision tree Complexity of recursive majority. Random Struct. Algorithms 48(3): 612-638 (2016) - 2014
- [j16]Frédéric Magniez, Claire Mathieu, Ashwin Nayak:
Recognizing Well-Parenthesized Expressions in the Streaming Model. SIAM J. Comput. 43(6): 1880-1905 (2014) - [j15]Rahul Jain
The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited. IEEE Trans. Inf. Theory 60(10): 6646-6668 (2014) - 2012
- [j14]Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha:
On the Hitting Times of Quantum Versus Random Walks. Algorithmica 63(1-2): 91-116 (2012) - [j13]Rahul Jain
Short Proofs of the Quantum Substate Theorem. IEEE Trans. Inf. Theory 58(6): 3664-3669 (2012) - 2011
- [j12]Frédéric Magniez, Ashwin Nayak, Jérémie Roland
Search via Quantum Walk. SIAM J. Comput. 40(1): 142-164 (2011) - [j11]Ashwin Nayak:
Inverting a Permutation is as Hard as Unordered Search. Theory Comput. 7(1): 19-25 (2011) - 2010
- [j10]Rahul Jain
A separation between divergence and Holevo information for ensembles. Math. Struct. Comput. Sci. 20(5): 977-993 (2010) - 2009
- [j9]Frédéric Magniez, Ashwin Nayak:
Foreword from the Guest Editors. Algorithmica 55(3): 393-394 (2009) - [j8]Matthew Andrew, Ashwin Nayak, Rajmohan Rajaraman:
Special Section on Foundations of Computer Science. SIAM J. Comput. 39(2): 545 (2009) - 2007
- [j7]Frédéric Magniez, Ashwin Nayak:
Quantum Complexity of Testing Group Commutativity. Algorithmica 48(3): 221-232 (2007) - [j6]Ashwin Nayak, Pranab Sen:
Invertible quantum operations and perfect encryption of quantum states. Quantum Inf. Comput. 7(1): 103-110 (2007) - [j5]Hartmut Klauck
Interaction in Quantum Communication. IEEE Trans. Inf. Theory 53(6): 1970-1982 (2007) - 2006
- [j4]Ashwin Nayak, Julia Salzman:
Limits on the ability of quantum states to convey classical messages. J. ACM 53(1): 184-206 (2006) - 2004
- [j3]Iordanis Kerenidis, Ashwin Nayak:
Weak coin flipping with small bias. Inf. Process. Lett. 89(3): 131-135 (2004) - 2002
- [j2]Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma
Dense quantum coding and quantum finite automata. J. ACM 49(4): 496-511 (2002) - 1999
- [j1]Ashwin Nayak, Alistair Sinclair, Uri Zwick:
Spatial Codes and the Hardness of String Folding Problems. J. Comput. Biol. 6(1): 13-36 (1999)
Conference and Workshop Papers
- 2021
- [c21]Anurag Anshu, Shima Bab Hadiashar, Rahul Jain, Ashwin Nayak, Dave Touchette:
One-Shot Quantum State Redistribution and Quantum Markov Chains. ISIT 2021: 130-135 - 2020
- [c20]Frédéric Magniez
Quantum Distributed Complexity of Set Disjointness on a Line. ICALP 2020: 82:1-82:18 - 2018
- [c19]Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, Ashwin Nayak:
Online Learning of Quantum States. NeurIPS 2018: 8976-8986 - [c18]Debbie W. Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu
Capacity approaching coding for low noise interactive quantum communication. STOC 2018: 339-352 - 2017
- [c17]Ashwin Nayak, Dave Touchette:
Augmented Index and Quantum Streaming Algorithms for DYCK(2). CCC 2017: 23:1-23:21 - 2014
- [c16]Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, Falk Unger:
Noisy Interactive Quantum Communication. FOCS 2014: 296-305 - 2011
- [c15]Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao:
Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority. ICALP (1) 2011: 317-329 - 2010
- [c14]Frédéric Magniez, Claire Mathieu, Ashwin Nayak:
Recognizing well-parenthesized expressions in the streaming model. STOC 2010: 261-270 - 2009
- [c13]Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha:
On the hitting times of quantum versus random walks. SODA 2009: 86-95 - 2008
- [c12]Rahul Jain, Hartmut Klauck, Ashwin Nayak:
Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract. STOC 2008: 599-608 - [c11]Rahul Jain, Ashwin Nayak, Yi Su:
A Separation between Divergence and Holevo Information for Ensembles. TAMC 2008: 526-541 - 2007
- [c10]Frédéric Magniez, Ashwin Nayak, Jérémie Roland
Search via quantum walk. STOC 2007: 575-584 - 2005
- [c9]Frédéric Magniez, Ashwin Nayak:
Quantum Complexity of Testing Group Commutativity. ICALP 2005: 1312-1324 - 2002
- [c8]Ashwin Nayak, Julia Salzman:
On Communication over an Entanglement-Assisted Quantum Channel. CCC 2002: 19 - [c7]Ashwin Nayak, Julia Salzman:
On communication over an entanglement-assisted quantum channel. STOC 2002: 698-704 - 2001
- [c6]Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous:
One-dimensional quantum walks. STOC 2001: 37-49 - [c5]Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma
Interaction in quantum communication and the complexity of set disjointness. STOC 2001: 124-133 - 1999
- [c4]Ashwin Nayak:
Optimal Lower Bounds for Quantum Automata and Random Access Codes. FOCS 1999: 369-377 - [c3]Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma
Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. STOC 1999: 376-383 - [c2]Ashwin Nayak, Felix Wu:
The Quantum Query Complexity of Approximating the Median and Related Statistics. STOC 1999: 384-393 - 1998
- [c1]Ashwin Nayak, Alistair Sinclair, Uri Zwick:
Spatial Codes and the Hardness of String Folding Problems (Extended Abstract). SODA 1998: 639-648
Reference Works
- 2016
- [r3]Robin Kothari
Quantum Algorithms for Matrix Multiplication and Product Verification. Encyclopedia of Algorithms 2016: 1673-1677 - [r2]Ashwin Nayak, Peter C. Richter, Mario Szegedy:
Quantum Analogues of Markov Chains. Encyclopedia of Algorithms 2016: 1683-1691 - 2008
- [r1]Ashwin Nayak:
Quantum Algorithm for Checking Matrix Identities. Encyclopedia of Algorithms 2008
Informal and Other Publications
- 2024
- [i30]Ashwin Nayak, Pulkit Sinha:
Proper vs Improper Quantum PAC learning. CoRR abs/2403.03295 (2024) - 2023
- [i29]Shima Bab Hadiashar, Ashwin Nayak, Pulkit Sinha:
Optimal lower bounds for Quantum Learning via Information Theory. CoRR abs/2301.02227 (2023) - 2022
- [i28]Máté Farkas, Jedrzej Kaniewski, Ashwin Nayak:
Mutually Unbiased Measurements, Hadamard Matrices, and Superdense Coding. CoRR abs/2204.11886 (2022) - [i27]Angus Lowe, Ashwin Nayak:
Lower bounds for learning quantum states with single-copy measurements. CoRR abs/2207.14438 (2022) - 2021
- [i26]Anurag Anshu, Shima Bab Hadiashar, Rahul Jain, Ashwin Nayak, Dave Touchette:
One-shot quantum state redistribution and quantum Markov chains. CoRR abs/2104.08753 (2021) - [i25]Ashwin Nayak:
Deterministic Algorithms for the Hidden Subgroup Problem. CoRR abs/2104.14436 (2021) - 2020
- [i24]Debbie W. Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu:
Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets. CoRR abs/2001.02818 (2020) - [i23]Frédéric Magniez, Ashwin Nayak:
Quantum Distributed Complexity of Set Disjointness on a Line. CoRR abs/2002.11795 (2020) - 2019
- [i22]Shima Bab Hadiashar, Ashwin Nayak:
On the Entanglement Cost of One-Shot Compression. CoRR abs/1905.02110 (2019) - 2018
- [i21]Shima Bab Hadiashar, Ashwin Nayak, Renato Renner:
Communication Complexity of One-Shot Remote State Preparation. CoRR abs/1802.07795 (2018) - [i20]Scott Aaronson, Xinyi Chen, Elad Hazan, Ashwin Nayak:
Online Learning of Quantum States. CoRR abs/1802.09025 (2018) - 2016
- [i19]Ashwin Nayak, Dave Touchette:
Augmented Index and Quantum Streaming Algorithms for DYCK(2). CoRR abs/1610.04937 (2016) - 2015
- [i18]Ashwin Nayak, Jamie Sikora, Levent Tunçel:
Quantum and classical coin-flipping protocols based on bit-commitment and their point games. CoRR abs/1504.04217 (2015) - 2014
- [i17]Ashwin Nayak, Jamie Sikora, Levent Tunçel:
A search for quantum coin-flipping protocols using optimization techniques. CoRR abs/1403.0505 (2014) - 2013
- [i16]Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao:
Improved bounds for the randomized decision tree complexity of recursive majority. CoRR abs/1309.7565 (2013) - 2011
- [i15]Rahul Jain, Ashwin Nayak:
A short proof of the Quantum Substate Theorem. CoRR abs/1103.6067 (2011) - 2010
- [i14]Rahul Jain, Ashwin Nayak:
The space complexity of recognizing well-parenthesized expressions. CoRR abs/1004.3165 (2010) - [i13]Ashwin Nayak:
Inverting a permutation is as hard as unordered search. CoRR abs/1007.2899 (2010) - [i12]Rahul Jain, Ashwin Nayak:
The space complexity of recognizing well-parenthesized expressions. Electron. Colloquium Comput. Complex. TR10 (2010) - [i11]Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao:
Improved bounds for the randomized decision tree complexity of recursive majority. Electron. Colloquium Comput. Complex. TR10 (2010) - [i10]Ashwin Nayak:
Inverting a permutation is as hard as unordered search. Electron. Colloquium Comput. Complex. TR10 (2010) - 2009
- [i9]Frédéric Magniez, Claire Mathieu, Ashwin Nayak:
Recognizing well-parenthesized expressions in the streaming model. CoRR abs/0911.3291 (2009) - [i8]Frédéric Magniez, Claire Mathieu, Ashwin Nayak:
Recognizing well-parenthesized expressions in the streaming model. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [i7]Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha:
On the hitting times of quantum versus random walks. CoRR abs/0808.0084 (2008) - 2007
- [i6]Rahul Jain, Hartmut Klauck, Ashwin Nayak:
Direct Product Theorems for Communication Complexity via Subdistribution Bounds. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [i5]Frédéric Magniez, Ashwin Nayak, Jérémie Roland
Search via Quantum Walk. CoRR abs/quant-ph/0608026 (2006) - 2000
- [i4]Ashwin Nayak, Amnon Ta-Shma, David Zuckerman:
Interaction in Quantum Communication Complexity. CoRR quant-ph/0005106 (2000) - 1999
- [i3]Ashwin Nayak:
Optimal lower bounds for quantum automata and random access codes. CoRR quant-ph/9904093 (1999) - 1998
- [i2]Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani:
Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata. CoRR quant-ph/9804043 (1998) - [i1]Ashwin Nayak, Felix Wu:
The quantum query complexity of approximating the median and related statistics. CoRR quant-ph/9804066 (1998)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-08 20:36 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: