All related publications need to mention the support from the project as follows: Supported by the French ANR Defis program under contract ANR-08-EMER-012 (QRAC project).

Journals

  1. T. Lee, F. Magniez and M. Santha (2012) A learning graph based quantum query algorithm for finding constant-size subgraphs. Chicago Journal of Theoretical Computer Science. (PDF) (BibTeX)
  2. G. Ivanyos, L. Sanselme and M. Santha (2012) An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups. Algorithmica, 62(1-2):480-498. (PDF) (BibTeX)
  3. D. Xiao (2012) Comment se mettre d'accord sur un rendez-vous ? La Recherche, 470(18-19). propos recueillis par Philippe Pajot (BibTeX)
  4. I. Kerenidis and S. Wehner (2012) Long distance two-party quantum crypto made simple. Quantum Information and Computation, 12:448-460. (PDF) (BibTeX)
  5. A. Pappa, A. Chailloux, S. Wehner, E. Diamanti and I. Kerenidis (2012) Multiparty entanglement verification resistant against dishonest parties. Physical Review Letters. (PDF) (BibTeX)
  6. Marc Renault and Adi Rosén (2012) On online algorithms with advice for the k-server problem. Theory of Computing systems, Published online November 2012. Special issue of WAOA 2011 (PDF) (BibTeX)
  7. R. Jain, I. Kerenidis, G. Kuperberg, M. Santha, O. Sattath and S. Zhang (2012) On the Power of a Unique Quantum Witness. Theory of Computing, 8:375-400. (PDF) (BibTeX)
  8. F. Magniez, A. Nayak, P. Richter and M. Santha (2012) On the hitting times of quantum versus random walks. Algorithmica, 63(1):91-116. (PDF) (BibTeX)
  9. S. Datta, R. Kulkarni, R. Tewari and N. Vinodchandran (2012) Space complexity of Bipartite Matching on bounded genus graphs. Journal of Computer and System Science, 78(3):765-779. (PDF) (BibTeX)
  10. H. Räcke and A. Rosén (2011) Approximation Algorithms for Time-Constrained Scheduling on Line Networks. Theory of Computing Systems, 49(4):834-856. Special issue of SPAA'09 (PDF) (BibTeX)
  11. Paz Carmi, Matthew J. Katz, Zvi Lotker and Adi Rosén (2011) Connectivity guarantees for wireless networks with directional antennas. Comput. Geom., 44(9):477-485. (PDF) (BibTeX)
  12. Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner and Thomas Vidick (2011) Entangled games are hard to approximate.. (PDF) (BibTeX)
  13. J. Silman, A. Chailloux, N. Aharon, I. Kerenidis, S. Pironio and S. Massar (2011) Fully Distrustful Quantum Bit Commitment and Coin Flipping. Physical Review Letters, 106(220501). (PDF) (BibTeX)
  14. M. Kaplan and S. Laplante (2011) Kolmogorov complexity and combinatorial methods in communication complexity. Theoretical Computer Science, 412(23):2524-2535. Special issue of TAMC'09 (PDF) (BibTeX)
  15. M. Kaplan, I. Kerenidis, S. Laplante and J. Roland (2011) Non-Local Box Complexity and Secure Function Evaluation. Quantum Information and Computation, 11(1):40-69. (PDF) (BibTeX)
  16. R. Kulkarni (2011) On the power of isolation in planar graphs. ACM Transactions on Computation Theory, 3(1). (PDF) (BibTeX)
  17. Y. Emek, P. Fraigniaud, A. Korman and A. Rosén (2011) Online Computation with Advice. Theoretical Computer Science, 412(24):2642-2656. Special issue of ICALP'09 (PDF) (BibTeX)
  18. A. Pappa, A. Chailloux, E. Diamanti and I. Kerenidis (2011) Practical quantum coin flipping. Physical Review A, 84:052305. (PDF) (BibTeX)
  19. A. Rosén and G. Scalosub (2011) Rate vs. Buffer Size - Greedy Information Gathering on the Line. ACM Transactions on Algorithms, 7(3):32. (PDF) (BibTeX)
  20. F. Magniez, A. Nayak, J. Roland and M. Santha (2011) Search via quantum walk. SIAM Journal on Computing, 40(1):142-164. (PDF) (BibTeX)
  21. J. Degorre, M. Kaplan, S. Laplante and J. Roland (2011) The communication complexity of non-signaling distributions. Quantum Information and Computation, 11(8):649-676. (PDF) (BibTeX)
  22. P. Hatami, R. Kulkarni and D. Pankratov (2011) Varations on the sensitivity conjecture. Theory of Computing, Graduate Surveys, 4. (PDF) (BibTeX)
  23. E. Fischer, F. Magniez and M. de Rougemont (2010) Approximate Satisfiability and Equivalence. SIAM Journal on Computing, 39(6):2251-2281. (PDF) (BibTeX)
  24. E. Gordon and A. Rosén (2010) Competitive Weighted Throughput Analysis of Greedy Protocols on DAGs. ACM Transactions on Algorithms, 6(3). (PDF) (BibTeX)
  25. Yuval Emek, Pierre Fraigniaud, Amos Korman and Adi Rosén (2010) On the additive constant of the k-server Work Function Algorithm. Inf. Process. Lett., 110(24):1120-1123. (PDF) (BibTeX)
  26. J. Naor, A. Rosén and G. Scalosub (2010) Online Time-Constrained Scheduling in Linear Networks. Journal of Discrete Algorithms, 8(4):346-355. (PDF) (BibTeX)
  27. R. Jain, H. Klauck and M. Santha (2010) Optimal direct sum results for deterministic and randomized decision tree complexity. Information Processing Letters, 110(20):893-897. (PDF) (BibTeX)
  28. L. Magnin, F. Magniez, A. Leverrier and N. Cerf (2010) Strong No-Go Theorem for Gaussian Quantum Bit Commitment. Physical Review A, 81(1):010302(R). (PDF) (BibTeX)
  29. Julia Kempe, Oded Regev and Ben Toner (2010) Unique Games with Entangled Provers are Easy. SIAM J. Comp., 39(7):3207-3229. (PDF) (BibTeX)
  30. K. Friedl, G. Ivanyos, M. Santha and Y. F. Verhoeven (2009) On the Black-Box Complexity of Sperner's Lemma. Theory of Computing Systems, 45(3):629-646. (PDF) (BibTeX)

