| Maciej Lukasz Obremski, D. Aggarwal (2022). A constant rate non-malleable code in the split-state model. IEEE Annual Symposium on Foundations of Computer Science (FOCS) |
|
| M Simkin, , M Skórski, , D Venturi, G Brian,, A Faonio, Maciej Lukasz Obremski, J Ribeiro, (2022). The Mother of All Leakages: How to Simulate Noisy Leakages via Bounded Leakage (Almost) for Free. IEEE Transactions on Information Theory |
|
| G Malavolta, Maciej Lukasz Obremski, D. Aggarwal, N Dottling, , J Dujmovic, , M Hajiabadi, (2022). Algebraic Restriction Codes and their Applications. Innovations in Theoretical Computer Science (ITCS) |
|
| L Siniscalchi, J Ribeiro, M Simkin, Maciej Lukasz Obremski, D. Aggarwal (2022). Two-Source Non-Malleable Extractors and Applications to Privacy Amplification with Tamperable Memory . IEEE Transactions on Information Theory |
|
| J Ribeiro, J B Nielsen, Maciej Lukasz Obremski (2022). Public Randomness Extraction with Ephemeral Roles and Worst-Case Corruptions. Proceedings of CRYPTO |
|
| P. Rebentrost, A.Luongo, João F. Doriguello, J.Bao, M. Santha (2022). Quantum algorithm for stochastic optimal stopping problems with applications in finance. Proceedings of TQC 2:1-2:2:24 |
 |
