Miklos Santha's homepage

Miklos Santha
Directeur de Recherche

Address	Université Paris Sud Laboratoire de Recherche en Informatique Bat. 490 91405 Orsay FRANCE
Phone	+33 1 69 15 65 99
e-mail	lastname_AT_lri.fr

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

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

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

Grants

QAP
RESQ
QAIP
RAND-APX
QUIPROCONE
QIT