D. Aggarwal, N. StephensDavidowitz (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 560575 

I. Arad, M. Santha, Aarthi Sundaram, Shengyu Zhang (2018). Linear time algorithm for quantum 2SAT. Theory of Computing 127 

Y. Qiao, G. Ivanyos (2018). Algorithms based on *algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing. ACM SIAM SODA 23572376 

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 23572376 

K.T. Goh, J. Kaniewski, Elie Wolfe, Tamas Vertesi, X. Wu, Y. Cai, YeongCherng Liang, V. Scarani (2018). Geometry of the quantum set of correlations. Phys. Rev. A 97 022104 

Mika Goos, R. Jain, Thomas Watson (2018). Extension Complexity of Independent Set Polytopes. SIAM Journal of Computing 

D. Aggarwal, M. Obremski, T. Kazana (2017). Inception makes nonmalleable 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 semiinvariants. Computational Complexity 26 717763 

D. Gavinsky, R. Jain, H. Klauck, S.Kundu, 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 32nd Computational Complexity Conference 30 

A. Anshu, D. Gavinsky, R. Jain, S.Kundu, T. Lee, P. Mukhopadhyay, M. Santha, S. Sanyal (2017). A Composition Theorem for Randomized Query Complexity. FSTTCS 2017 

S. Nimmrichter, J. Dai, A.Roulet, V. Scarani (2017). Quantum and classical dynamics of a threemode absorption refrigerator. Quantum 1 37 

A. Anshu, V. Krishna, R. Jain (2017). Quantum Communication Using Coherent Rejection Sampling. Phys. Rev. Lett. 119 120506 

A. Anshu, R. Jain, P. Mukhopadhyay, Ala Shayeghi, P. Yao (2017). A new operational interpretation of relative entropy and trace distance between quantum states. IEEE Transactions on Information Theory 

A. Anshu, Shalev BenDavid, Ankit Garg, R. Jain, Robin Kothari, 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 7385 

T. Lee, Z.H. Wei, Ronald de Wolf (2017). Some upper and lower bounds on PSDrank. Mathematical Programming 162 495521 

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 199228 

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 612638 

Gábor Braun, R. Jain, T. Lee, Sebastian Pokutta (2016). Informationtheoretic approximations of the nonnegative rank. Computational Complexity 150 

A. Anshu, Aleksandrs Belovs, Shalev BenDavid, Mika Göös, R. Jain, Robin Kothari, T. Lee, M. Santha (2016). Separations in communication complexity using cheat sheets and information complexity. Proc. IEEE FOCS 555564 

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, T. Lee, M. Santha, Juris Smotrovs (2016). Separation in query complexity based on pointer functions. Proceedings of ACM STOC 800813 

H.S. Poh, Marcin Markiewicz, Pawel Kurzynski, A. Cere, D. Kaszlikowski, C. Kurtsiefer (2016). Probing the quantumclassical 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 915930 

Ralph C. Bottesch, D. Gavinsky, H. Klauck (2015). Equality, Revisited. International Symposium MFCS 2 127138 

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 1819 

Ralph C. Bottesch, D. Gavinsky, H. Klauck (2015). Correlation in Hard Distributions in Communication Complexity. RANDOM 544572 

Christopher Perry, R. Jain, J. Oppenheim (2015). Communication tasks with infinite quantumclassical separation. Phys. Rev. Lett. 115 030504 

Lila Fontes, R. Jain, I. Kerenidis, Sophie Laplante, Mathieu Laurier, Jérémie 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 Largescale Graph Problems. ACM SIAM SODA 391410 

H. Klauck, S. Podder (2014). New Bounds for the GardenHose 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 124 

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 fewqubit states. Phys. Rev. A 89 062333 

Nathanaël François, R. Jain, Frédéric Magniez (2014). Input/Output Streaming Complexity of Reversal and Sorting. RANDOM 654668 

R. Jain, A. Pereszlenyi, P. Yao (2014). A parallel repetition theorem for entangled twoplayer oneround games under product distributions. Proc. IEEE CCC 209216 

A. Nayak, R. Jain (2014). The space complexity of recognizing wellparenthesized expressions in the streaming model: the Index function revisited. IEEE Transactions on Information Theory 60 123 

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 226238 

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 663675 

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 397408 

L. Mancinska, T. Vidick (2014). Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability. LNCS 8572 835846 

Honghao Fu, Debbie Leung, L. Mancinska (2014). When the asymptotic limit offers no advantage in the localoperationsandclassicalcommunication paradigm. Phys. Rev. A 89 052310 

Julien Barre, Bruno Marcos, D. Wilkowski (2014). Nonequilibrium Phase Transition with Gravitationallike 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 928939 

R. Kulkarni, M. Santha (2013). Query complexity of matroids. CIAC 300311 

R. Jain, Yaoyun Shi, Z.H. Wei, S. Zhang (2013). Efficient protocols for generating bipartite classical distributions and quantum states. IEEE Transactions on Information Theory 59 51715178 

Prahladh Harsha, R. Jain (2013). A strong direct product theorem for the tribes function via the smoothrectangle bound. Proceedings of FSTTCS 141152 

T. Decker, G. Ivanyos, M. Santha, Pawel Wocjan (2013). Hidden Symmetry Subgroup Problems. SIAM Journal of Computing 42 19872007 

H. Klauck, V. Prakash (2013). Streaming computations with a loquacious prover. Proc. ICS 305320 

H. Klauck, Ronald de Wolf (2013). Fooling OneSided Quantum Protocols. Proceedings of STACS 424433 

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 3Uniform Hypergraphs Is Weakly Evasive. Theory and Applications of Models of Computation 224235 

Le Huy Nguyen, Y. Cai, X. Wu, V. Scarani (2013). Treesize 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 434445 

T. Lee, Jeremie Roland (2012). A strong direct product theorem for quantum query complexity. IEEE Conference on Computational Complexity 27 236246 

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, M. Santha, Ronald de Wolf (2012). New bounds on the classical and quantum communication complexity of some graph properties. Proceedings of FSTTCS 148159 

R. Jain, I. Kerenidis, Greg Kuperberg, M. Santha, Or Sattah, S. Zhang, Name of nonCQT author (2012). On the power of a unique quantum witness. Theory of Computing 8 375400 

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 boundedround publiccoin 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 98116 

L. Magnin (2011). Twoplayer interaction in quantum computing: cryptographic primitives and query complexity. PhD Thesis 

Andris Ambainis, L. Magnin, Martin Roetteler, Jérémie Roland (2011). Symmetryassisted adversaries for quantum state generation. Proc. IEEE CCC 167177 

Biamonte, JD, Bergholm, V., Whitfield, J.D., J. Fitzsimons, AspuruGuzik, A. (2011). Adiabatic quantum simulators. AIP Advances 1 022126 

Jop Briet, Harry Buhrman, T. Lee, Thomas Vidick (2011). All Schatten spaces endowed with the Schur product are Qalgebras. Journal of Functional Analysis 262 19 

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). Selftesting graph states. Proceedings of TQC 

