| Kang-Da Wu, Chengran Yang, Ren-Dong He, M. Gu, Guo-Yong Xiang, Chuan-Feng Li, Guang-Can Guo, Thomas J. Elliott (2023). Implementing quantum dimensionality reduction for non-Markovian stochastic simulation. Nature Communications 14 2624 |
 |
| J. Jirawat Tangpanitanon, J. Tangpanitanon, S. Thanasilp, Marc-Antoine Lemonde, Ninnat Dangniam, D.G. Angelakis (2023). Signatures of a sampling quantum advantage in driven quantum many-body systems. Quantum Science and Technology 8 025019 |
|
| W.Y Suen, Thomas J. Elliott, Jayne Thompson, Andrew J. P. Garner, John R. Mahoney, Vlatko Vedral, M. Gu (2022). Surveying structural complexity in quantum many-body systems. Journal of Statistical Physics 187 1-18 |
|
| T. Lee, Swagato Sanyal, M. Santha, T. Lee, D. Gavinsky (2022). A composition theorem for randomized query complexity via max conflict complexity. Theory of Computing 18 |
|
| S.Kundu, Shalev Ben-David, Anurag Anshu (2021). On Query-to-Communication Lifting for Adversary Bounds. Proceedings of the Computational Complexity Conference |
|
| S.Kundu, R. Jain (2021). A direct product theorem for quantum communication complexity with applications to device-independent QKD. Proc. IEEE FOCS |
|
| S.Kundu, R. Jain (2021). A Direct Product Theorem for One-Way Quantum Communication. Proceedings of the Computational Complexity Conference |
|
| Yu Baichu, P.Jayachandran, Adam Burchardt, Yu Cai, Nicolas Brunner, V. Scarani (2021). Absolutely entangled sets of pure states for bipartitions and multipartitions. Phys. Rev. A 104 032414 |
|
| S. Thanasilp, J. Jirawat Tangpanitanon, J. Tangpanitanon, Marc-Antoine Lemonde, Ninnat Dangniam, D.G. Angelakis (2021). Quantum supremacy and quantum phase transitions. Phys. Rev. B 103 165132 |
|
| Noah Heskel Sklaire Stephens-Davidowitz, Joao Ribeiro, D. Aggarwal, Siyao Guo, Maciej Lukasz Obremski (2020). Extractor Lower Bounds, Revisited. RANDOM |
|
| D. Gavinsky (2020). Bare quantum simultaneity versus classical interactivity in communication complexity. ACM STOC |
|
| D. Gavinsky (2020). Entangled simultaneity versus classical interactivity in communication complexity. IEEE Trans. Inf. |
|
| J. Jirawat Tangpanitanon, J. Tangpanitanon, S. Thanasilp, Ninnat Dangniam, Marc-Antoine Lemonde, D.G. Angelakis (2020). Expressibility and trainability of parameterized analog quantum systems for machine learning applications. Physical Review Research 2 043364 |
|
| D. Gavinsky (2019). Quantum versus classical simultaneity in communication complexity. IEEE Trans. Inf. 10 6466-6483 |
|
| Francesco Petruccione, Leonard Wossnig, Maria Schuld, R.Patrick, Seth Lloyd (2019). Quantum gradient descent and Newton\'s method for constrained polynomial optimization. New J. Phys. |
|
| Youming Qiao, Gábor Ivanyos (2019). Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing. SIAM Journal of Computing |
|
| Lajos Rónyai, Péter Kutas, Gábor Ivanyos (2019). Explicit equivalence of quadratic forms over $\\\\mathbb{F}_q(t)$. Finite Fields and Their Applications |
|
| Ansis Rosmanis, Harumichi Nishimura, François Le Gall (2019). Quantum Advantage for the LOCAL Model in Distributed Computing. Proceedings of STACS |
|
| Farrokh Labib, Harry Buhrman, Jop Briët, Tom Bannink, T. Lee, T. Lee (2019). Bounding quantum-classical separations for classes of nonlocal games. Proceedings of STACS |
|
| Netanel H. Lindner, I. Arad, Eyal Bairey (2019). Learning a local Hamiltonian from local measurements. Phys. Rev. Lett. |
|
| N.G. Boddu, Dave Touchette, Anurag Anshu (2019). Quantum Log-Approximate-Rank Conjecture is also False. Proc. IEEE FOCS |
|
| Joao Ribeiro, Jesper Buus Nielsen, Ivan Damgard, D. Aggarwal, Maciej Lukasz Obremski, E. Purwanto, Mark Simkin (2019). Stronger Leakage-Resilient and Non-Malleable Secret-Sharing Schemes for General Access Structures. Proceedings of CRYPTO |
|
| M.Ray, T. Lee, M. Santha, T. Lee (2019). Strategies for quantum races. ITCS 14 |
|
| Gábor Ivanyos, Péter Kutas, Lajos Rónyai (2019). Explicit equivalence of quadratic forms over $\\mathbb{F}_q(t)$. Finite Fields and Their Applications 55 33-63 |
|
| M. Santha, Youming Qiao, Raghav Kulkarni, Gábor Ivanyos, Aarthi Sundaram (2018). On the Complexity of Trial and Error for Constraint Satisfaction Problems. Journal of Computer and System Sciences 92 48-64 |
|
| Ansis Rosmanis, Aleksandrs Belovs (2018). Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems. TQCCC |
|
| M. Santha, T. Lee, Gavin K. Brennen, D. Aggarwal, T. Lee, M. Tomamichel (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger 3 |
|
| Aarthi Sundaram, Jamie Sikora, M. Santha, Sevag Gharibian, Justin Yirka (2018). Quantum generalizations of the polynomial hierarchy with applications to QMA(2). International Symposium MFCS 1-16 |
|
| Lajos Rónyai, Péter Kutas, Gábor Ivanyos (2018). Computing explicit isomorphisms with full matrix algebras over $\mathbb{F}_q(x)$. Foundations of Computational Mathematics 18 381-397 |
|
| D. Aggarwal, N. Stephens-Davidowitz (2018). (Gap/S)ETH Hardness of SVP. ACM STOC |
|
| G. Ivanyos, Marek Karpinski, M. Santha, Nitin Saxena, Igor Shparlinski (2018). Polynomial Interpolation and Identity Testing from High Powers over Finite Fields. Algorithmica 80 560-575 |
|
| M. Santha, T. Lee, Gavin K. Brennen, D. Aggarwal, T. Lee, M. Tomamichel (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger |
|
| I. Arad, M. Santha, Aarthi Sundaram, Shengyu Zhang (2018). Linear time algorithm for quantum 2SAT. Theory of Computing 1-27 |
|
| G. Ivanyos, Y. Qiao (2018). Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing. ACM SIAM SODA 2357-2376 |
|
| J. Thompson, A.Garner, John R. Mahoney, James P. Crutchfield, V. Vedral, M. Gu (2018). Causal Asymmetry in a Quantum World. Phys. Rev. X 8 031013 |
|
| Youming Qiao, G. Ivanyos (2018). Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing. Symposium on Discrete Algorithms 2357-2376 |
|
| K.T. Goh, J. Kaniewski, Elie Wolfe, Tamas Vertesi, X. Wu, Y. Cai, Yeong-Cherng Liang, V. Scarani (2018). Geometry of the quantum set of correlations. Phys. Rev. A 97 022104 |
|
| G. Ivanyos, Péter Kutas, Lajos Rónyai (2018). Computing explicit isomorphisms with full matrix algebras over $\\mathbb{F}_q(x)$. Foundations of Computational Mathematics |
|
| G. Ivanyos, Youming Qiao, K. V. Subrahmanyam (2018). Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristics. Computational Complexity |
|
| Mika Goos, R. Jain, Thomas Watson (2018). Extension Complexity of Independent Set Polytopes. SIAM Journal of Computing 47 241–269 |
|
| Kaspars Balodis, M. Santha, Juris Smotrovs, T. Lee, T. Lee, Aleksandrs Belovs, Andris Ambainis (2017). Separations in Query Complexity Based on Pointer Functions. JACM 64 |
|
| D. Aggarwal, M. Obremski, T. Kazana (2017). Inception makes non-malleable codes stronger. Theory of Cryptography |
|
| Mark Bradshaw, Syed M. Assad, Jing Yan Haw, S. Tan, Ping Koy Lam, M. Gu (2017). Overarching framework between Gaussian quantum discord and Gaussian quantum illumination. Phys. Rev. A 95 022333 |
|
| G. Ivanyos, Youming Qiao, K. V. Subrahmanyam (2017). On generating the ring of matrix semi-invariants. Computational Complexity 26 717-763 |
|
| D. Gavinsky, R. Jain, H. Klauck, S.Kundu, T. Lee, T. Lee, M. Santha, S. Sanyal, Jevgenijs Vihrovs (2017). Quadratically Tight Relations for Randomized Query Complexity. CSR |
|
| M. Santha, Y. Qiao, G. Ivanyos, A. Belovs, S.Yang (2017). On the Polynomial Parity Argument complexity of the Combinatorial Nullstellensatz. Proceedings of the Computational Complexity Conference 30 |
|
| A. Anshu, A. Anshu, D. Gavinsky, R. Jain, S.Kundu, T. Lee, T. Lee, P. Mukhopadhyay, M. Santha, S. Sanyal (2017). A Composition Theorem for Randomized Query Complexity. FSTTCS |
|
| S. Nimmrichter, J. Dai, A.Roulet, V. Scarani (2017). Quantum and classical dynamics of a three-mode absorption refrigerator. Quantum 1 37 |
|
| W.Y Suen, J. Thompson, A.Garner, V. Vedral, M. Gu (2017). The classical-quantum divergence of complexity in modelling spin chains. Quantum 1 25 |
|
| A. Anshu, A. Anshu, V. Krishna, R. Jain (2017). Quantum Communication Using Coherent Rejection Sampling. Phys. Rev. Lett. 119 120506 |
|
| A. Anshu, A. Anshu, Shalev Ben-David, Ankit Garg, R. Jain, Robin Kothari, T. Lee, T. Lee (2017). Separating quantum communication and approximate rank. Proc. IEEE CCC |
|
| G. Ivanyos, M. Santha (2017). On solving systems of diagonal polynomial equations over finite fields. Theoretical Computer Science 657 73-85 |
|
| T. Lee, T. Lee, Z.H. Wei, Ronald de Wolf (2017). Some upper and lower bounds on PSD-rank. Mathematical Programming 162 495--521 |
|
| A. Shu, J. Dai, V. Scarani (2017). The power of an optical Maxwell demon. Phys. Rev. A 95 022123 |
|
| R. Jain, Z.H. Wei, Penghui Yao, S. Zhang (2017). Multipartite Quantum Correlation and Communication Complexities. Computational Complexity 26 199--228 |
|
| A. Anshu, A. Anshu, R. Jain, P. Mukhopadhyay, Ala Shayeghi, P. Yao (2016). New One Shot Quantum Protocols With Application to Communication Complexity. IEEE Trans. Inf. 62 7566 - 757 |
|
| Prahladh Harsha, R. Jain, Jaikumar Radhakrishnan (2016). Partition bound is quadratically tight for product distributions. Proceedings of ICALP |
|
| Frederic Magniez, Ashwin Nayak, M. Santha, Jonah Sherman, G. Ivanyos, David Xiao (2016). Improved bounds for the randomized decision tree complexity of recursive majority. Random Structures and Algorithms 48 612-638 |
|
| Gabor Braun, R. Jain, T. Lee, T. Lee, Sebastian Pokutta (2016). Information-theoretic approximations of the nonnegative rank. Computational Complexity 26 147–197 |
|
| A. Anshu, A. Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Goos, R. Jain, Robin Kothari, T. Lee, T. Lee, M. Santha (2016). Separations in communication complexity using cheat sheets and information complexity. Proc. IEEE FOCS 555-564 |
|
| Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, T. Lee, T. Lee, M. Santha, Juris Smotrovs (2016). Separation in query complexity based on pointer functions. Proceedings of ACM STOC 800-813 |
|
| H.S. Poh, Marcin Markiewicz, Pawel Kurzynski, A. Cere, D. Kaszlikowski, C. Kurtsiefer (2016). Probing the quantum-classical boundary with compression software. New J. Phys. 18 035011 |
|
| D. Gavinsky (2016). Entangled simultaneity versus classical interactivity in communication complexity. Proceedings of ACM STOC |
|
| R. Jain (2016). New strong direct product results in communication complexity. JACM 62 |
|
| Xiao Yuan, Syed M. Assad, J. Thompson, Jing Yan Haw, V. Vedral, Timothy C. Ralph, Ping Koy Lam, Christian Weedbrook, M. Gu (2015). Replicating the benefits of closed timelike curves without breaking causality. NPJ: Quantum Information 1 15007 |
|
| Robin Kothari, DR.Desloges, M. Santha (2015). Separating decision tree complexity from subcube partition complexity. Proceedings of International Workshop on Randomization and Computation 915-930 |
|
| Ralph C. Bottesch, D. Gavinsky, H. Klauck (2015). Equality, Revisited. International Symposium MFCS 2 127-138 |
|
| Y. Cai, Le Huy Nguyen, V. Scarani (2015). State complexity and quantum computation. Ann. Phys. 527 684 |
|
| M. Santha (2015). Quantum and randomized query complexities. International Conference on Theory and Applications of Models of Computation 18-19 |
|
| Ralph C. Bottesch, D. Gavinsky, H. Klauck (2015). Correlation in Hard Distributions in Communication Complexity. RANDOM 544-572 |
|
| Christopher Perry, R. Jain, J. Oppenheim (2015). Communication tasks with infinite quantum-classical separation. Phys. Rev. Lett. 115 030504 |
|
| Lila Fontes, R. Jain, I. Kerenidis, Sophie Laplante, Mathieu Laurier, Jeremie Roland (2015). Relative discrepancy does not separate information and communication complexity. Proceedings of ICALP |
|
| Anna Pappa, Niraj Kumar, Thomas Lawson, M. Santha, S. Zhang, Eleni Diamanti, I. Kerenidis (2015). Nonlocality and conflicting interest games. Phys. Rev. Lett. 020401 |
|
| H. Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson (2015). Distributed Computation of Large-scale Graph Problems. ACM SIAM SODA 391-410 |
|
| H. Klauck, S. Podder (2014). New Bounds for the Garden-Hose Model . Proceedings of FSTTCS |
|
| Katalin Friedl, G. Ivanyos, Frederic Magniez, M. Santha, Pranab Sen (2014). Hidden Translation and Translating Coset in Quantum Computing. SIAM Journal of Computing 43 1-24 |
|
| T. Decker, P. Hoyer, G. Ivanyos, M. Santha (2014). Polynomial time quantum algorithms for certain bivariate hidden polynomial problems. Quantum Information and Computation 14 790–806 |
|
| Le Huy Nguyen, Y. Cai, X. Wu, Rafael Rabelo, V. Scarani (2014). Maximal tree size of few-qubit states. Phys. Rev. A 89 062333 |
|
| Nathanael Francois, R. Jain, Frederic Magniez (2014). Input/Output Streaming Complexity of Reversal and Sorting. RANDOM 654-668 |
|
| R. Jain, A. Pereszlenyi, P. Yao (2014). A parallel repetition theorem for entangled two-player one-round games under product distributions. Proc. IEEE CCC 209-216 |
|
| A. Nayak, R. Jain (2014). The space complexity of recognizing well-parenthesized expressions in the streaming model: the Index function revisited. IEEE Trans. Inf. 60 1-23 |
|
| T. Decker, G. Ivanyos, R. Kulkarni, Y. Qiao, M. Santha (2014). An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group. International Symposium MFCS 226-238 |
|
| G. Ivanyos, R. Kulkarni, Y. Qiao, M. Santha, A. Sundaram (2014). On the complexity of trial and error for constraint satisfaction problems. Proceedings of ICALP 663-675 |
|
| Joshua A. Grochow, Y. Qiao (2014). Algorithms for group isomorphism via group extensions and cohomology. IEEE Conference on Computational Complexity |
|
| G. Ivanyos, Marek Karpinski, Y. Qiao, M. Santha (2014). Generalized Wong sequences and their applications to Edmonds. Proceedings of STACS 25 397-408 |
|
| L. Mancinska, T. Vidick (2014). Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability. LNCS 8572 835-846 |
|
| Honghao Fu, Debbie Leung, L. Mancinska (2014). When the asymptotic limit offers no advantage in the local-operations-and-classical-communication paradigm. Phys. Rev. A 89 052310 |
|
| Julien Barre, Bruno Marcos, D. Wilkowski (2014). Nonequilibrium Phase Transition with Gravitational-like Interaction in a Cloud of Cold Atoms. Phys. Rev. Lett. 112 133001 |
|
| H. Klauck, S. Podder (2014). Two Results about Quantum Messages. International Symposium MFCS |
|
| Michael Elkin, H. Klauck, Danupon Nanongkai, Gopal Pandurangan (2014). Can Quantum Communication Speed Up Distributed Computation?. ACM Symposium PODC |
|
| H. Klauck, V. Prakash (2014). An Improved Interactive Streaming Algorithm for the Distinct Elements Problem. Proceedings of ICALP 928-939 |
|
| R. Kulkarni, M. Santha (2013). Query complexity of matroids. CIAC 300-311 |
|
| R. Jain, Yaoyun Shi, Z.H. Wei, S. Zhang (2013). Efficient protocols for generating bipartite classical distributions and quantum states. IEEE Trans. Inf. 59 5171-5178 |
|
| Prahladh Harsha, R. Jain (2013). A strong direct product theorem for the tribes function via the smooth-rectangle bound. Proceedings of FSTTCS 141-152 |
|
| T. Decker, G. Ivanyos, M. Santha, Pawel Wocjan (2013). Hidden Symmetry Subgroup Problems. SIAM Journal of Computing 42 1987-2007 |
|
| H. Klauck, V. Prakash (2013). Streaming computations with a loquacious prover. Proc. ICS 305-320 |
|
| H. Klauck, Ronald de Wolf (2013). Fooling One-Sided Quantum Protocols. Proceedings of STACS 424-433 |
|
| T. H. Johnson, J. D. Biamonte, S. Clark, D. Jaksch (2013). Solving search problems by strongly simulating quantum circuits. Scientific Reports 1235 |
|
| Atul Mantri, J. Fitzsimons, C.A. Delgado (2013). Optimal Blind Quantum Computation. Phys. Rev. Lett. 111 230502 |
|
| Ankit Gupta, Neeraj Kayal, Y. Qiao (2013). Random Arithmetic Formulas can be Reconstructed Efficiently (extended abstract). Proc. IEEE CCC |
|
| R. Kulkarni, Y. Qiao, Xiaoming Sun (2013). Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive. Theory and Applications of Models of Computation 224-235 |
|
| Le Huy Nguyen, Y. Cai, X. Wu, V. Scarani (2013). Tree-size complexity of multiqubit states. Phys. Rev. A 88 012321 |
|
| L. Magnin, Jérémie Roland (2013). Explicit relation between all lower bound techniques for quantum query complexity. Proceedings of STACS 20 434-445 |
|
| T. Lee, T. Lee, Jeremie Roland (2012). A strong direct product theorem for quantum query complexity. IEEE Conference on Computational Complexity 27 236-246 |
|
| C.A. Delgado, Marcin Zwierz, Pieter Kok (2012). Ultimate limits to quantum metrology and the meaning of the Heisenberg limit. Phys. Rev. A 2112 8 |
|
| G. Ivanyos, H. Klauck, T. Lee, T. Lee, M. Santha, Ronald de Wolf (2012). New bounds on the classical and quantum communication complexity of some graph properties. Proceedings of FSTTCS 148-159 |
|
| R. Jain, I. Kerenidis, Greg Kuperberg, M. Santha, Or Sattah, S. Zhang (2012). On the power of a unique quantum witness. Theory of Computing 8 375-400 |
|
| P. Coles (2012). Collapse of the quantum correlation hierarchy links entropic uncertainty to entanglement creation. Phys. Rev. A 86 062334 |
|
| A. Pereszlenyi (2012). On Quantum Interactive Proofs with Short Messages. CJTCS 2012 |
|
| R. Jain, Yaoyun Shi, Z.H. Wei, S. Zhang (2012). Correlation/Communication complexity of generating bipartite states. Symposium on Discrete Algorithms |
|
| R. Jain, A. Pereszlenyi, P. Yao (2012). A direct product theorem for bounded-round public-coin randomized communication complexity. Proc. IEEE FOCS |
|
| Frederic Magniez, A. Nayak, Peter Richter, M. Santha (2012). On the hitting times of quantum versus random walks. Algorithmica 63 98-116 |
|
| L. Magnin (2011). Two-player interaction in quantum computing: cryptographic primitives and query complexity. PhD Thesis |
|
| Andris Ambainis, L. Magnin, Martin Roetteler, Jérémie Roland (2011). Symmetry-assisted adversaries for quantum state generation. Proc. IEEE CCC 167-177 |
|
| Biamonte, JD, Bergholm, V., Whitfield, J.D., J. Fitzsimons, Aspuru-Guzik, A. (2011). Adiabatic quantum simulators. AIP Advances 1 022126 |
|
| Jop Briet, Harry Buhrman, T. Lee, T. Lee, Thomas Vidick (2011). All Schatten spaces endowed with the Schur product are Q-algebras. Journal of Functional Analysis 262 1-9 |
|
| P. Kurzynski, T. Paterek, R. Ramanathan, W. Laskowski, D. Kaszlikowski (2011). Correlation complementarity yields Bell monogamy relations. Phys. Rev. Lett. 106 180402 |
|
| M.E. McKague (2011). Self-testing graph states. Proceedings of TQC |
|
| S. Zhang (2011). On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity. Proceedings of ICALP 1 49-60 |
|
| Andre Chailloux, I. Kerenidis, B. Rosgen (2011). Quantum Commitments from Complexity Assumptions. Proceedings of ICALP 73-85 |
|
| T. Lee, T. Lee, Rajat Mittal, Ben Reichardt, Robert Spalek, M. Szegedy (2011). Quantum query complexity of state conversion. Proc. IEEE FOCS |
|
| R. Jain, S. Zhang (2011). The influence lower bound via query elimination. Theory of Computing |
|
| H. Klauck (2011). On Arthur Merlin Games in Communication Complexity. Proc. IEEE CCC 189-199 |
|
| Andre Chailloux, I. Kerenidis, Jamie Sikora (2010). Lower Bounds for Quantum Oblivious Transfer. Proceedings of FSTTCS |
|
| R. Jain, H. Klauck, M. Santha (2010). Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity. Inf. Proc. Lett 110 893-897 |
|
| B. Rosgen (2010). Computational distinguishability of degradable and antidegradable channels. Quantum Information and Computation 10 735-746 |
|
| R. Jain, Z. Ji, S. Upadhyay, J. Watrous (2010). QIP = PSPACE. Proceedings of ACM STOC 573-582 |
|
| R. Jain, H. Klauck (2010). The Partition Bound for Classical Communication Complexity and Query Complexity. Proc. IEEE CCC 247 |
|
| R. Jain, H. Klauck, S. Zhang (2010). Depth-Independent Lower bounds on Communication Complexity of Read-Once Boolean Functions. COCOON 16 |
|
| H. Klauck (2010). A strong direct product theorem for disjointness. Proceedings of ACM STOC 77-86 |
|
| Andre Chailloux, I. Kerenidis (2009). Optimal quantum strong coin flipping. Proc. IEEE FOCS |
|
| T. Lee, T. Lee, A. Shraibman (2009). An approximation algorithm for approximation rank. Proc. IEEE CCC 351-357 |
|
| P. Harsha, R. Jain, D.M. Allester, J. Radhakrishnan (2009). The communication complexity of correlation. IEEE Trans. Inf. 56 438 - 449 |
|
| M. Santha, M. Szegedy (2009). Quantum and classical query complexities of local search are polynomially related. Algorithmica 55 557-575 |
|
| R. Jain, A. Kolla, G. Midrijanis, B.W. Reichardt (2009). On parallel composition of zero-knowledge proofs with black-box quantum simulators. Quantum Information and Computation 9 513-532 |
|
| R. Jain, H. Klauck (2009). New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques. Proc. IEEE CCC 369-378 |
|
| K. Friedl, G. Ivanyos, M. Santha, Y.F. Verhoeven (2009). On the black-box complexity of Sperner's Lemma. Theory of Computing Systems 45 629-646 |
|
| R. Jain, S. Upadhyay, J. Watrous (2009). Two-message quantum interactive proofs are in PSPACE. Proc. IEEE FOCS |
|
| Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, S. Wehner (2008). The quantum moment problem and bounds on entangled multi-prover games. Proc. IEEE CCC 199--210 |
|
| R. Jain, H. Klauck, A. Nayak (2008). Direct product theorems for classical communication complexity via subdistribution bounds. Proceedings of ACM STOC 599-608 |
|
| Wim van Dam, Frederic Magniez, Michele Mosca, M. Santha (2007). Self-testing of universal and fault-tolerant sets of quantum gates. SIAM Journal of Computing 2 611-629 |
|
| Frederic Magniez, M. Santha, Mario Szegedy (2007). Quantum algorithms for the triangle problem. SIAM Journal of Computing 2 413-424 |
|
| J. Sudjana, L. Magnin, R. Garcia-Patron, N. J. Cerf (2007). Heisenberg-limited eavesdropping on the continuous-variable quantum cryptographic protocol with no basis switching is impossible. Phys. Rev. A 76 052301 |
|
| R. Cleve, W. Slofstra, F. Unger, S. Upadhyay (2007). Perfect parallel repetition theorem for quantum XOR proof systems.. Proc. IEEE CCC |
|
| H. Klauck (2007). One-Way Communication Complexity and the Neciporuk Lower Bound on Formula Size. SIAM Journal of Computing 37 552-583 |
|
| H. Klauck (2007). Lower Bounds for Quantum Communication Complexity. SIAM Journal of Computing 37 20-46 |
|
| H. Klauck, Robert Spalek, Ronald de Wolf (2007). Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. SIAM Journal of Computing 36 1472-1493 |
|
| H. Klauck, A. Nayak, Amnon Ta-Shma, David Zuckerman (2007). Interaction in Quantum Communication. IEEE Trans. Inf. 53 1970-1982 |
|
| S. Wehner (2006). Entanglement in Interactive Proof Systems with Binary Answers. Proceedings of STACS 3884 162-171 |
|
| L. Fortnow, T. Lee, T. Lee, N. Vereshchagin (2006). Kolmogorov Complexity with Error. Proceedings of ACM STOC 3884 137-148 |
|
| S. Laplante, T. Lee, T. Lee, M. Szegedy (2006). The quantum adversary method and formula size lower bounds . Proc. IEEE CCC 15 163-196 |
|
| R. Jain (2006). Communication complexity of remote state preparation with entanglement. Quantum Information and Computation 6 461-464 |
|
| R. Jain, J. Radhakrishnan, P. Sen (2005). Prior entanglement, message compression and privacy in quantum communication. Proc. IEEE CCC 285-296 |
|
| H. Klauck (2004). Quantum and Approximate Privacy. Theory of Computing Systems 37 221-246 |
|
| H. Klauck (2004). Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds. Proceedings of FSTTCS 384-395 |
|
| H. Klauck (2003). Rectangle Size Bounds and Threshold Covers in Communication Complexity. Proc. IEEE CCC 118-134 |
|
| Manaswi Paraashar, T. Lee, Sourav Chakraborty, Srinivasan Arunachalam, T. Lee, Ronald de Wolf Two new results about quantum exact learning. Proceedings of ICALP |
|
| Niraj Kumar, Eleni Diamanti, I. Kerenidis Efficient quantum communications with multiplexed coherent state fingerprints. Phys. Rev. A |
|
| Gabor Ivanyos, Anupam Prakash, M. Santha On learning linear functions from subset and its applications in quantum computing. |
|
