 |
Research Interests
Probabilistic analysis of algorithms
Randomized algorithms
Random data structures such as hashing, graphs, and trees.
Randomized allocation processes and load balancing
Publications
K. Dalal, L. Devroye. E. Malalla, and E. McLeish, “Two-way chaining with reassignment," SIAM Journal on Computing, Vol. 35 (2), pp 327--340, 2005. [PDF]
L. Devroye and E. Malalla, K. Dalal “Two-way linear probing,” submitted to Discrete Mathematics and Theoretical Computer Science.
L. Devroye and E. Malalla, “On the k-orientability of random graphs,” submitted.
E. Malalla, “Multiple-choice Hashing for Non-uniform Distributions,” submitted.
E. Malalla, Two-way Hashing with Separate Chaining and Linear Probing, Ph.D. thesis, School of Computer Science, McGill University, Canada, 2004. [PDF]
E. Malalla, “Non-uniform Randomized Balanced Allocations,” in: Proceedings of the 1st International Conference on Digital Communications and Computer Applications, March 19-23, pp. 1-13, 2007.
Multiple-Choice Allocation Processes
The multiple-choice allocation process has been discovered in 1994 by Azar, Broder, Karlin and Upfal. Since then, extensive research has been done to further analyze, generalize and expand the applications of such processes. Here is some of the history.
Ph.D. Theses:
M. D. Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, Ph.D. thesis, Computer Science Department, University of California at Berkeley, USA, 1996.
E. Malalla, Two-way Hashing with Separate Chaining and Linear Probing, Ph.D. thesis, School of Computer Science, McGill University, Canada, 2004. [PDF]
C. Weidling, Space Efficient Hash Tables with Ensured Constant Access Time, Ph.D. thesis, Computer Science Department, Technische Universität Ilmenau, 2004.
J. Cain, Random Graph Processes and Optimization, Ph.D. thesis, Department of Mathematics and Statistics, University of Melbourne, Australia, 2006.
D. Fernholz, Sparse Random Graphs: Methods, Structure, and Heuristics, Ph.D. thesis, Department of Computer Sciences, University of Texas at Austin, USA, 2007.
Research Papers:
Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal, "Balanced allocations," SIAM Journal on Computing, vol. 29:1, pp. 180--200, 2000. A preliminary version of this paper appeared in Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pp. 593--602, 1994.