Research

Quantum Computation and Complexity Theory: I'm interested in the connections between Quantum Computing and classical Complexity Theory, communication complexity, quantum cryptography, algorithms and Private Information Retrieval.

 

Employment

• 2006 - now: CNRS - University of Paris (XI)
  Permanent Researcher (CR) at the Laboratoire de Recherche en Informatique (LRI).
  

• 2009 - now: Center for Quantum Technologies, Singapore
  Visiting Professor
  

• 2004 - 2006: Massachusetts Institute of Technology
  Postdoctoral Associate in the Dept. of Mathematics
  Supervisor: Peter Shor

Education

• 2000 - 2004: University of California, Berkeley
  Ph.D. in Computer Science
  Thesis: Quantum Encodings and Applications to Locally Decodable Codes and Communication Complexity
  Adviser: Umesh Vazirani
  

• 1995 - 2000: National Technical University of Athens
  GRAD. in Electrical and Computer Engineering
  Adviser: Eustathios Zachos,
  GPA: 9.5/10.0 (1st out of ~1500)

• French Young Researcher Grant (ANR Jeunes Chercheurs), 2009-2012.
• European Marie Curie International Reintegration Grant, 2006-2008.
• University of California-Berkeley Regents Fellowship, 2000-2003
• Gold Medal for highest GPA among all graduating students at NTU, Athens.
• Scholarships from the Greek Fellowship Foundation for highest academic achievement, 1995-1999
• 9 awards in Greek National Math, Physics and Chemistry Competitions, 1990-1994

• ANR Jeunes Chercheurs Project "Quantum Cryptography" (Coordinator), 2009-2013.
• MAEE-CNRS STIC-Asie Project: "Foundations of Quantum Information and Computation (Coordinator), 20010-2012.
• JST-CNRS Strategic French-Japanese Cooperative Program on Information and Communications Technology (ICT) "Quantum Computation: Theory and Feasibility" (Coordinator), 2008-2010.
• ANR Defis "Quantum and Randomized Algorithms and Complexity", 2009-2013.
• CSQIP: EU-Canada Cooperation Programme: Collaborative student training in Quantum Information Processing, 2008-2011
• European Union FP7 STREP Project: "Quantum Computer Science", 2010-2013.

Teaching

• "Quantum Information and Applications" 2009-2010 at the Master Parisien de Recherche en Informatique (MPRI).
• "Quantum Information and Applications" 2008-2009, MPRI.
• "Quantum Information and Applications" 2007-2008, MPRI.
• "Quantum Information and Applications" 2006-2007, MPRI.

 

Students

PhD

• Andre Chailloux, 2007-now
• Anna Pappa, 2010-now

Master

• Andre Chailloux, 2007
• Anna Pappa, 2007

 

Committees

• Steering Committee: "GdR Information Quantique, Fondements & Applications", 2010-now
• Steering Committee: "GdR Informatique Mathematique", responsable du GT Informatique Quantique, 2010-now
• Steering Committee: GdR Information et Communication Quantique", 2005-2008.
• Program committee, Quantum Information Processing (QIP), 2011.
• Program committee, Quantum Information Processing (QIP), 2010.
• Program committee, International Conference on Quantum Information and Technology (ICQIT), 2009.
• Organizing committee: Conference on Computational Complexity (CCC), 2009

 

Publications

• Quantum commitments from complexity assumptions [pdf]
  Andre Chailloux, Iordanis Kerenidis, Bill Rosgen
  - quant-ph arXiv:1010.2793 , 2010.
  

• Long distance two-party quantum cryptography made simple [pdf]
  Iordanis Kerenidis, Stephanie Wehner
  - quant-ph arXiv:1008.0253 , 2010.
  

• Lower Bounds for Quantum Oblivious Transfer [pdf]
  André Chailloux, Iordanis Kerenidis, Jamie Sikora
  - [FSTTCS 10] Foundations of Software Technology and Theoretical Computer Science, 2010.

• On the power of a unique quantum witness [pdf]
  Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, Shengyu Zhang
  - [ICS 10] First Symposium on Innovations in Computer Science, 2010.
  - [QIP 10] Contributed talk at Quantum Information Processing, 2010

• Optimal quantum strong coin flipping [pdf]
  Andre Chailloux, Iordanis Kerenidis
  - [FOCS 09] 50th Annual Symposium on Foundations of Computer Science, 2009.
  - [QIP 10] Invited talk at Quantum Information Processing (by Andre Chailloux), 2010.

• Non-Local Box Complexity and Secure Function Evaluation [pdf]
  Marc Kaplan, Iordanis Kerenidis, Sophie Laplante, Jeremie Roland
  - [FSTTCS 09] Foundations of Software Technology and Theoretical Computer Science, 2009.

