Miklos Santha
Principal Investigator
S15-04-02
cqtms@nus.edu.sg
+65 6516 6242
Miklos Santha http://www.liafa.univ-paris-diderot.fr/~santha/
Preprints
- M.Ray, Siyi Yang, Xin Wang, M. Santha, R.Patrick, Yassine Hamoudi. Quantum algorithms for hedging and the Sparsitron.
- M. Santha, Antoine Joux, G. Ivanyos. Discrete logarithm and Diffie-Hellman problems in identity black-box groups.
Publications
- Jonathan Allcock, Yassine Hamoudi, A. Joux, M. Santha, Felix Klingelhöfer. (2022). Classical and quantum dynamic programming for Subset-Sum and variants. European Symposium on Algorithms (ESA)
- J.Bao, M. Santha, R.Patrick, A.Luongo, João F. Doriguello. (2022). Quantum algorithm for stochastic optimal stopping problems with applications in finance. Proceedings of TQC 2:1-2:2:24
- D. Gavinsky, Swagato Sanyal, M. Santha, T. Lee. (2022). A composition theorem for randomized query complexity via max conflict complexity. Theory of Computing 18
- M. Santha, S. Massar. (2021). Characterizing the intersection of QMA and coQMA. Quantum Information Processing 20(12), pp. 396
- Shengyu Zhang, M. Santha, Tongyang Li, T. Lee. (2021). On the cut dimension of a graph. Proceedings of the Computational Complexity Conference 200 15:1-15:35
- Shengyu Zhang, M. Santha, T. Lee. (2021). Quantum algorithms for graph problems with cut queries. ACM-SIAM Symposium on Discrete Algorithms (SODA) 939-958
- M. Santha, Siyi Yang, Xin Wang, Maharshi Ray, Yassine Hamoudi, R.Patrick. (2021). Quantum algorithms for hedging and the learning of Ising models. Phys. Rev. A 103
- M. Santha, S. Massar. (2021). Total Functions in QMA. Quantum Information Processing 20(1) pp. 1-35
- H. Klauck, D. Gavinsky, S.Kundu, Jevgenijs Vihrovs, Swagato Sanyal, M. Santha, T. Lee, R. Jain. (2020). Quadratically Tight Relations for Randomized Query Complexity. Theory of Computing Systems 64 101-119
- M. Santha, Ansis Rosmanis, R.Patrick, Yassine Hamoudi. (2019). Quantum and Classical Algorithms for Approximate Submodular Function Minimization. Quantum Information and Computation 19 1325-1349
- M.Ray, M. Santha, T. Lee. (2019). Strategies for quantum races. ITCS 14
- Aarthi Sundaram, M. Santha, Youming Qiao, Raghav Kulkarni, Gábor Ivanyos. (2018). On the Complexity of Trial and Error for Constraint Satisfaction Problems. Journal of Computer and System Sciences 92 48-64
- M. Tomamichel, M. Santha, T. Lee, Gavin K. Brennen, D. Aggarwal. (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger 3
- Justin Yirka, Aarthi Sundaram, Jamie Sikora, M. Santha, Sevag Gharibian. (2018). Quantum generalizations of the polynomial hierarchy with applications to QMA(2). International Symposium MFCS 1-16
- 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
- M. Tomamichel, M. Santha, T. Lee, Gavin K. Brennen, D. Aggarwal. (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger
- I. Arad, M. Santha, Aarthi Sundaram, Shengyu Zhang. (2018). Linear time algorithm for quantum 2SAT. Theory of Computing 1-27
- Aleksandrs Belovs, Andris Ambainis, Kaspars Balodis, M. Santha, Juris Smotrovs, T. Lee. (2017). Separations in Query Complexity Based on Pointer Functions. JACM 64
- 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 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
- 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 Goos, 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
- 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. (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
- M. Santha, Anupam Prakash, Gábor Ivanyos. On learning linear functions from subset and its applications in quantum computing. - None -
- Justin Yirka, Aarthi Sundaram, Jamie Sikora, M. Santha, Sevag Gharibian. Quantum generalizations of the polynomial hierarchy with applications to QMA(2). - None -
- Gabor Ivanyos, Anupam Prakash, M. Santha. On learning linear functions from subset and its applications in quantum computing. - None -
