Miklos Santha's homepage

Miklos Santha
Directeur de Recherche

Postal Address	Université Paris Diderot - Paris 7 LIAFA Case 7014 75205 Paris Cedex 13 FRANCE
Office	Université Paris Diderot - Paris 7 LIAFA B. Sophie Germaine 75013 Paris 4th floor Office 4024
Phone	+33 1 57 27 94 03
e-mail	firstname.lastname_AT_gmail.com

Publications since 1995

Journals

M. Santha, On the Monte Carlo decision tree complexity of read-once formulae, Random Structures and Algorithms 6:1, 75-87, 1995: postscript
G. Brassard, C. Crépeau and M. Santha, Oblivious Transfers and Intersecting Codes, IEEE Transactions on Information Theory, 42: 6, 1769-1780, 1996: postscript
C. Dürr, H. LeThanh, and M. Santha, A decision procedure for well-formed linear quantum cellular automata, Random Structures and Algorithms 11:4, 381-394, 1997: postscript
M. Santha and S. Tan, Verifying the determinant in parallel, Computational Complexity 7:2, 128-151, 1998: postscript
W. Fernandez de la Vega, A. Frieze and Miklos Santha, Average -case analysis of the merging algorithm of Hwang and Lin, Algorithmica 22:4, 483-489, 1998: postscript
C. Bazgan, M. Santha and Zs. Tuza, On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs, Journal of Algorithms, 31, 249-268, 1999: postscript
C. Dürr and M. Santha, A decision procedure for unitary linear quantum cellular automata, SIAM J. of Computing, 31:4, 1076-1089, 2002: postscript
C. Bazgan, M. Santha and Zs. Tuza, Efficient approximation algorithms for the SUBSET-SUM EQUALITY problem, Journal of Computer and System Sciences, Vol 64, 160-170, 2002: postscript
M. Kiwi, F. Magniez and M. Santha, Approximate testing with relative error, Journal of Computer and System Sciences, 66:2, 371-392, 2003: pdf
F. Noilhan and M. Santha, Semantical counting circuits, Theory of Computing, Vol. 36, 217-229, 2003: pdf
G. Ivanyos, F. Magniez and M. Santha, Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem, International Journal of Foundations of Computer Science, 14:5, 723-739, 2003: pdf
H. Buhrman, C. Dürr, M. Heiligman, P. Hoyer, F. Magniez, M. Santha and R. de Wolf, Quantum algorithms for element distinctness, SIAM J. of Computing, 34:6, 1324-1330, 2005: pdf
W. van Dam, F. Magniez, M. Mosca and M. Santha, Self-Testing of universal and fault-tolerant sets of quantum gates, SIAM J. of Computing, 37:2, 611-629, 2007: pdf
F. Magniez, M. Santha and M. Szegedy, Quantum algorithms for the triangle problem, SIAM J. of Computing, 37:2, 413-424, 2007: pdf
K. Friedl, F. Magniez, M. Santha and P. Sen, Quantum testers for hidden group properties, Fundamenta Informaticae, 91:2, 325-340, 2009: pdf
M. Santha and M. Szegedy, Quantum and classical query complexities of local search are polynomially related, Algorithmica, 55:3, 557-575, 2009: pdf
K. Friedl, G. Ivanyos, M. Santha and Y. Verhoeven, On the black-box Complexity of Sperner's Lemma, Theory of Computing Systems, 45:3, 629-646, 2009: pdf
R. Jain, H. Klauck and M. Santha, Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity, Information Processing Letters, 110, 893-897, 2010: pdf
F. Magniez, A. Nayak, J. Roland and M. Santha, Search via quantum walk, SIAM J. of Computing, 40:1, 142-164, 2011: pdf
G. Ivanyos, L. Sanselme and M. Santha, An efficient quantum algorithm for the Hidden Subgroup problem in nil-2 groups, Algorithmica, 62:1-2, 480-498, 2012: pdf
F. Magniez, A. Nayak, P. Richter and M. Santha, On the hitting times of quantum versus random walks, Algorithmica, 63:1-2, 91-116, 2012: pdf
R. Jain, I. Kerenidis, G. Kuperberg, M. Santha, O. Sattah and S. Zhang, On the power of a unique quantum witness, Theory of Computing, Vol. 8, pp. 375--400, 2012: pdf
T. Lee, F. Magniez and M. Santha, Learning graph based quantum query algorithms for finding constant-size subgraphs. Chicago Journal of Theoretical Computer Science, Vol. 2012, Article 10, pp. 1-21, 2012: pdf
T. Decker, G. Ivanyos, M. Santha and P. Wocjan, Hidden symmetry subgroup problem. SIAM Journal on Computing, Vol. 42, No. 5, pp. 1987-2007, 2013: pdf
K. Friedl, G. Ivanyos, F. Magniez, M. Santha and P. Sen, Hidden Translation and Translating Coset in quantum computing. SIAM Journal on Computing, Vol. 43, No. 1, pp. 1-24, 2014: pdf
T. Decker, P. Hoyer, G. Ivanyos and M. Santha, Polynomial time quantum algorithms for certain bivariate hidden polynomial problems. Quantum Information and Computation, Vol. 14, No. 91, pp. 790-806, 2014: pdf
A. Pappa, N. Kumar, T. Lawson, M. Santha, S. Zhang, E. Diamanti and I. Kerenidis, Nonlocality and conflicting interest games, Physical Review Letters 114, 020401, 2015: pdf
G. Ivanyos, M. Karpinski, Y. Qiao and M. Santha, Generalized Wong sequences and their applications to Edmonds' problems, Journal of Computer and System Sciences, 81:7, pp. 1373-1386, 2015: pdf
M. Magniez, A. Nayak, M. Santha, J. Sherman, G. Tardos and D. Xiao, Improved bounds for the randomized decision tree complexity of recursive majority, Random Structures and Algorithms, 48:3, pp. 612--638, 2016: pdf