• Increasing the Power of the Verifier in Quantum Zero Knowledge [pdf]
  Andre Chailloux, Iordanis Kerenidis
  - [FSTTCS 08] Foundations of Software Technology and Theoretical Computer Science, 2008.

• Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model [pdf]
  Andre Chailloux, Dragos Florin Ciocan, Iordanis Kerenidis, Salil Vadhan
  - [TCC 08] Theory of Cryptography Conference, 2008.

• The role of Help in classical and quantum Zero Knowledge [pdf]
  Andre Chailloux, Iordanis Kerenidis
  - Cryptology ePrint 2007/421 and quant-ph/0711.4251, (superseded by the combined paper above), 2007.

• Exponential separations for one-way quantum communication complexity, with applications to cryptography [pdf]
  Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf
  - [SICOMP 08] SIAM Journal of Computing, Volume 38, Issue 5, pp. 1695-1708, 2008.
  - [STOC 07] Proceedings of ACM Symposium on Theory of Computating, 2007. [ps]
  - [QIP 07] Contributed talk at Quantum Information Processing, 2007.

• The one-way communication complexity of the Boolean Hidden Matching Problem [ps]
  Iordanis Kerenidis, Ran Raz
  - ECCC TR06-087 and quant-ph/0607173 (superseded by the combined paper above), 2006.

• Introduction to Quantum Information Theory [pdf]
  Iordanis Kerenidis
  - [ICITS 07, invited presentation] Second International Conference on Information Theoretic Security, Springer Lecture Notes in Computer Science, Volume 4883, p. 146-147.

• Quantum Multiparty communication complexity and circuit lower bounds [pdf]
  Iordanis Kerenidis
  - [MSCS 09, special TAMC issue] Mathematical Structures in Computer Science , Volume 19, pp 119-132 , 2009.
  - [TAMC 07] 4th Conference on Theory and Applications of Models of Computation, 2007 [ps]
  - [QIP 05] Invited talk at Quantum Information Processing, 2005.

• Statistical Zero Knowledge and quantum one-way functions [ps]
  Elham Kashefi, Iordanis Kerenidis
  - [TCS 07] Theoretical Computer Science, 378(1): 101-116 (2007).
  - [PQCrypto 06] PQCrypto 2006: International Workshop on Post-Quantum Cryptography [ps]
  

• On the optimality of quantum encryption schemes [ps]
  Iordanis Kerenidis, Daniel Nagaj
  - [J. Math Phys 06] Journal of Mathematical Physics, 47, 092102 2006. Also selected for the Virtual Journal of Quantum Information -- September 2006 Volume 6, Issue 9, 2006.
  

• Quantum Encodings and Applications to Locally Decodable Codes and Communication Complexity [ps]
  Iordanis Kerenidis 
  - PhD Thesis, UC Berkeley, 2004.

• Exponential separation of quantum and classical one-way communication complexity [ps]
  Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis
  - [SICOMP 08] SIAM Journal of Computing, Volume 38 Issue 1, Pages 366-384, 2008.
  - [STOC 04] Proceedings of ACM Symposium on Theory of Computating, 2004 [ps]
  - [QIP 04] Invited talk at Quantum Information Processing, 2004.

• Quantum Symmetrically-Private Information Retrieval [ps]
  Iordanis Kerenidis, Ronald de Wolf
  - [IPL 04] Information Processing Letters, Vol 90, Issue 3, Pages 109-114, May 2004.
  

• Weak coin flipping with small bias [ps]
  Iordanis Kerenidis, Ashwin Nayak
  - [IPL 04] Information Processing Letters, Vol. 89, Num. 3, p. 131-135, February 2004
  

• Exponential Lower Bound for 2-Query Locally Decodable Codes [ps]
  Iordanis Kerenidis, Ronald de Wolf
  - [JCSS 04, special STOC issue] Journal of Computer and System Sciences (JCSS), 69(3):395-420, 2004
  - [STOC 03] Proceedings of ACM Symposium on Theory of Computating, 2004 [ps]
  - [QIP 03] Invited talk at Quantum Information Processing (by Ronald de Wolf), 2003.

• Competitive Recommendation Systems [ps]
  Petros Drineas, Iordanis Kerenidis, Prabhakar Raghavan
  - [STOC 02] Proceedings of ACM Symposium on Theory of Computating, 2002.

• Quantum Clock synchronization with one qubit [ps]
  Chris Harrelson, Iordanis Kerenidis 
  - LANL archive cs.CC/0103021, March 2001