Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 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
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: postscript
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: pdf
M. Santha and M. Szegedy, Quantum and classical query complexities of local
search are polynomially related, 36th STOC, 494-501, 2004: pdf
F. Magniez, M. Santha and M. Szegedy, Quantum algorithms for the triangle
problem, 16th SODA, 1109-1117, 2005: pdf
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: pdf
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