Preprints

  • Frank Patrick Rebentrost, Yassine Hamoudi, M.Ray, Siyi Yang, Xin Wang, M. Santha. Quantum algorithms for hedging and the Sparsitron.
  • Antoine Joux, G. Ivanyos, M. Santha. Discrete logarithm and Diffie-Hellman problems in identity black-box groups.

Publications

  • 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, Frank Patrick Rebentrost. (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
  • R. Jain, D. Gavinsky, Jevgenijs Vihrovs, Swagato Sanyal, M. Santha, T. Lee, S.Kundu, H. Klauck. (2020). Quadratically Tight Relations for Randomized Query Complexity. Theory of Computing Systems 64 101-119
  • Frank Patrick Rebentrost, Yassine Hamoudi, M. Santha, Ansis Rosmanis. (2019). Quantum and Classical Algorithms for Approximate Submodular Function Minimization. Quantum Information and Computation 19 1325-1349
  • T. Lee, D. Gavinsky, Swagato Sanyal, M. Santha. (2019). A composition theorem for randomized query complexity via max conflict complexity. Automata, Languages, and Programming
  • M. Santha, T. Lee, M.Ray. (2019). Strategies for quantum races. ITCS 14
  • Raghav Kulkarni, Gábor Ivanyos, Aarthi Sundaram, M. Santha, Youming Qiao. (2018). On the Complexity of Trial and Error for Constraint Satisfaction Problems. Journal of Computer and System Sciences 92 48-64
  • Gavin K. Brennen, D. Aggarwal, M. Tomamichel, M. Santha, T. Lee. (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger 3
  • M. Santha, Sevag Gharibian, Justin Yirka, Aarthi Sundaram, Jamie Sikora. (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
  • Gavin K. Brennen, D. Aggarwal, M. Tomamichel, M. Santha, T. Lee. (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
  • Juris Smotrovs, T. Lee, Aleksandrs Belovs, Andris Ambainis, Kaspars Balodis, M. Santha. (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
  • Anupam Prakash, Gábor Ivanyos, M. Santha. On learning linear functions from subset and its applications in quantum computing. - None -
  • M. Santha, Sevag Gharibian, Justin Yirka, Aarthi Sundaram, Jamie Sikora. 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 -