| M. Santha, T. Lee, D. Gavinsky, Swagato Sanyal (2022). A composition theorem for randomized query complexity via max conflict complexity. Theory of Computing 18 |
|
| M. Santha, Tongyang Li, T. Lee, Shengyu Zhang (2021). On the cut dimension of a graph. Proceedings of the Computational Complexity Conference 200 15:1-15:35 |
|
| Shengyu Zhang, M. Santha, T. Lee (2021). Quantum algorithms for graph problems with cut queries. ACM-SIAM Symposium on Discrete Algorithms (SODA) 939-958 |
|
| Maharshi Ray, Yassine Hamoudi, P. Rebentrost, M. Santha, Siyi Yang, Xin Wang (2021). Quantum algorithms for hedging and the learning of Ising models. Phys. Rev. A 103 |
|
| M. Santha, S. Massar (2021). Total Functions in QMA. Quantum Information Processing 20(1) pp. 1-35 |
|
| Shalev Ben-David, Anurag Anshu, S.Kundu (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 |
|
| Ashwin Nayak, R. Jain, Shima Bab Hadiashar, Anurag Anshu, Dave Touchette (2021). One-shot quantum state redistribution and quantum Markov chains. Annual Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC) |
|
| R. Jain (2021). Chain-rules for channel capacity. IEEE International Symposium on Information Theory |
|
| S.Kundu, R. Jain (2021). A Direct Product Theorem for One-Way Quantum Communication. Proceedings of the Computational Complexity Conference |
|
| M.Ray, N.G. Boddu, K. Bharti, L.C. Kwek, Adán Cabello (2021). Graph-theoretic approach to dimension witnessing. New J. Phys. 23 033006 |
|
| Maciej Lukasz Obremski, D. Aggarwal, J Ribeiro, L Siniscalchi, I Visconti (2020). How to Extract Useful Randomness from Unreliable Sources. Proceedings of EUROCRYPT |
|
| M Skorski, Maciej Lukasz Obremski (2020). Complexity of Estimating Renyi Entropy of Markov Chains. ISIT 2021 |
|
| Maciej Lukasz Obremski, J Ribeiro, , N Stephens-Davidowitz, D. Aggarwal, S Guo (2020). Extractors Lower Bounds, Revisited. RANDOM |
|
| Gianluca Brian, Antonio Faonio, Maciej Lukasz Obremski, Daniele Venturi, Mark Simkin (2020). Non-Malleable Secret Sharing against Bounded Joint-Tampering Attacks in the Plain Model. Proceedings of CRYPTO |
|
| Farzin Salek, Anurag Anshu, Min-Hsiu Hsieh, R. Jain, Javier R. Fonollosa (2020). One-shot Capacity bounds on the Simultaneous Transmission of Classical and Quantum Information. IEEE Transactions on Information Theory 66 2141-2164 |
|
| A. Anshu, Mario Berta, R. Jain, M. Tomamichel (2020). Partially smoothed information measures. IEEE Transactions on Information Theory 66 5022-5036 |
|
| A. Anshu, Min-Hsiu Hsieh, R. Jain (2020). Noisy quantum state redistribution with promise and the Alpha-bit. IEEE Transactions on Information Theory 66 |
|
| R. Jain, Carl A. Miller, Yaoyun Shi (2020). Parallel Device-Independent Quantum Key Distribution. IEEE Transactions on Information Theory |
|
| M. Tomamichel, R. Jain, Mario Berta, Anurag Anshu (2019). A minimax approach to one-shot entropy inequalities. J. Math. Phys. 60 |
|
| 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 |
|
| Péter Kutas, Gábor Ivanyos, Lajos Rónyai (2019). Explicit equivalence of quadratic forms over $\\\\mathbb{F}_q(t)$. Finite Fields and Their Applications |
|
| Ivan Damgard, Maciej Lukasz Obremski, D. Aggarwal, E. Purwanto, Mark Simkin, Joao Ribeiro, Jesper Buus Nielsen (2019). Stronger Leakage-Resilient and Non-Malleable Secret-Sharing Schemes for General Access Structures. Proceedings of CRYPTO |
|
| Jesper Buus Nielsen, Nico Dottling, D. Aggarwal, E. Purwanto, Maciej Obremski (2019). Continuous non-malleable codes in the 8-split-state model. Springer EUROCRYPT 531-561 |
|
| M.Ray, 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 |
|
| 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 48 926-963 |
|
| Y. Wang, I.W. Primaatmaja, E. Lavie, A.Varvitsiotis, C.C.W. Lim (2019). Characterising the correlations of prepare-and-measure quantum networks. NPJ: Quantum Information 5 17 |
|
| A. Anshu, R. Jain, NA Warsi (2019). On the near-optimality of one-shot classical communication over quantum channels. J. Math. Phys. |
|
| A. Anshu, R. Jain, NA Warsi (2019). Building blocks for communication over noisy quantum networks. IEEE Transactions on Information Theory 65 1287-1306 |
|
| A. Anshu, R. Jain, NA Warsi (2019). A hypothesis testing approach for communication over entanglement assisted compound quantum channel. IEEE Transactions on Information Theory 65 2623-2636 |
|
| D. Aggarwal, Kai-Min Chung, H.H. Lin, T. Vidick (2019). A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries. Springer EUROCRYPT 442-469 |
|
| A. Anshu, R. Jain, NA Warsi (2019). Convex-Split and Hypothesis Testing Approach to One-Shot Quantum Measurement Compression and Randomness Extraction. IEEE Transactions on Information Theory 65 5905-5924 |
|
| Youming Qiao, Raghav Kulkarni, Gábor Ivanyos, Aarthi Sundaram, M. Santha (2018). On the Complexity of Trial and Error for Constraint Satisfaction Problems. Journal of Computer and System Sciences 92 48-64 |
|
| T. Lee, Gavin K. Brennen, D. Aggarwal, M. Tomamichel, M. Santha (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger 3 |
|
| Jamie Sikora, M. Santha, Sevag Gharibian, Justin Yirka, Aarthi Sundaram (2018). Quantum generalizations of the polynomial hierarchy with applications to QMA(2). International Symposium MFCS 1-16 |
|
| Péter Kutas, Gábor Ivanyos, Lajos Rónyai (2018). Computing explicit isomorphisms with full matrix algebras over $\mathbb{F}_q(x)$. Foundations of Computational Mathematics 18 381-397 |
|
| Youming Qiao, Gábor Ivanyos, K. V. Subrahmanyam (2018). Constructive noncommutative rank computation is in deterministic polynomial time. Computational Complexity 27 561–593 |
|
| K. V. Subrahmanyam, Gábor Ivanyos, Youming Qiao (2018). Constructive noncommutative rank computation is in deterministic polynomial time. Computational Complexity 27 561-593 |
|
| D. Aggarwal, N. Stephens-Davidowitz (2018). (Gap/S)ETH Hardness of SVP. ACM STOC |
|
| P. Mukhopadhyay, D. Aggarwal (2018). Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm. ISAAC |
|
| D. Aggarwal, A. Joux, A. Prakash, M. Santha (2018). A new public-key cryptosystem via Mersenne numbers. CRYPTO |
|
| 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 |
|
| Mathieu Bozzio, Adeline Orieux, Luis Trigo Vidarte, Isabelle Zaquine, I. Kerenidis, Eleni Diamanti (2018). Experimental investigation of practical unforgeable quantum money. New J. Phys. |
|
| T. Lee, Gavin K. Brennen, D. Aggarwal, M. Tomamichel, M. Santha (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 |
|
| 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 2357-2376 |
|
| A. Anshu, Min-Hsiu Hsieh, R. Jain (2018). Quantifying Resources in General Resource Theory with Catalysts. Phys. Rev. Lett. 121 |
|
| 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 |
|
| D. Aggarwal, Noah Stephens-Davidowitz (2018). Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP). Proceedings of the Symposium on Simplicity in Algorithms |
|
| A. Anshu, R. Jain, NA Warsi (2018). A generalized quantum Slepian-Wolf. IEEE Transactions on Information Theory 64 1436 - 145 |
|
| 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 |
|
| A. Anshu, R. Jain, NA Warsi (2018). A one-shot achievability result for quantum state redistribution. IEEE Transactions on Information Theory 64 1425 - 143 |
|
| A. Anshu, Ankit Garg, Aram Harrow, P. Yao (2018). Expected communication cost of distributed quantum tasks. IEEE Transactions on Information Theory |
|
| Mika Goos, R. Jain, Thomas Watson (2018). Extension Complexity of Independent Set Polytopes. SIAM Journal of Computing 47 241–269 |
|
| 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 |
|
| M. Santha, Juris Smotrovs, T. Lee, Aleksandrs Belovs, Andris Ambainis, Kaspars Balodis (2017). Separations in Query Complexity Based on Pointer Functions. JACM 64 |
|
| André Chailloux, I. Kerenidis (2017). Optimal bounds for quantum bit commitment. SIAM Journal of Computing 46 1647–167 |
|
| D. Aggarwal, M. Obremski, T. Kazana (2017). Inception makes non-malleable codes stronger. Theory of Cryptography |
|
| 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 |
|
| Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena (2017). Irreducibility and r-th root finding over finite fields. ISSAC 37-44 |
|
| 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, 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 |
|
| 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, 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, 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 |
|
| D. Aggarwal, O. Regev (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, 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 |
|
| A. Anshu, R. Jain, P. Mukhopadhyay, Ala Shayeghi, P. Yao (2016). New One Shot Quantum Protocols With Application to Communication Complexity. IEEE Transactions on Information Theory 62 7566 - 757 |
|
| 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 |
|
| Gabor Braun, R. Jain, T. Lee, Sebastian Pokutta (2016). Information-theoretic approximations of the nonnegative rank. Computational Complexity 26 147–197 |
|
| A. Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Goos, 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, 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, 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 |
|
| 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 |
|
| 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 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 (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 58 3664 - 366 |
|
| 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 |
|
| S Sekar, Maciej Lukasz Obremski, D. Aggarwal, B Obbattu, B Kanukurthi Non-malleable Codes with rate 1/3 via Rate Boosters. Annual ACM Symposium on Theory of Computing (STOC) |
|
| 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. |
|
| Gábor Ivanyos Finding hidden Borel subgroups of the general linear group. Quantum Information and Computation |
|
