Computer Science Group Publications

Year Content Icon
Leonard Wossnig, Zhikuan Zhao, A.Prakash (2018). A quantum linear system algorithm for dense matrices. Phys. Rev. Lett. 120 050502
A. Anshu, R. Jain, N.A Warsi (2018). A generalized quantum Slepian-Wolf. IEEE Transactions on Information Theory
A. Anshu, R. Jain, N.A Warsi (2018). A one-shot achievability result for quantum state redistribution. IEEE Transactions on Information Theory
Mika Göös, 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
H. Klauck (2017). The Complexity of Quantum Disjointness. International Symposium MFCS 83 15:1-15:13
A.Prakash, Jamie William Jonathon Sikora, A.Varvitsiotis, Zhaohui Wei (2017). Completely positive semidefinite rank. Mathematical Programming
Gábor Ivanyos, Rajat Mittal, Nitin Saxena, Vishwas Bhargava (2017). Irreducibility and r-th root finding over finite fields. ISSAC 37-44
Youming Qiao, K. V. Subrahmanyam, G. Ivanyos (2017). On generating the ring of matrix semi-invariants. Computational Complexity 26 717-763
D. Aggarwal, T. Kazana (2017). Inception makes non-malleable codes stronger. Theory of Cryptography 319-343
D. Gavinsky, R. Jain, H. Klauck, S.Kundu, T. Lee, M. Santha, S. Sanyal, Jevgenijs Vihrovs (2017). Quadratically Tight Relations for Randomized Query Complexity. Electronic Colloquium on Computational Complexity 123
A. Anshu, R. Jain, N.A Warsi (2017). A hypothesis testing approach for communication over entanglement assisted compound quantum channel. CoRR abs/1706.0
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 (2017). An upper bound on quantum capacity of unital channels. Proc. IEEE ITW
A. Anshu, Dave Touchette, P. Yao, Nengkun Yu (2017). Exponential Separation of Quantum Communication and Classical Information. ACM STOC 277-288
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 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
G. Ivanyos, M. Santha (2017). On solving systems of diagonal polynomial equations over finite fields. Theoretical Computer Science 657 73-85
T. Lee, Frederic Magniez, M. Santha (2017). Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing. Algorithmica 77 459-486
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
P. Mukhopadhyay, Y. Qiao (2017). Sparse multivariate polynomial interpolation in the basis of Schubert polynomials. Computational Complexity 26 881-909
Z.H. Wei, S. Zhang (2017). Quantum Game Players Can Have Advantage Without Discord. Information and Computation 256 174-184
O. Regev, D. Aggarwal (2016). A Note on Discrete Gaussian Combinations of Lattice Vectors. CJTCS 1
(2016). Revisiting the {S}anders-{B}ogolyubov-{R}uzsa theorem in $mathbb{F}_p^n$ and its application to non-malleable codes. IEEE ISIT 1322-1326
A. Anshu, Ankit Garg, Aram Harrow, P. Yao (2016). Lower bound on expected communication cost of quantum Huffman coding. TQCCC 61 3:1-3:18
A. Anshu, I. Arad, Thomas Vidick (2016). Simple proof of the detectability lemma and spectral gap amplification. Phys. Rev. B 93 205142
A. Anshu (2016). Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems. New J. Phys. 18 083011
Prahladh Harsha, R. Jain, Jaikumar Radhakrishnan (2016). Partition bound is quadratically tight for product distributions. Proceedings of ICALP
A. Anshu, I. Arad, Aditya Jain (2016). How local is the information in MPS/PEPS tensor networks?. Phys. Rev. B 94 195143
Ashwin Nayak, Jamie William Jonathon Sikora, Levent Tuncel (2016). A search for quantum coin-flipping protocols using optimization techniques. Mathematical Programming 156 581-613
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
Andre Chailloux, I. Kerenidis, S.Kundu, Jamie William Jonathon Sikora (2016). Optimal bounds for parity-oblivious random access codes. New J. Phys. 045003
Alex B. Grilo, I. Kerenidis, Jamie William Jonathon Sikora (2016). QMA with subset state witnesses. CJTCS
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 (2016). Simple, near-optimal quantum protocols for die-rolling based on integer-commitment. TQCCC
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
Nikhil Balaji, Samir Datta, R. Kulkarni, S. Podder (2016). Graph properties in node-query setting: effect of breaking symmetry. International Symposium MFCS
T. Lee, A.Prakash, R. de Wolf, H. Yuen (2016). On the sum-of-squares degree of symmetric quadratic functions. Proc. IEEE CCC
Alex B. Grilo, I. Kerenidis, A. Pereszlenyi (2016). Pointer Quantum PCPs and Multi-Prover Games. International Symposium MFCS
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
I. Arad, M. Santha, A. Sundaram, S. Zhang (2016). Linear time algorithm for quantum 2SAT. Automata, Languages, and Programming 15 1-14
I. Arad, A. Bouland, D. Grier, M. Santha, A. Sundaram, S. Zhang (2016). On the complexity of probabilistic trials for hidden satisfiability problems. International Symposium MFCS 12 1-14
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
D. Gavinsky (2016). Entangled simultaneity versus classical interactivity in communication complexity. Proceedings of ACM STOC
D. Gavinsky, Pavel Pudlak (2016). On the Joint Entropy of d-Wise-Independent Variables. Commentationes Mathematicae Universitatis Carolinae 57 333-343
Iordanis Kerenidis, André Chailloux, Srijita Kundu, Jamie Sikora (2016). Optimal bounds for parity-oblivious random access codes with applications. New J. Phys. 18 045003
R. Jain (2016). New strong direct product results in communication complexity. JACM 62
Sevag Gharibian, Jamie William Jonathon Sikora (2015). Ground state connectivity of local Hamiltonians. Proceedings of ICALP 9134 617-628
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
Friesen, Mirjam, Hamed, Aya, T. Lee, Theis, Dirk Oliver (2015). Fooling-sets and rank. European Journal of Combinatorics 48
Chakraborty, Sourav, R. Kulkarni, Lokam, Satyanarayana V., Saurabh, Nitin (2015). Upper Bounds on Fourier Entropy. Computing and Combinatorics 9198
J. Kaniewski, T. Lee, de Wolf, Ronald (2015). Query Complexity in Expectation. Automata, Languages, and Programming 9134
Sattath, Or, I. Arad (2015). A CONSTRUCTIVE QUANTUM LOVASZ LOCAL LEMMA FOR COMMUTING PROJECTORS. Quantum Information and Computation 15
R. Kulkarni, Y. Qiao, Sun, Xiaoming (2015). On the Power of Parity Queries in Boolean Decision Trees. Theory and Applications of Models of Computation 9076
I. Kerenidis, Sophie Laplante, Virginie Lerays, Jeremie Roland, David Xiao (2015). Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications. SIAM Journal of Computing 44
Ralph C. Bottesch, D. Gavinsky, H. Klauck (2015). Equality, Revisited. International Symposium MFCS 2 127-138
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, 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 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
Andre Chailloux, I. Kerenidis, Jamie William Jonathon Sikora (2014). Strong connections between quantum encodings, nonlocality, and cryptography. Phys. Rev. A 89 022334
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
Nathanaël François, R. Jain, Frédéric 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 Transactions on Information Theory 60 1-23
Somshubhro Bandyopadhyay, R. Jain, J. Oppenheim, Christopher Perry (2014). Conclusive Exclusion of Quantum States. Phys. Rev. A 89 22336-2234
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
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 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
Sevag Gharibian, Jamie Sikora, S. Upadhyay (2013). QMA variants with polynomially many provers. Quantum Information and Computation 13 0135-0157
M.E. McKague (2013). On the power quantum computation over real Hilbert spaces. Int. J. Quant. Info. 11 1350001
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
A. Anshu, M. Mhalla (2013). Pseudo-telepathy games and genuine NS k-way nonlocality using graph states. Quantum Information and Computation 13 0834-0846
Anna Pappa, André Chailloux, S. Wehner, Eleni Diamanti, I. Kerenidis (2012). Multipartite Entanglement Verification Resistant against Dishonest Parties. Phys. Rev. Lett. 108 260502
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, 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
R. Jain, I. Kerenidis, Greg Kuperberg, M. Santha, Or Sattah, S. Zhang, Name of non-CQT author (2012). On the power of a unique quantum witness. Theory of Computing 8 375-400
M.E. McKague, T.H. Yang, V. Scarani (2012). Robust Self Testing of the Singlet. J. Phys. A: Math. Gen. 45 455304
A. Pereszlenyi (2012). On Quantum Interactive Proofs with Short Messages. CJTCS 2012
C.A. Delgado, Mark E. Pearce, Pieter Kok (2012). Fundamental Limits of Classical and Quantum Imaging. Phys. Rev. Lett. 109
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
I. Kerenidis, S. Wehner (2012). Long distance two-party quantum cryptography made simple. Quantum Information Processing 12 0448-0460
Stefanie Barz, Elham Kashefi, Anne Broadbent, J. Fitzsimons, Anton Zeilinger, Philip Walther (2012). Experimental Demonstration of Blind Quantum Computing. Science 303
R. Jain, A. Nayak (2012). A short proof of the Quantum Substate Theorem. IEEE Transactions on Information Theory
Frederic Magniez, A. Nayak, Peter Richter, M. Santha (2012). On the hitting times of quantum versus random walks. Algorithmica 63 98-116
G. Ivanyos, Luc Sanselme, M. Santha (2012). An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups. Algorithmica 62 480-498
F. Magniez, M. de Rougemont, M. Santha, X. Zeitoun (2011). The complexity of approximate Nash equilibrium in congestion games with negative delays. Proceedings of WINE 266-277
Anna Pappa, Andre Chailloux, Eleni Diamanti, I. Kerenidis (2011). Practical Quantum Coin Flipping. Phys. Rev. A 84 052305
J. Fitzsimons (2011). Review of algebraic cryptanalysis by Gregory V. Bard. abbrv 42 14-18
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
J. Silman, A. Chailloux, N. Aharon, I. Kerenidis, S. Pironio, S. Massar (2011). Fully Distrustful Quantum Cryptography. Phys. Rev. Lett. 106 220501
Andre Chailloux, I. Kerenidis (2011). Optimal bounds for quantum bit commitment. Proc. IEEE FOCS
Yuichiro Matsuzaki, Simon C. Benjamin, J. Fitzsimons (2011). Entangling unstable optically active matter qubits. Phys. Rev. A 83 060303
Tom Close, Femi Fadugba, Simon C. Benjamin, J. Fitzsimons, Brendon W. Lovett (2011). Rapid and robust spin state amplification. Phys. Rev. Lett. 106 167204
Yuichiro Matsuzaki, Simon C. Benjamin, J. Fitzsimons (2011). Magnet field sensing beyond the standard quantum limit under the effect of decoherence. Phys. Rev. A 84 012103
M.E. McKague (2011). Super-quantum non-local correlations in quaternionic quantum theory. Int. J. Quant. Info.
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
Frederic Magniez, A. Nayak, Jeremie Roland, M. Santha (2011). Search via Quantum Walk. SIAM Journal of Computing 1 142-164
Andre Chailloux, I. Kerenidis, B. Rosgen (2011). Quantum Commitments from Complexity Assumptions. Proceedings of ICALP 73-85
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
R. Jain, P. Yao (2011). A Parallel Approximation Algorithm for Positive Semidefinite Programming. Proc. IEEE FOCS
H. Klauck (2011). On Arthur Merlin Games in Communication Complexity. Proc. IEEE CCC 189-199
Marc Kaplan, I. Kerenidis, Sophie Laplante, Jeremie Roland (2010). Non-Local Box Complexity and Secure Function Evaluation. Quantum Information and Computation 11 40-69
Andre Chailloux, I. Kerenidis, Jamie Sikora (2010). Lower Bounds for Quantum Oblivious Transfer. Proceedings of FSTTCS
Earl T. Campbell, J. Fitzsimons (2010). An introduction to one-way quantum computing in distributed architectures. Int. J. Quant. Info. 8 219-258
R. Jain (2010). Resource requirements of private quantum channels and consequences for oblivious remote state preparation. Journal of Cryptology 1-13
G. Ivanyos, M. Karpinski, N. Saxena (2010). Deterministic polynomial time algorithms for matrix completion problems. SIAM Journal of Computing 39 3736-3751
T. Lee, S. Zhang (2010). Composition theorems in communication complexity . Proceedings of ICALP
M. Schaffry, E.M. Gauger, J.J.L. Morton, J. Fitzsimons, S.C. Benjamin, B.W. Lovett (2010). Quantum metrology with molecular ensembles. Phys. Rev. A 82 042114
B. Rosgen (2010). Testing non-isometry is QMA-complete. Proceedings of TQC
Y. Matsuzaki, S.C. Benjamin, J. Fitzsimons (2010). Distributed quantum computation with arbitrarily poor photon detection. Phys. Rev. A 82 010302
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
Y. Matsuzaki, S.C. Benjamin, J. Fitzsimons (2010). Probabilistic growth of large entangled states with low error accumulation. Phys. Rev. Lett. 104 050501
Andre Chailloux, I. Kerenidis (2009). Optimal quantum strong coin flipping. Proc. IEEE FOCS
M.E. McKague, M. Mosca, N. Gisin (2009). Simulating quantum systems using real hilbert spaces. Phys. Rev. Lett. 102 020505
M.E. McKague (2009). Device independent quantum key distribution secure against coherent attacks with memoryless measurement devices. New J. Phys. 11 103037
T. Decker (2009). Symmetric measurements attaining the accessible information. IEEE Transactions on Information Theory 55 2375-2383
T. Decker, J. Draisma, P. Wocjan (2009). Quantum algorithm for identifying hidden polynomial function graphs. Quantum Information and Computation 9 215-230
G. Ivanyos, M. Karpinski, N. Saxena (2009). Schemes for deterministic polynomial factoring. ISSAC 191-198
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
P. Harsha, R. Jain, D.M. Allester, J. Radhakrishnan (2009). The communication complexity of correlation. IEEE Transactions on Information Theory 56 438 - 449
R. Jain, S. Zhang (2009). New bounds on classical and quantum one-way communication complexity. Theoretical Computer Science 410 2463-2477
M. Santha, M. Szegedy (2009). Quantum and classical query complexities of local search are polynomially related. Algorithmica 55 557-575
R. Cleve, D. Gavinsky, R. Jain (2009). Entanglement-resistant two-prover interactive proof systems and non-adaptive private information retrieval systems. Quantum Information and Computation 9 648-656
R. Jain, J. Radhakrishnan, P. Sen (2009). A new information-theoretic property about quantum states with an application to privacy in quantum communication. JACM 56
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, J. Watrous (2009). Parallel approximation of non-interactive zero-sum quantum games. Proc. IEEE CCC 243-253
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
K. Friedl, F. Magniez, M. Santha, P. Sen (2009). Quantum testers for hidden group properties. Fundamenta Informaticae 91 325-340
R. Jain, S. Upadhyay, J. Watrous (2009). Two-message quantum interactive proofs are in PSPACE. Proc. IEEE FOCS
C.E. Bardyn, M.E. McKague, S. Massar, V. Scarani (2009). Device independent state estimation based on Bell. Phys. Rev. A 80 062327
D. Bacon, T. Decker (2008). Optimal single-copy measurement for the hidden-subgroup problem. Phys. Rev. A 77 032335
D. Janzing, T. Decker (2008). How much is a quantum controller controlled by the controlled system?. Applicable Algebra in Engineering, Communication and Computing 19 241-258
P. Wocjan, D. Janzing, T. Decker, T. Beth (2008). Measuring 4-local n-qubit observables could probabilistically solve PSPACE. Quantum Information and Computation 8 741-755
G. Ivanyos, A.B. Nagy, L. Rónyai (2008). Constructions for quantum computing with symmetrized gates. Quantum Information and Computation 8 0411-0429
G. Ivanyos (2008). On solving systems of random linear disequations. Quantum Information and Computation 8 0579-0594
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
R. Jain (2008). New binding-concealing trade-offs for quantum string commitment. Journal of Cryptology 24 579-592
R. Jain, A. Nayak, Y. Su (2008). A separation between divergence and Holevo information for ensembles. Theory and Applications of Models of Computation 526-541
J. Ivanyos, L. Sanselme, M. Santha (2008). An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups. Latin American Symposium on Theoretical Informatics 759-771
M. Santha (2008). Quantum walk based search algorithms. International Conference on Theory and Applications of Models of Computation 31-46
S. Hemon, M.D. Rougemont, M. Santha (2008). Approximate Nash equilibria for multi-player games. Symposium on Algorithmic Game Theory 267-278
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
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 Transactions on Information Theory 53 1970-1982
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
D. Janzing, T. Decker (2006). Minimally disturbing Heisenberg-Weyl symmetric measurements using hard-core collisions of Schrödinger particles. J. Math. Phys. 47 082102
T. Decker, M. Grassl (2006). Implementation of generalized measurements with minimal disturbance on a quantum computer. Fortschritte der Physik 54 898-916
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
R. Jain (2006). Communication complexity of remote state preparation with entanglement. Quantum Information and Computation 6 461-464
T. Decker, D. Janzing, M. Rötteler (2005). Implementation of group-covariant positive operator valued measures by orthogonal measurements. J. Math. Phys. 44 012104
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
T. Decker, D. Janzing, T. Beth (2004). Quantum circuits for single-qubit measurements corresponding to platonic solids. Int. J. Quant. Info. 2 353-377
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
H. Klauck (2003). Rectangle Size Bounds and Threshold Covers in Communication Complexity. Proc. IEEE CCC 118-134
D. Janzing, T. Decker, T. Beth (2003). Performing joint measurements and transformations on several qubits by operating on a single control qubit. Phys. Rev. A 67 042320
R. Jain, J. Radhakrishnan, P. Sen (2003). A direct sum theorem in communication complexity via message compression. Proceedings of ICALP 187
R. Jain, J. Radhakrishnan, P. Sen (2003). A lower bound for bounded round quantum communication complexity of set disjointness. Proc. IEEE FOCS 220
T. Lee (2003). Arithmetical Definability over Finite Structures. Mathematical Logic Quarterly 49 385-392
R. Jain, J. Radhakrishnan, P. Sen (2002). The quantum communication complexity of the pointer chasing problem: the bit version. Proceedings of FSTTCS 218-229
A. Deshpande, R. Jain, S.V. Lokam, J. Radhakrishnan, K. Telikapalli (2002). Improved lower bounds for locally decodable codes. Proc. IEEE CCC 152-161
R. Jain, J. Radhakrishnan, P. Sen (2002). Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states. Proc. IEEE FOCS 429-438
V. Tereshko, T. Lee (2002). How Information-Mapping Patterns Determine Foraging Behaviour of a Honey Bee Colony . Open Sys. Info. Dyn. 9 1-13
Gábor Ivanyos Finding hidden Borel subgroups of the general linear group. Quantum Information and Computation
Raghav Kulkarni, Youming Qiao, M. Santha, Aarthi Sundaram, Gábor Ivanyos On the Complexity of Trial and Error for Constraint Satisfaction Problems. Journal of Computer and System Sciences
Igor Shparlinski, G. Ivanyos, Marek Karpinski, M. Santha, Nitin Saxena Polynomial Interpolation and Identity Testing from High Powers over Finite Fields. Algorithmica
Kaspars Balodis, Aleksandrs Belovs, T. Lee, M. Santha, Juris Smotrovs, Andris Ambainis Separations in Query Complexity Based on Pointer Functions. JACM