Proceedings

  1. T. Lee F. Magniez and M. Santha (2013) Improved quantum query algorithms for triangle finding and associativity testing. In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, pages 1486-1502. (PDF) (BibTeX)
  2. S. Jeffery, R. Kothari and F. Magniez (2013) Nested quantum walks with quantum data structures. In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, pages 1474-1485. (PDF) (BibTeX)
  3. N. François and F. Magniez (2013) Streaming complexity of checking priority queues. In Proceedings of 30th Symposium on Theoretical Aspects of Computer Science. To appear (PDF) (BibTeX)
  4. I. Kerenidis and S. Zhang (2012) A quantum protocol for sampling correlated equilibria unconditionally and without a mediator. In Proceedings of 7th Theory of Quantum Computation, Communication and Cryptography (TQC). (PDF) (BibTeX)
  5. M. de Rougemont and P. Thao Cao (2012) Approximate answers to OLAP queries on streaming data warehouses. In Proceedings of 15th international workshop on Data warehousing and OLAP, pages 121-128. (PDF) (BibTeX)
  6. S. Peyronnet, M. de Rougemont and Y. Strozecki (2012) Approximate verification and enumeration problems. In Proceedings of 9th International Conference on Theoretical Aspects of Computing, pages 228-242. (PDF) (BibTeX)
  7. S. Laplante, V. Lerays and J. Roland (2012) Classical and quantum partition bound and detector inefficiency. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP). (PDF) (BibTeX)
  8. S. Datta, A. Gopalan, R. Kulkarni and R. Tewari (2012) Improved bounds for Bipartite Matching on surfaces. In Prooceedings of 29th Symposium on Theoretical Aspects of Computer Science (STACS). (PDF) (BibTeX)
  9. S. Jeffery, R. Kothari and F. Magniez (2012) Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. In Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP) Pages 522-532. (PDF) (BibTeX)
  10. I. Kerenidis, S. Laplante, V. Lerays, J. Roland and D. Xiao (2012) Lower bounds on information complexity via zero-communication protocols and applications. In Proceedings of 53rd Annual Symposium on Foundations of Computer Science (FOCS) Pages 500-509. (PDF) (BibTeX)
  11. C. Konrad, F. Magniez and C. Mathieu (2012) Maximum Matching in Semi-Streaming with Few Passes. In Proceedings of 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) Pages 231-242. (PDF) (BibTeX)
  12. A. Pappa, A. Chailloux, S. Wehner, E. Diamanti and I. Kerenidis (2012) Multiparty entanglement verification resistant against dishonest parties. In Proceedings of 7th Theory of Quantum Computation, Communication and Cryptography (TQC). (PDF) (BibTeX)
  13. G. Ivanyos, H. Klauck, T. Lee, M. Santha and R. de Wolf (2012) New bounds on the classical and quantum communication complexity of some graph properties. In Proceedings of 31st Foundations of Software Technology and Theoretical Computer Science, pages 148-159. (PDF) (BibTeX)
  14. D. Xiao (2012) Round-optimal black-box statistically binding selective-opening secure commitments. In Proceedings of 5th International Conference on Cryptology in Africa (AFRICACRYPT) Pages 395-411. (PDF) (BibTeX)
  15. Y. Emek, M. Halldórsson and A. Rosén (2012) Space-Constrained Interval Selection. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP) Pages 302-313. (PDF) (BibTeX)
  16. C. Konrad and F. Magniez (2012) Validating XML Documents in the Streaming Model with External Memory. In Proceedings of 15th International Conference on Database Theory (ICDT). (PDF) (BibTeX)
  17. David Xiao (2011) (Nearly) Round-Optimal Black-Box Constructions of Commitments Secure against Selective Opening Attacks. In Proc. 8th TCC, pages 541-558. (PDF) (BibTeX)
  18. Sevag Gharibian and Julia Kempe (2011) Approximation Algorithms for QMA-Complete Problems. In Proc. 26th IEEE Conference on Computational Complexity, pages 178-188. (PDF) (BibTeX)
  19. F. Magniez, A. Nayak, M. Santha and D. Xiao (2011) Improved bounds for the randomized decision tree complexity of recursive majority. In Proceedings of 38th International Colloquium on Automata, Languages and Programming. LNCS. (PDF) (BibTeX)
  20. G. Brassard, P. Høyer, K. Kalach, M. Kaplan, S. Laplante and L. Salvail (2011) Merkle puzzles in a quantum world. In Proceedings of Crypto'11, pages 385-404. (PDF) (BibTeX)
  21. Marc Renault and Adi Rosén (2011) On online algorithms with advice for the k-server problem. In Proc. WAOA, pages 198-210. (PDF) (BibTeX)
  22. André Chailloux and Iordanis Kerenidis (2011) Optimal bounds for quantum bit commitment. In Proc. of IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 354-362. (PDF) (BibTeX)
  23. Julia Kempe and Thomas Vidick (2011) Parallel repetition of entangled games. In Proc. 43rd ACM STOC, pages 353-362. (PDF) (BibTeX)
  24. André Chailloux, Iordanis Kerenidis and Bill Rosgen (2011) Quantum Commitments from Complexity Assumptions. In ICALP, pages 73-85. (PDF) (BibTeX)
  25. A. Ambainis, L. Magnin, M. Roetteler and J. Roland (2011) Symmetry-assisted adversaries for quantum state generation. In Proceedings of the 26th IEEE Conference on Computational Complexity, pages 167-177. (PDF) (BibTeX)
  26. F. Magniez, M. de Rougemont, M. Santha and X. Zeitoun (2011) The complexity of approximate Nash equilibrium in congestion games with negative delays. In Proceedings of 7th Workshop on Internet and Network Economics (WINE) Pages 266-277. (PDF) (BibTeX)
  27. I. Haitner, M. Mahmoody and D. Xiao (2010) A new sampling protocol and applications to basing cryptographic primitives on NP. In Proc. CCC'10, pages 76-87. (PDF) (BibTeX)
  28. Andris Ambainis, Julia Kempe and Or Sattath (2010) A quantum Lovász Local Lemma. In Proceedings of ACM STOC, pages 151-160. (PDF) (BibTeX)
  29. M. de Rougemont and A. Vieilleribière (2010) Approximate Structural Consistency. In SOFSEM '10. Springer Berlin / Heidelberg, pages 685-696. (PDF) (BibTeX)
  30. H. Krovi, F. Magniez, M. Ozols and J. Roland (2010) Finding is as easy as detecting for quantum walks. In Proceedings of 37st International Colloquium on Automata, Languages and Programming. LNCS, pages 540-551. (PDF) (BibTeX)
  31. L. Becchetti, I. Bordino, S. Leonardi and A. Rosén (2010) Fully Decentralized Computation of Aggregates over Data Streams. In Proc. of the 1st International Workshop on Novel Data Stream Pattern Mining Techniques. (PDF) (BibTeX)
  32. A. Chailloux (2010) Improved loss tolerant quantum coin flipping. In Proc. Asian Conference on Quantum Information Science. (PDF) (BibTeX)
  33. D. Xiao (2010) Learning to create is as hard as learning to appreciate. In Proc. COLT'10, pages 516-518. (PDF) (BibTeX)
  34. André Chailloux, Iordanis Kerenidis and Jamie Sikora (2010) Lower bounds for Quantum Oblivious Transfer. In Proc. FSTTCS, pages 157-168. (PDF) (BibTeX)
  35. Julia Kempe and Oded Regev (2010) No Strong Parallel Repetition with Entangled and Non-signaling Provers. In Proc. IEEE CCC'10, pages 7-15. (PDF) (BibTeX)
  36. R. Jain, I. Kerenidis, G. Kuperberg, M. Santha, O. Sattath and S. Zhang (2010) On the Power of a Unique Quantum Witness. In Proc. 1st Symposium on Innovation in Computer Science (ICS). (PDF) (BibTeX)
  37. M. Mahmoody and D. Xiao (2010) On the power of randomized reductions and the checkability of SAT. In Proc. CCC'10, pages 64-75. (PDF) (BibTeX)
  38. S. Dov Gordon, H. Wee, D. Xiao and A. Yerukhimovich (2010) On the round complexity of zero-knowledge proofs from one-way permutations. In Proc. Latincrypt'10. (PDF) (BibTeX)
  39. F. Magniez, C. Mathieu and A. Nayak (2010) Recognizing well-parenthesized expressions in the streaming model. In Proceedings of 42nd ACM Symposium on Theory of Computing, pages 261-270. (PDF) (BibTeX)
  40. Roy Kasher and Julia Kempe (2010) Two-source Extractors Secure Against Quantum Adversaries. In Proc. RANDOM'10, pages 656-669. (PDF) (BibTeX)
  41. M. Kaplan and S. Laplante (2009) Kolmogorov complexity and combinatorial methods in communication complexity. In Proceedings of the Conference on Theory and Applications of Models of Computation, pages 261-270. (PDF) (BibTeX)
  42. M. Kaplan, I. Kerenidis, S. Laplante and J. Roland (2009) Non-Local Box Complexity and Secure Function Evaluation. In FSTTCS 09. (PDF) (BibTeX)
  43. Y. Emek, P. Fraigniaud, A. Korman and A. Rosén (2009) On the Additive Constant of the $k$-server Work Function Algorithm. In Proc. WAOA'09, pages 128-134. (PDF) (BibTeX)
  44. F. Magniez, A. Nayak, P. Richter and M. Santha (2009) On the hitting times of quantum versus random walks. In Proceedings of 20th ACM-SIAM Symposium on Discrete Algorithms, pages 86-95. (PDF) (BibTeX)
  45. Y. Emek, P. Fraigniaud, A. Korman and A. Rosén (2009) Online Computation with Advice. In Proc. ICALP'09, pages 427-438. (PDF) (BibTeX)
  46. A. Chailloux and I. Kerenidis (2009) Optimal quantum strong coin flipping. In FOCS'09. (PDF) (BibTeX)
  47. M. de Rougemont and M. Tracol (2009) Statistical Analysis for Probabilistic Processes. In LICS '09, pages 299-308. (PDF) (BibTeX)
  48. J. Degorre, M. Kaplan, S. Laplante and J. Roland (2009) The communication complexity of non-signaling distributions. In Proc. MFCS'09, pages 270-281. (PDF) (BibTeX)
  49. Michel de Rougemont (2009) The value of sponsored ads for XML documents. In ICEB (International Conference on Electronic Business), Macau. (PDF) (BibTeX)

Others

  1. David Xiao (2011) Pseudo-aléa: objets et génération. Invited talk. Invited talk (PDF) (BibTeX)
  2. F. Magniez (2010) Application of Phase Estimation in Quantum Walks. Invited talk. Invited talk (BibTeX)
  3. S. Laplante (2010) Le plus grand des hasards : Surprises quantiques. (J.-F. Dars and A. Papillaut, Eds.) Belin. Book chapter (URL) (BibTeX)
  4. M. Santha (2010) Quantization of random walks: Search algorithms and hitting time. In Proc. 5th International Computer Science Symposium in Russia (CSR), page 343. LNCS. Invited talk (PDF) (BibTeX)
  5. Julia Kempe and Thomas Vidick (2010) Quantum Information, Computation and Cryptography.. (BibTeX)
  6. M. Santha (2009) Quantum Walk Based Search Algorithms.. (BibTeX)
  7. (2009) Special issue in Quantum Computation, Algorithmica 55(3). (F. Magniez and A. Nayak, Eds.) Springer. (BibTeX)

Link to the full file: qrac.bib