Miklos Santha
Principal Investigator
S15-04-02
cqtms@nus.edu.sg
+65 6516 6242
Miklos Santha

Preprints

  • Marco Tomamichel, Gavin K. Brennen, M. Santha, T. Lee, D. Aggarwal. Quantum attacks on Bitcoin, and how to protect against them.

Publications

  • 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
  • I. Arad, M. Santha, Aarthi Sundaram, Shengyu Zhang. (2018). Linear time algorithm for quantum 2SAT. Theory of Computing 1-27
  • 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
  • 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
  • , 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, 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
  • Gabor Ivanyos, Anupam Prakash, M. Santha. On learning linear functions from subset and its applications in quantum computing. - None -