| 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 |
| 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
- Calcul quantique 2001-02
- Complexite et algorithmes probabilistes 1995-96, 1996-97, notes de Dominique Rossin: postscript