# Ashwin Nayak

According to our database

Collaborative distances:

^{1}, 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