S. Zhang (2011). On the Power of Lower Bound Methods for OneWay Quantum Communication Complexity. Proceedings of ICALP 1 4960 

Andre Chailloux, I. Kerenidis, B. Rosgen (2011). Quantum Commitments from Complexity Assumptions. Proceedings of ICALP 7385 

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 189199 

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 893897 

B. Rosgen (2010). Computational distinguishability of degradable and antidegradable channels. Quantum Information and Computation 10 735746 

R. Jain, Z. Ji, S. Upadhyay, J. Watrous (2010). QIP = PSPACE. Proceedings of ACM STOC 573582 

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). DepthIndependent Lower bounds on Communication Complexity of ReadOnce Boolean Functions. COCOON 16 

H. Klauck (2010). A strong direct product theorem for disjointness. Proceedings of ACM STOC 7786 

Andre Chailloux, I. Kerenidis (2009). Optimal quantum strong coin flipping. Proc. IEEE FOCS 

T. Lee, A. Shraibman (2009). An approximation algorithm for approximation rank. Proc. IEEE CCC 351357 

P. Harsha, R. Jain, D.M. Allester, J. Radhakrishnan (2009). The communication complexity of correlation. IEEE Transactions on Information Theory 56 438  449 

M. Santha, M. Szegedy (2009). Quantum and classical query complexities of local search are polynomially related. Algorithmica 55 557575 

