Centre for Quantum Technologies Computer Science Group

Publications


Journals

  1. R. Jain. New binding-concealing trade-offs for quantum string commitment, Journal of Cryptology 24:4, pp. 579-592, 2008.
  2. R. Jain, A. Kolla, G. Midrijanis and B. Reichardt. On parallel composition of zero-knowledge proofs with black-box quantum simulators, Quantum Information and Computation 9:5-6, pp. 513-532, 2009.
  3. R. Jain and S. Zhang. New bounds on classical and quantum one-way communication complexity, Theoretical Computer Science, 410, pp. 2463-2477, 2009.
  4. R. Cleve, D. Gavinsky and R. Jain. Entanglement-resistant two-prover interactive proof systems and non-adaptive private information retrieval systems, Quantum Information and Computation, 9:7-8, pp. 648-656, 2009.
  5. R. Jain, J. Radhakrishnan and P. Sen. A new information-theoretic property about quantum states with an application to privacy in quantum communication, Journal of ACM, to appear, 2009.
  6. K. Friedl, F. Magniez, M. Santha and P. Sen. Quantum testers for hidden group properties, Fundamenta Informaticae, 91:2, pp. 325-340, 2009.
  7. M. Santha and M. Szegedy. Quantum and classical query complexities of local search are polynomially related, Algorithmica, 55:3, pp. 557-575, 2009.
  8. P. Harsha, R. Jain, D. Mc. Allester, J. Radhakrishnan. The communication complexity of correlation. IEEE Transactions on Information Theory, 2009. Extended abstract appeared in Proceedings of 22nd IEEE Conference on Computational Complexity (CCC), pp 10-23, 2007.
  9. K. Friedl, G. Ivanyos, M. Santha and Y. Verhoeven. On the black-box Complexity of Sperner's Lemma, Theory of Computing Systems, 45:3, pp. 629-646, 2009.
  10. Bill Rosgen. Computational distinguishability of degradable and antidegradable channels. Quantum Information and Computation, to appear, 2010.

Proceedings

  1. R. Jain, H. Klauck and A. Nayak. Direct product theorems for classical communication complexity via subdistribution bounds, 40th ACM Symposium on Theory of Computing, pp. 599-608, 2008.
  2. R. Jain, A. Nayak and Y. Su. A separation between divergence and Holevo information for ensembles, 4th Theory and Applications of Models of Computation, pp. 526-541, 2008.
  3. G. Ivanyos, L. Sanselme and M. Santha. An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups, 8th Latin American Symposium on Theoretical Informatics, LNCS 4957, pp. 759--771, 2008.
  4. M. Santha. Quantum walk based search algorithms, 5th International Conference on Theory and Applications of Models of Computation, LNCS 4978, pp. 31--46, 2008.
  5. S. Hemon, M. de Rougemont and M. Santha. Approximate Nash equilibria for multi-player games, 1st Symposium on Algorithmic Game Theory, LNCS 4997, pp. 267-278, 2008.
  6. F. Magniez, A. Nayak, P. Richter and M. Santha. On the hitting time of quantum versus random walks, 20th Symposium on Discrete Algorithms, pp. 86-95, 2009.
  7. R. Jain and H. Klauck. New results in the simultaneous message passing model via information theoretic techniques, 24th IEEE Conference on Computational Complexity, pp. 369-378. 2009.
  8. R. Jain and J. Watrous. Parallel approximation of non-interactive zero-sum quantum games, 24th IEEE Conference on Computational Complexity, pp. 243-253. 2009.
  9. R. Jain, S. Upadhyay and J. Watrous. Two-message quantum interactive proofs are in PSPACE, 50th Annual Symposium on Foundations of Computer Science, to appear, 2009.
  10. A. Chailloux and I. Kerenidis. Optimal quantum strong coin flipping, 50th Annual Symposium on Foundations of Computer Science, to appear, 2009.
  11. R. Jain, I. Kerenidis, M. Santha and S. Zhang. On the power of a unique quantum witness, 1st Annual Conference on Innovations in Computer Science (ICS), 2010.
  12. R. Jain, Z. Ji, S. Upadhyay and J. Watrous. QIP = PSPACE, The 42nd ACM Symposium on Theory of Computing (STOC), 2010. Recipient of the best paper award.
  13. R. Jain, H. Klauck, S. Zhang. Depth-Independent Lower bounds on Communication Complexity of Read-Once Boolean Functions, The 16th Annual International Computing and Combinatorics Conference (COCOON) 2010.
  14. Bill Rosgen. Testing non-isometry is QMA-complete. To appear in the proceedings of TQC 2010.
  15. H. Klauck. A Strong Direct Product Theorem for Disjointness. 42nd ACM Symposium on Theory of Computing (STOC), 2010.
  16. R. Jain, H. Klauck. The Partition Bound for Classical Communication Complexity and Query Complexity. The 25th IEEE Conference on Computational Complexity (CCC), 2010.

Preprints on quant-ph

  1. M. Kaplan, I. Kerenidis, S. Laplante and J. Roland. Non-Local Box Complexity and Secure Function Evaluation, arXiv:0903.2179.
  2. Rahul Jain, Ashwin Nayak. The space complexity of recognizing well-parenthesized expression. arXiv:0025567
  3. Rahul Jain, Hartmut Klauck, Miklos Santha. Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity. arXiv:1004.0105

Back