Publications

All

Year Content Icon
, Mathieu Bozzio, Adeline Orieux, Luis Trigo Vidarte, Isabelle Zaquine, I. Kerenidis, Eleni Diamanti (2018). Experimental investigation of practical unforgeable quantum money. New J. Phys.
, Leonard Wossnig, Zhikuan Zhao, A.Prakash (2018). A quantum linear system algorithm for dense matrices. Phys. Rev. Lett. 120 050502
Leonard Wossnig, Zhikuan Zhao, Anupam Prakash (2018). A quantum linear system algorithm for dense matrices. Phys. Rev. Lett. 120
A. Anshu, R. Jain, NA Warsi (2018). A generalized quantum Slepian-Wolf. IEEE Transactions on Information Theory
Mika Goos, R. Jain, Thomas Watson (2018). Extension Complexity of Independent Set Polytopes. SIAM Journal of Computing
M. Grassl, L. Kong, Z.H. Wei, Z. Yin, B. Zeng (2018). Quantum Error-Correcting Codes for Qudit Amplitude Damping. IEEE Transactions on Information Theory
André Chailloux, I. Kerenidis (2017). Optimal bounds for quantum bit commitment. SIAM Journal of Computing 46 1647–167
A.Prakash, Jamie William Jonathon Sikora, A.Varvitsiotis, Zhaohui Wei (2017). Completely positive semidefinite rank. Mathematical Programming
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
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
A. Anshu, V. Krishna, R. Jain (2017). Quantum Communication Using Coherent Rejection Sampling. Phys. Rev. Lett. 119 120506
A. Anshu, Shalev Ben-David, Ankit Garg, R. Jain, Robin Kothari, T. Lee (2017). Separating quantum communication and approximate rank. Proc. IEEE CCC
Jamie William Jonathon Sikora, A.Varvitsiotis (2017). Linear conic formulations for two-party correlations and values of nonlocal games. Mathematical Programming 162 431-463
T. Lee, Z.H. Wei, Ronald de Wolf (2017). Some upper and lower bounds on PSD-rank. Mathematical Programming 162 495--521
Z.H. Wei, Jamie William Jonathon Sikora (2017). Device-independent characterizations of the quantum state in a Bell experiment. Phys. Rev. A 95 032103
R. Jain, Z.H. Wei, Penghui Yao, S. Zhang (2017). Multipartite Quantum Correlation and Communication Complexities. Computational Complexity 26 199--228
Z.H. Wei, S. Zhang (2017). Quantum Game Players Can Have Advantage Without Discord. Information and Computation 256 174-184
Jamie William Jonathon Sikora, A.Varvitsiotis, Z.H. Wei (2016). Minimum dimension of a Hilbert space needed to generate a quantum correlation. Phys. Rev. Lett. 117 060401
Jamie William Jonathon Sikora, A.Varvitsiotis, Z.H. Wei (2016). Device-independent dimension tests in the prepare-and-measure scenario. Phys. Rev. A 94 042125
Gábor Braun, R. Jain, T. Lee, Sebastian Pokutta (2016). Information-theoretic approximations of the nonnegative rank. Computational Complexity 1-50
A. Anshu, Aleksandrs Belovs, Shalev Ben-David, 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 555-564
T. Lee, A.Prakash, R. de Wolf, H. Yuen (2016). On the sum-of-squares degree of symmetric quadratic functions. Proc. IEEE CCC
T. Lee, N. Leonardos, M. Saks, F. Wang (2016). Hellinger volume and number-on-the-forehead communication complexity. Journal of Computer and System Sciences
L. Mancinska, D. E. Roberson, A.Varvitsiotis (2016). On deciding the existence of perfect entangled strategies for nonlocal games. CJTCS 1-16
, 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 800-813
R. Jain (2016). New strong direct product results in communication complexity. JACM 62
, Friesen, Mirjam, Hamed, Aya, T. Lee, Theis, Dirk Oliver (2015). Fooling-sets and rank. European Journal of Combinatorics 48
J. Kaniewski, T. Lee, de Wolf, Ronald (2015). Query Complexity in Expectation. Automata, Languages, and Programming 9134
, Ralph C. Bottesch, D. Gavinsky, H. Klauck (2015). Equality, Revisited. International Symposium MFCS 2 127-138
, 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, Jérémie Roland (2015). Relative discrepancy does not separate information and communication complexity. Proceedings of ICALP
H. Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson (2015). Distributed Computation of Large-scale Graph Problems. ACM SIAM SODA 391-410
T. Lee, Frederic Magniez, M. Santha (2015). Improved quantum query algorithms for Triangle Finding and Associativity Testing. Algorithmica 1486-1502
H. Klauck, S. Podder (2014). New Bounds for the Garden-Hose Model . Proceedings of FSTTCS
L. Mancinska, David E. Roberson, A.Varvitsiotis (2014). Two characterizations of nonlocal games with perfect maximally entangled strategies. AQIS
, M. E.-Nagy, Monique Laurent, A.Varvitsiotis (2014). Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope. Journal of Combinatorial Theory, Series B 108 40-80
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
A. Nayak, R. Jain (2014). The space complexity of recognizing well-parenthesized expressions in the streaming model: the Index function revisited. IEEE Transactions on Information Theory 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
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
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. Lee, Jeremie Roland (2012). A strong direct product theorem for quantum query complexity. IEEE Conference on Computational Complexity 27 236-246
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 148-159
T. Lee, Frederic Magniez, M. Santha (2012). Learning graph based quantum query algorithms for finding constant-size subgraphs. CJTCS 2012 1-21
Jop Briet, Harry Buhrman, T. Lee, Thomas Vidick (2011). All Schatten spaces endowed with the Schur product are Q-algebras. Journal of Functional Analysis 262 1-9
T. Lee, Rajat Mittal, Ben Reichardt, Robert Spalek, M. Szegedy (2011). Quantum query complexity of state conversion. Proc. IEEE FOCS
T. Lee, S. Zhang (2010). Composition theorems in communication complexity . Proceedings of ICALP
T. Lee, A. Shraibman (2009). Disjointness is hard in the multi-party number-on-the-forehead model. Proc. IEEE CCC 309-336
T. Lee, R. Mittal (2009). Product theorems via semidefinite programming.. Proceedings of ICALP 5125 674-685
T. Lee, A. Shraibman (2009). An approximation algorithm for approximation rank. Proc. IEEE CCC 351-357
T. Lee, G. Schechtman,, A. Shraibman (2009). Lower bounds on quantum multiparty communication complexity . Proc. IEEE CCC 254-262
T. Lee, A. Shraibman, R. Spalek (2008). A direct product theorem for discrepancy. Proc. IEEE CCC 71-80
, A.M. Childs, T. Lee (2008). Optimal quantum adversary lower bounds for ordered search. . Proceedings of ICALP 5125 869-880
T. Lee (2007). A new rank technique for formula size lower bounds. Proceedings of STACS 4393 145-156
P. Hoyer, T. Lee, R. Spalek (2007). Negative weights make adversaries stronger. ACM STOC 526-535
T. Lee, A. Shraibman (2007). Lower bounds on communication complexity . Foundations & Trends in Theoretical Computer Science 4 263-399
, L. Fortnow, T. Lee, N. Vereshchagin (2006). Kolmogorov Complexity with Error. Proceedings of ACM STOC 3884 137-148
S. Laplante, T. Lee, M. Szegedy (2006). The quantum adversary method and formula size lower bounds . Proc. IEEE CCC 15 163-196
, H. Buhrman, T. Lee, D. van Melkebeek (2004). Language Compression and Pseudorandom Generators. Proc. IEEE CCC 14 228-255
T. Lee, A. Romashchenko (2004). Resource Bounded Symmetry of Information Revisited . Theoretical Computer Science 345 386-405
T. Lee (2003). Arithmetical Definability over Finite Structures. Mathematical Logic Quarterly 49 385-392
V. Tereshko, T. Lee (2002). How Information-Mapping Patterns Determine Foraging Behaviour of a Honey Bee Colony . Open Sys. Info. Dyn. 9 1-13
Yukun Wang, I.W. Primaatmaja, Antonios Varvitsiotis, Charles Ci Wen Lim Characterising the behaviour of classical-quantum broadcast networks. - None -
Niraj Kumar, Eleni Diamanti, I. Kerenidis Efficient quantum communications with multiplexed coherent state fingerprints. Phys. Rev. A