Prof. Shlomo Moran
The Bernard Elkin Chair in Computer Science
- Contact information
- Office Hours:
- By appointment
- Research interests
- Algorithmic aspects of bioinformatics (with emphasis on phylogenetics); combinatorics and graph theory.
- Selected publications
IBARRA, O., and MORAN, S., "Probabilistic algorithms for deciding equivalence of straight line programs", Journal of the ACM, Vol. 30, No. 1, pp. 217-228, 1983.
IBARRA, O., MORAN, S., and HUI, R., "A generalization of the fast LUP matrix decomposition algorithm and applications", Journal of Algorithms, Vol. 3 pp. 45-56, 1982.
MORAN, S., "On the length of optimal TSP circuits in sets of bounded diameter", Journal of Combinatorial Theory, Series B, Vol. 37, No. 2, pp. 113-141, 1984.
MORAN, S., SNIR, M., and MANBER, U., "Applications of Ramsey's theorem to decision trees complexity", Journal of the ACM, Vol. 32, No. 4, pp. 938-949, 1985.
KLAWE, A.M.M., MORAN, S., SHOR, P.W., and WILBER, R., "Geometric applications of a matrix-searching algorithm", Algorithmica, Vol. 2, 1987, special issue of selected papers from the 2nd ACM symposium on Computational Geometry, pp. 195-208, 1986.
BABAI, L., and MORAN, S., "Arthur Merlin games: a randomized proof system, and a hierarchy of complexity classes", Journal of Computer and System Sciences, Vol. 36, 1988, special issue of selected papers from 17th ACM symposium on Theory of Computing, pp. 254-276, 1985.
BIRAN, O., MORAN, S., and ZAKS, S., "A combinatorial characterization of the distributed 1-solvable tasks", Journal of Algorithm, Vol. 11, 1990, special issue of selected papers from 7th ACM symposium on Principles of Distributed Computing, pp. 420-440, 1988.
DOLEV, S., ISRAELI, A., and MORAN, S., "Self stabilization of dynamic systems assuming only read/write atomicity", Distributed Computing, Vol. 7, No. 1, special issue on self stabilizing systems, pp. 3-16, 1993.
BODLAENDER, H., MORAN, S., and WARMUTH, M., "The distributed bit complexity of the ring: from the anonymous to the non-anonymous case", Information and Computation, Vol. 108, No. 1, pp. 34-50, 1994.
FISCHER, M.J., MORAN, S., RUDICH, S., and TAUBENFELD, G., "The wakeup problem", SIAM Journal of Computing, Vol. 25, No. 6, pp. 1332-1357, 1996.
ALLENBERG-NAVONY, N., ITAI, A., and MORAN, S., "Average and randomized complexity of distributed problems", SIAM Journal of Computing, Vol. 25, No. 6, pp. 1255-1267, 1996.
DINITZ, Y., MORAN, S., AND RAJSBAUM, S., "Bit complexity of breaking and achieving symmetry", 31st Annual ACM Symposium on theory of Computing, 1999.
EILAM, T., MORAN, S., and ZAKS, S., "Approximation algorithms for survivable optical networks", 14th International Symposium on Distributed Computing, 2000.
LEMPEL, R., and MORAN, S., "The stochastic approach for link-structure analysis to appear in ACM Transactions on Information Systems, 2001.