Miklos Santha
Principal Investigator
Centre for Quantum Technologies
Emeritus Research Director
French National Centre for Scientific Research (CNRS)
S15-04-02
Preprints
- Xin Wang, M. Santha, R.Patrick, Yassine Hamoudi, M.Ray, Siyi Yang. Quantum algorithms for hedging and the Sparsitron.
- G. Ivanyos, M. Santha, Antoine Joux. 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)
- M. Santha, R.Patrick, A.Luongo, João F. Doriguello, J.Bao. (2022). Quantum algorithm for stochastic optimal stopping problems with applications in finance. Proceedings of TQC 2:1-2:2:24
- T. Lee, Swagato Sanyal, M. Santha, T. Lee, D. Gavinsky. (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, T. Lee. (2021). On the cut dimension of a graph. Proceedings of the Computational Complexity Conference 200 15:1-15:35
- T. Lee, Shengyu Zhang, M. Santha, T. Lee. (2021). Quantum algorithms for graph problems with cut queries. ACM-SIAM Symposium on Discrete Algorithms (SODA) 939-958
- Xin Wang, Maharshi Ray, Yassine Hamoudi, R.Patrick, M. Santha, Siyi Yang. (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
- Swagato Sanyal, M. Santha, T. Lee, R. Jain, H. Klauck, D. Gavinsky, T. Lee, S.Kundu, Jevgenijs Vihrovs. (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, T. Lee, M. Santha, T. Lee. (2019). Strategies for quantum races. ITCS 14
- M. Santha, Youming Qiao, Raghav Kulkarni, Gábor Ivanyos, Aarthi Sundaram. (2018). On the Complexity of Trial and Error for Constraint Satisfaction Problems. Journal of Computer and System Sciences 92 48-64
- M. Santha, T. Lee, Gavin K. Brennen, D. Aggarwal, T. Lee, M. Tomamichel. (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger 3
- Aarthi Sundaram, Jamie Sikora, M. Santha, Sevag Gharibian, Justin Yirka. (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. Santha, T. Lee, Gavin K. Brennen, D. Aggarwal, T. Lee, M. Tomamichel. (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
- Kaspars Balodis, M. Santha, Juris Smotrovs, T. Lee, T. Lee, Aleksandrs Belovs, Andris Ambainis. (2017). Separations in Query Complexity Based on Pointer Functions. JACM 64
- D. Gavinsky, R. Jain, H. Klauck, S.Kundu, T. Lee, 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, A. Anshu, D. Gavinsky, R. Jain, S.Kundu, T. Lee, 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, A. Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Goos, R. Jain, Robin Kothari, T. Lee, 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, 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, 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, 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, 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 -
