Ashwin Nayak

According to our database1, Ashwin Nayak authored at least 43 papers between 1998 and 2020.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

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

2019
Noisy Interactive Quantum Communication.
SIAM J. Comput., 2019

On the Entanglement Cost of One-Shot Compression.
CoRR, 2019

2018
Communication Complexity of One-Shot Remote State Preparation.
IEEE Trans. Information Theory, 2018

Online Learning of Quantum States.
CoRR, 2018

Capacity approaching coding for low noise interactive quantum communication.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Online Learning of Quantum States.
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).
Proceedings of the 32nd Computational Complexity Conference, 2017

2016
Quantum Analogues of Markov Chains.
Encyclopedia of Algorithms, 2016

Quantum Algorithms for Matrix Multiplication and Product Verification.
Encyclopedia of Algorithms, 2016

Improved bounds for the randomized decision tree Complexity of recursive majority.
Random Struct. Algorithms, 2016

A search for quantum coin-flipping protocols using optimization techniques.
Math. Program., 2016

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

2014
The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited.
IEEE Trans. Information Theory, 2014

2012
Short Proofs of the Quantum Substate Theorem.
IEEE Trans. Information Theory, 2012

On the Hitting Times of Quantum Versus Random Walks.
Algorithmica, 2012

2011
Inverting a Permutation is as Hard as Unordered Search.
Theory of Computing, 2011

Search via Quantum Walk.
SIAM J. Comput., 2011

A short proof of the Quantum Substate Theorem
CoRR, 2011

2010
A separation between divergence and Holevo information for ensembles.
Mathematical Structures in Computer Science, 2010

Improved bounds for the randomized decision tree complexity of recursive majority.
Electronic Colloquium on Computational Complexity (ECCC), 2010

The space complexity of recognizing well-parenthesized expressions.
Electronic Colloquium on Computational Complexity (ECCC), 2010

2009
Special Section on Foundations of Computer Science.
SIAM J. Comput., 2009

Recognizing well-parenthesized expressions in the streaming model.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Foreword from the Guest Editors.
Algorithmica, 2009

2008
Quantum Algorithm for Checking Matrix Identities.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007
Interaction in Quantum Communication.
IEEE Trans. Information Theory, 2007

Invertible quantum operations and perfect encryption of quantum states.
Quantum Information & Computation, 2007

Direct Product Theorems for Communication Complexity via Subdistribution Bounds.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Quantum Complexity of Testing Group Commutativity.
Algorithmica, 2007

2006
Limits on the ability of quantum states to convey classical messages.
J. ACM, 2006

2004
Weak coin flipping with small bias.
Inf. Process. Lett., 2004

2002
Dense quantum coding and quantum finite automata.
J. ACM, 2002

On communication over an entanglement-assisted quantum channel.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001
Interaction in quantum communication and the complexity of set disjointness.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

One-dimensional quantum walks.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000
Interaction in Quantum Communication Complexity
CoRR, 2000

1999
Spatial Codes and the Hardness of String Folding Problems.
Journal of Computational Biology, 1999

The Quantum Query Complexity of Approximating the Median and Related Statistics.
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.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Optimal Lower Bounds for Quantum Automata and Random Access Codes.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Spatial Codes and the Hardness of String Folding Problems (Extended Abstract).
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998


  Loading...