R. Jain, A. Kolla, G. Midrijanis, B.W. Reichardt (2009). On parallel composition of zeroknowledge proofs with blackbox quantum simulators. Quantum Information and Computation 9 513532 

R. Jain, H. Klauck (2009). New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques. Proc. IEEE CCC 369378 

K. Friedl, G. Ivanyos, M. Santha, Y.F. Verhoeven (2009). On the blackbox complexity of Sperner's Lemma. Theory of Computing Systems 45 629646 

R. Jain, S. Upadhyay, J. Watrous (2009). Twomessage quantum interactive proofs are in PSPACE. Proc. IEEE FOCS 

Andrew C. Doherty, YeongCherng Liang, Ben Toner, S. Wehner (2008). The quantum moment problem and bounds on entangled multiprover games. Proc. IEEE CCC 199210 

R. Jain, H. Klauck, A. Nayak (2008). Direct product theorems for classical communication complexity via subdistribution bounds. Proceedings of ACM STOC 599608 

Wim van Dam, Frederic Magniez, Michele Mosca, M. Santha (2007). Selftesting of universal and faulttolerant sets of quantum gates. SIAM Journal of Computing 2 611629 

Frederic Magniez, M. Santha, Mario Szegedy (2007). Quantum algorithms for the triangle problem. SIAM Journal of Computing 2 413424 

J. Sudjana, L. Magnin, R. GarciaPatron, N. J. Cerf (2007). Heisenberglimited eavesdropping on the continuousvariable 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). OneWay Communication Complexity and the Neciporuk Lower Bound on Formula Size. SIAM Journal of Computing 37 552583 

H. Klauck (2007). Lower Bounds for Quantum Communication Complexity. SIAM Journal of Computing 37 2046 

H. Klauck, Robert Spalek, Ronald de Wolf (2007). Quantum and Classical Strong Direct Product Theorems and Optimal TimeSpace Tradeoffs. SIAM Journal of Computing 36 14721493 

H. Klauck, A. Nayak, Amnon TaShma, David Zuckerman (2007). Interaction in Quantum Communication. IEEE Transactions on Information Theory 53 19701982 

S. Wehner (2006). Entanglement in Interactive Proof Systems with Binary Answers. Proceedings of STACS 3884 162171 

L. Fortnow, T. Lee, N. Vereshchagin (2006). Kolmogorov Complexity with Error. Proceedings of ACM STOC 3884 137148 

S. Laplante, T. Lee, M. Szegedy (2006). The quantum adversary method and formula size lower bounds . Proc. IEEE CCC 15 163196 

R. Jain (2006). Communication complexity of remote state preparation with entanglement. Quantum Information and Computation 6 461464 

R. Jain, J. Radhakrishnan, P. Sen (2005). Prior entanglement, message compression and privacy in quantum communication. Proc. IEEE CCC 285296 

H. Klauck (2004). Quantum and Approximate Privacy. Theory of Computing Systems 37 221246 

H. Klauck (2004). Quantum and Classical CommunicationSpace Tradeoffs from Rectangle Bounds. Proceedings of FSTTCS 384395 

H. Klauck (2003). Rectangle Size Bounds and Threshold Covers in Communication Complexity. Proc. IEEE CCC 118134 

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.  None  
