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 175, rue du Chevaleret 75013 Paris 7th floor Office 7A26
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

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)
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
R. Jain, I. Kerenidis, G. Kuperberg, M. Santha, O. Sattath and S. Zhang, On the Power of a Unique Quantum Witness, 1st ICS, 2010: 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 Foundations of Software Technology and Theoretical Computer Science, 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 Symposium on Discrete Algorithms}, New Orleans, 2013, pp. 1486-1502: pdf

MPRI

Calcul quantique 2001-02
Complexite et algorithmes probabilistes 1995-96, 1996-97, notes de Dominique Rossin: postscript
Expose d'introduction au calcul quantique: pdf
Expose d'introduction aux marches quantiques: pdf

Postdoc

Offer

Grants

QCS
DIQIP
QRAC

Former Grants

QAP
RESQ
QAIP