Miklos Santha
Principal Investigator
+65 6516 6242
Miklos Santha

Short bio

Miklos Santha has received the Ph.D. degree in Mathematics from the Université Paris Diderot in 1983 and the Doctorat d'Etat in Computer Science from the Université Paris-Sud, Orsay in 1988. In 1988 he joined the Centre National de la Recherche Scientifique where he is Senior Researcher in Computer Science in the Research Institute on the Foundations of Computer Science (IRIF) in Paris. Since 2008 he is also Visiting Research Professor and Principal Investigator in the Centre for Quantum Technologies at the National University of Singapore. His research interests include quantum computing, randomness and complexity theory. He was a Humboldt Fellow in the Max Planck Institute in Saarbrücken from 1990 to 1991. In the last three decades he was the coordinator for the CNRS of several EU projects on randomized and quantum algorithms.

Website: http://www.liafa.univ-paris-diderot.fr/~santha/


  • 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
  • M. Santha, Y. Qiao, G. Ivanyos, A. Belovs, S.Yang. (2017). On the Polynomial Parity Argument complexity of the Combinatorial Nullstellensatz. Proceedings of the 32nd Computational Complexity Conference 30
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • M. Santha. (2015). Quantum and randomized query complexities. International Conference on Theory and Applications of Models of Computation 18-19
  • Anna Pappa, Niraj Kumar, Thomas Lawson, M. Santha, S. Zhang, Eleni Diamanti, I. Kerenidis. (2015). Nonlocality and conflicting interest games. Phys. Rev. Lett. 020401
  • T. Lee, Frederic Magniez, M. Santha. (2015). Improved quantum query algorithms for Triangle Finding and Associativity Testing. Algorithmica 1486-1502
  • 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
  • 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
  • G. Ivanyos, Marek Karpinski, Y. Qiao, M. Santha. (2014). Generalized Wong sequences and their applications to Edmonds. Proceedings of STACS 25 397-408
  • R. Kulkarni, M. Santha. (2013). Query complexity of matroids. CIAC 300-311
  • T. Decker, G. Ivanyos, M. Santha, Pawel Wocjan. (2013). Hidden Symmetry Subgroup Problems. SIAM Journal of Computing 42 1987-2007
  • 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
  • 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
  • Frederic Magniez, A. Nayak, Jeremie Roland, M. Santha. (2011). Search via Quantum Walk. SIAM Journal of Computing 1 142-164
  • R. Jain, H. Klauck, M. Santha. (2010). Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity. Inf. Proc. Lett 110 893-897
  • M. Santha, M. Szegedy. (2009). Quantum and classical query complexities of local search are polynomially related. Algorithmica 55 557-575
  • 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
  • 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
  • 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
  • Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, M. Santha, Aarthi Sundaram. On the Complexity of Trial and Error for Constraint Satisfaction Problems. Journal of Computer and System Sciences
  • G. Ivanyos, Marek Karpinski, M. Santha, Nitin Saxena, Igor Shparlinski. Polynomial Interpolation and Identity Testing from High Powers over Finite Fields. Algorithmica
  • Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, T. Lee, M. Santha, Juris Smotrovs. Separations in Query Complexity Based on Pointer Functions. JACM