Ashwin Nayak

Publication Activity (10 Years)

Years Active: 1998-2023
Publications (10 Years): 28

Top Topics

Diagnostic Reasoning

Medical Records

Top Venues

IEEE Trans. Inf. Theory

SIAM J. Comput.

Publications

Máté Farkas, Jedrzej Kaniewski, Ashwin Nayak
Mutually Unbiased Measurements, Hadamard Matrices, and Superdense Coding. IEEE Trans. Inf. Theory 69 (6) (2023)
Thomas Savage, Ashwin Nayak, Robert Gallo, Ekanath Rangan, Jonathan H. Chen
Diagnostic Reasoning Prompts Reveal the Potential for Large Language Model Interpretability in Medicine. CoRR (2023)
Anurag Anshu, Shima Bab Hadiashar, Rahul Jain, Ashwin Nayak, Dave Touchette
One-Shot Quantum State Redistribution and Quantum Markov Chains. IEEE Trans. Inf. Theory 69 (9) (2023)
Shima Bab Hadiashar, Ashwin Nayak, Pulkit Sinha
Optimal lower bounds for Quantum Learning via Information Theory. CoRR (2023)
Scott L. Fleming, Alejandro Lozano, William J. Haberkorn, Jenelle A. Jindal, Eduardo P. Reis, Rahul Thapa, Louis Blankemeier, Julian Z. Genkins, Ethan Steinberg, Ashwin Nayak, Birju S. Patel, Chia-Chun Chiang, Alison Callahan, Zepeng Huo, Sergios Gatidis, Scott J. Adams, Oluseyi Fayanju, Shreya J. Shah, Thomas Savage, Ethan Goh, Akshay S. Chaudhari, Nima Aghaeepour, Christopher D. Sharp, Michael A. Pfeffer, Percy Liang, Jonathan H. Chen, Keith E. Morse, Emma P. Brunskill, Jason A. Fries, Nigam H. Shah
MedAlign: A Clinician-Generated Dataset for Instruction Following with Electronic Medical Records. CoRR (2023)
Ashwin Nayak
Deterministic algorithms for the hidden subgroup problem. Quantum Inf. Comput. 22 (9&10) (2022)
Angus Lowe, Ashwin Nayak
Lower bounds for learning quantum states with single-copy measurements. CoRR (2022)
Frédéric Magniez, Ashwin Nayak
Quantum Distributed Complexity of Set Disjointness on a Line. ACM Trans. Comput. Theory 14 (1) (2022)
Máté Farkas, Jedrzej Kaniewski, Ashwin Nayak
Mutually Unbiased Measurements, Hadamard Matrices, and Superdense Coding. CoRR (2022)
Anurag Anshu, Shima Bab Hadiashar, Rahul Jain, Ashwin Nayak, Dave Touchette
One-shot quantum state redistribution and quantum Markov chains. CoRR (2021)
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. IEEE Trans. Inf. Theory 67 (8) (2021)
Anurag Anshu, Shima Bab Hadiashar, Rahul Jain, Ashwin Nayak, Dave Touchette
One-Shot Quantum State Redistribution and Quantum Markov Chains. ISIT (2021)
Ashwin Nayak
Deterministic Algorithms for the Hidden Subgroup Problem. CoRR (2021)
Shima Bab Hadiashar, Ashwin Nayak
On the Entanglement Cost of One-Shot Compression. Quantum 4 (2020)
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 (2020)
Frédéric Magniez, Ashwin Nayak
Quantum Distributed Complexity of Set Disjointness on a Line. ICALP (2020)
Frédéric Magniez, Ashwin Nayak
Quantum Distributed Complexity of Set Disjointness on a Line. CoRR (2020)
Shima Bab Hadiashar, Ashwin Nayak
On the Entanglement Cost of One-Shot Compression. CoRR (2019)
Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, Falk Unger
Noisy Interactive Quantum Communication. SIAM J. Comput. 48 (4) (2019)
Shima Bab Hadiashar, Ashwin Nayak, Renato Renner
Communication Complexity of One-Shot Remote State Preparation. IEEE Trans. Inf. Theory 64 (7) (2018)
Shima Bab Hadiashar, Ashwin Nayak, Renato Renner
Communication Complexity of One-Shot Remote State Preparation. CoRR (2018)
Scott Aaronson, Xinyi Chen, Elad Hazan, Ashwin Nayak
Online Learning of Quantum States. CoRR (2018)
Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, Ashwin Nayak
Online Learning of Quantum States. NeurIPS (2018)
Debbie W. Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu
Capacity approaching coding for low noise interactive quantum communication. STOC (2018)
Ashwin Nayak, Dave Touchette
Augmented Index and Quantum Streaming Algorithms for DYCK(2). Computational Complexity Conference (2017)
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. Random Struct. Algorithms 48 (3) (2016)
Ashwin Nayak, Jamie Sikora, Levent Tunçel
A search for quantum coin-flipping protocols using optimization techniques. Math. Program. 156 (1-2) (2016)
Ashwin Nayak, Dave Touchette
Augmented Index and Quantum Streaming Algorithms for DYCK(2). CoRR (2016)
Ashwin Nayak, Jamie Sikora, Levent Tunçel
Quantum and classical coin-flipping protocols based on bit-commitment and their point games. CoRR (2015)
Frédéric Magniez, Claire Mathieu, Ashwin Nayak
Recognizing Well-Parenthesized Expressions in the Streaming Model. SIAM J. Comput. 43 (6) (2014)
Rahul Jain, Ashwin Nayak
The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited. IEEE Trans. Inf. Theory 60 (10) (2014)
Ashwin Nayak, Jamie Sikora, Levent Tunçel
A search for quantum coin-flipping protocols using optimization techniques. CoRR (2014)
Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, Falk Unger
Noisy Interactive Quantum Communication. FOCS (2014)
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 (2013)
Rahul Jain, Ashwin Nayak
Short Proofs of the Quantum Substate Theorem. IEEE Trans. Inf. Theory 58 (6) (2012)
Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha
On the Hitting Times of Quantum Versus Random Walks. Algorithmica 63 (1-2) (2012)
Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao
Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority. ICALP (1) (2011)
Rahul Jain, Ashwin Nayak
A short proof of the Quantum Substate Theorem CoRR (2011)
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha
Search via Quantum Walk. SIAM J. Comput. 40 (1) (2011)
Ashwin Nayak
Inverting a Permutation is as Hard as Unordered Search. Theory Comput. 7 (1) (2011)
Rahul Jain, Ashwin Nayak, Yi Su
A separation between divergence and Holevo information for ensembles. Math. Struct. Comput. Sci. 20 (5) (2010)
Rahul Jain, Ashwin Nayak
The space complexity of recognizing well-parenthesized expressions CoRR (2010)
Ashwin Nayak
Inverting a permutation is as hard as unordered search CoRR (2010)
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. 17 (2010)
Frédéric Magniez, Claire Mathieu, Ashwin Nayak
Recognizing well-parenthesized expressions in the streaming model. STOC (2010)
Ashwin Nayak
Inverting a permutation is as hard as unordered search. Electron. Colloquium Comput. Complex. 17 (2010)
Rahul Jain, Ashwin Nayak
The space complexity of recognizing well-parenthesized expressions. Electron. Colloquium Comput. Complex. 17 (2010)
Frédéric Magniez, Claire Mathieu, Ashwin Nayak
Recognizing well-parenthesized expressions in the streaming model CoRR (2009)
Frédéric Magniez, Claire Mathieu, Ashwin Nayak
Recognizing well-parenthesized expressions in the streaming model. Electron. Colloquium Comput. Complex. 16 (2009)
Matthew Andrew, Ashwin Nayak, Rajmohan Rajaraman
Special Section on Foundations of Computer Science. SIAM J. Comput. 39 (2) (2009)
Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha
On the hitting times of quantum versus random walks. SODA (2009)
Frédéric Magniez, Ashwin Nayak
Foreword from the Guest Editors. Algorithmica 55 (3) (2009)
Rahul Jain, Hartmut Klauck, Ashwin Nayak
Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract. STOC (2008)
Rahul Jain, Ashwin Nayak, Yi Su
A Separation between Divergence and Holevo Information for Ensembles. TAMC (2008)
Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha
On the hitting times of quantum versus random walks. CoRR (2008)
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha
Search via quantum walk. STOC (2007)
Frédéric Magniez, Ashwin Nayak
Quantum Complexity of Testing Group Commutativity. Algorithmica 48 (3) (2007)
Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
Interaction in Quantum Communication. IEEE Trans. Inf. Theory 53 (6) (2007)
Rahul Jain, Hartmut Klauck, Ashwin Nayak
Direct Product Theorems for Communication Complexity via Subdistribution Bounds. Electron. Colloquium Comput. Complex. 14 (064) (2007)
Ashwin Nayak, Pranab Sen
Invertible quantum operations and perfect encryption of quantum states. Quantum Inf. Comput. 7 (1) (2007)
Ashwin Nayak, Julia Salzman
Limits on the ability of quantum states to convey classical messages. J. ACM 53 (1) (2006)
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha
Search via Quantum Walk. CoRR (2006)
Frédéric Magniez, Ashwin Nayak
Quantum Complexity of Testing Group Commutativity. ICALP (2005)
Iordanis Kerenidis, Ashwin Nayak
Weak coin flipping with small bias. Inf. Process. Lett. 89 (3) (2004)
Ashwin Nayak, Julia Salzman
On communication over an entanglement-assisted quantum channel. STOC (2002)
Ashwin Nayak, Julia Salzman
On Communication over an Entanglement-Assisted Quantum Channel. Computational Complexity Conference (2002)
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
Dense quantum coding and quantum finite automata. J. ACM 49 (4) (2002)
Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
Interaction in quantum communication and the complexity of set disjointness. STOC (2001)
Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous
One-dimensional quantum walks. STOC (2001)
Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
Interaction in Quantum Communication Complexity CoRR (2000)
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. STOC (1999)
Ashwin Nayak, Alistair Sinclair, Uri Zwick
Spatial Codes and the Hardness of String Folding Problems. J. Comput. Biol. 6 (1) (1999)
Ashwin Nayak
Optimal Lower Bounds for Quantum Automata and Random Access Codes. FOCS (1999)
Ashwin Nayak, Felix Wu
The Quantum Query Complexity of Approximating the Median and Related Statistics. STOC (1999)
Ashwin Nayak
Optimal lower bounds for quantum automata and random access codes CoRR (1999)
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata CoRR (1998)
Ashwin Nayak, Alistair Sinclair, Uri Zwick
Spatial Codes and the Hardness of String Folding Problems (Extended Abstract). SODA (1998)
Ashwin Nayak, Felix Wu
The quantum query complexity of approximating the median and related statistics CoRR (1998)