Proceedings

C. Dürr, H. LeThanh, and M. Santha, A decision procedure for well-formed linear quantum cellular automata, 13th STACS, LNCS 1046, 281-292, 1996 (see journal version)
C. Dürr and M. Santha, A decision procedure for unitary linear quantum cellular automata, 37th FOCS, 37-45, 1996 (see journal version)
C. Bazgan, M. Santha and Zs. Tuza, On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs, 15th STACS, LNCS 1373, 276-286, 1998 (see journal version)
C. Bazgan, M. Santha and Zs. Tuza, Efficient approximation algorithms for the SUBSET-SUM EQUALITY problem, 25th ICALP, LNCS 1443, 387-396, 1998 (see journal version)
M. Kiwi, F. Magniez and M. Santha, Approximate testing with relative error, 31st STOC, 51-60, 1999 (see journal version)
F. Noilhan and M. Santha, Semantical counting circuits, 4th CIAC, LNCS 1767, 87-101, 2000 (see journal version)
W. van Dam, F. Magniez, M. Mosca and M. Santha, Self-testing of universal and fault-tolerant sets of quantum gates, 32nd STOC, 688-696, 2000 (see journal version)
H. Buhrman, C. Dürr, M. Heiligman, P. Hoyer, F. Magniez, M. Santha and R. de Wolf, Quantum algorithms for element distinctness, 16th Complexity, 131-137, 2001 (see journal version)
G. Ivanyos, F. Magniez and M. Santha, Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem, 13th SPAA, 263-270, 2001 (see journal version)
M. Kiwi, F. Magniez and M. Santha, Exact and approximate testing/correcting of algebraic functions: a survey,Theoretical Aspects of Computer Science, LNCS 2292, 30-83, 2002: postscript
K. Friedl, G. Ivanyos, F. Magniez , M. Santha and P. Sen, Hidden Translation and Orbit Coset in Quantum Computing, 35th STOC, 1-9, 2003: pdf
K. Friedl, F. Magniez , M. Santha and P. Sen, Quantum testers for hidden group properties, 28th MFCS, LNCS 2747, 419-428, 2003 (see journal version)
M. Santha and M. Szegedy, Quantum and classical query complexities of local search are polynomially related, 36th STOC, 494-501, 2004 (see journal version)
F. Magniez, M. Santha and M. Szegedy, Quantum algorithms for the triangle problem, 16th SODA, 1109-1117, 2005 (see journal version)
K. Friedl, G. Ivanyos and M. Santha, Efficient testing of groups, 37th STOC, 157-166, 2005: postscript
K. Friedl, G. Ivanyos, M. Santha and Y. Verhoeven, On the black-box Complexity of Sperner's Lemma, 15th FCT, 245-257, 2005 (see journal version)
K. Friedl, G. Ivanyos, M. Santha and Y. Verhoeven, Locally 2-dimensional Sperner problem complete for the Polynomial Parity Argument classes, 6th CIAC, 380-391, 2006: pdf
G. Ivanyos, L. Sanselme and M. Santha, An efficient quantum algorithm for the Hidden Subgroup Problem in extraspecial groups, 24th STACS, LNCS 4393, 586-597, 2007: pdf
F. Magniez, A. Nayak, J. Roland and M. Santha, Search via quantum walk, 39th STOC, 575-584, 2007: pdf
G. Ivanyos, L. Sanselme and M. Santha, An efficient quantum algorithm for the Hidden Subgroup Problem in nil-2 groups, 8th LATIN, LNCS 4957, 759-771, 2008: pdf
M. Santha, Quantum walk based search algorithms, 5th TAMC, LNCS 4978, 31-46, 2008: pdf
S. Hemon, M. de Rougemont and M. Santha, Approximate Nash equilibria for multi-player games, 1st SAGT, LNCS 4997, 267-278, 2008: pdf
F. Magniez, A. Nayak, P. Richter and M. Santha, On the hitting time of quantum versus random walks, 20th SODA, 86-95, 2009: pdf
M. Santha, Quantization of random walks: Search algorithms and hitting time, 5th CSR, LNCS 6072, 343, 2010: pdf
F. Magniez, A. Nayak, M. Santha and D. Xiao, Improved bounds for the randomized decision tree complexity of recursive majority, 38th ICALP, 317-329, 2011: pdf
F. Magniez, M. de Rougemont, M. Santha and X. Zeitoun, The complexity of approximate Nash equilibrium in congestion games with negative delays, 7th WINE, 266-277, 2011: pdf
G. Ivanyos, H. Klauck, T. Lee, M. Santha and R. de Wolf, New bounds on the classical and quantum communication complexity of some graph properties. 31st FSTTCS, Hyderabad, 2012, LIPICS 18, pp. 148-159. pdf
T. Lee, F. Magniez and M. Santha, Improved quantum query algorithms for Triangle Finding and Associativity Testing, 24th ACM-SIAM SODA, New Orleans, pp. 1486-1502, 2013: pdf
R. Kulkarni and M. Santha, Query complexity of matroids. 8th CIAC, Barcelona, pp. 300-311, 2013: pdf
G. Ivanyos, M. Karpinski, Y. Qiao and M. Santha, Generalized Wong sequences and their applications to Edmonds' problems, 31st Symposium on Theoretical Aspects of Computer Science, Lyon, pp. 397-408, 2014: pdf
G. Ivanyos, R. Kulkarni, Y. Qiao, M. Santha and A. Sundaram, On the complexity of trial and error for constraint satisfaction problems, 41st International Colloquium on Automata, Languages and Programming, Copenhagen, pp. 663-675, 2014: pdf
T. Decker, G. Ivanyos, R. Kulkarni, Y. Qiao and M. Santha, An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group, 39th International Symposium on Mathematical Foundations of Computer Science, Budapest, pp. 226-238, 2014: pdf
R. Kothari, D. Racicot-Desloges and M. Santha, Separating decision tree complexity from subcube partition complexity, 19th International Workshop on Randomization and Computation, Princeton, pp. 915-930, 2015: pdf
G. Ivanyos and M. Santha, On solving systems of diagonal polynomial equations over finite fields, 9th International Frontiers of Algorithmics Workshop, Guilin, pp. 125-137, 2015: pdf
A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha and J. Smotrovs, Separations in query complexity based on pointer functions, 48th Annual Symposium on the Theory of Computing, Boston, pp. 800--813, 2016: pdf
I. Arad, M. Santha, A. Sundaram and S. Zhang, Linear time algorithm for quantum 2SAT, 43rd International Colloquium on Automata, Languages and Programming, Roma, pp. 15:1-15:14, 2016: pdf
I. Arad, A. Bouland, D. Grier, M. Santha, A. Sundaram and S. Zhang, On the complexity of probabilistic trials for hidden satisfiability problems, 41st International Symposium on Mathematical Foundations of Computer Science, Krakow, pp. 12:1-12:14, 2016: pdf
A. Anshu, A. Belovs, S. Ben-David, M. Gˆˆs, R. Kothari, R. Jain, T. Lee and M. Santha, Separations in communication complexity using cheat sheets and information complexity, 57th IEEE Symposium on Foundations of Computer Science, New Brunswick, 2016: pdf

Postdoc

Offer

Grants

QALGO
DIQIP
RDAM

Former Grants

QCS
QAP
RESQ
QAIP