Randomized Algorithms

Applications of Probabilistic Concepts -- the Aggie connection

The application of probabilistic concepts in computer science is something that might happen right next door. The following references should give you an idea what is going on in Aggieland. It is needless to say that this list is incomplete. Hopefully, you will contribute soon!
  1. N.M. Amato, M.T. Goodrich, and E.A. Ramos, Linear time triangulation of a simple polygon made easier via randomization, Proceedings of the 16th Annual ACM Symposium on Computational Geometry (SoCG'00), pp. 201-212, 2000.
  2. N.M. Amato, M.T. Goodrich, and E.A. Ramos, Computing Faces in Segment and Simplex Arrangements, Proceedings of the 26th ACM Symposium on Theory of Computing (STOC), 1995, pp. 672-682.
  3. L. Cai, J. Chen, and J. Hastad, Circuit bottom fan-in and computational power, SIAM Journal on Computing 27, pp. 341-355, 1998.
  4. J. Chen, J., I.A. Kanj, and G. Wang, Hypercube network fault tolerance: a probabilistic approach, Proc. 2002 International Conference on Parallel Processing (ICPP'02), pp. 65-72, 2002.
  5. B.A. Coan and J.L. Welch, Transaction Commit in a Realistic Timing Model, Distributed Computing, Vol. 4, No. 2, pp. 87-103, 1990.
  6. S. Dolev, E. Schiller, and J.L. Welch, J. L., Random Walk for Self-Stabilizing Group Communication in Ad-Hoc Networks, Proc. 21st Symposium on Reliable Distributed Systems, Oct 2002.
  7. S. Dolev and J.L. Welch, Self-Stabilizing Clock Synchronization in the Presence of Byzantine Faults, 2nd Workshop on Self-Stabilizing Systems, May 1995.
  8. Y. Guan, X. Fu, R. Bettati, and W. Zhao, An Optimal Strategy for Anonymous Communication Protocols, Proceedings of the 22th International Conference on Distributed Computing Systems, Vienna, Austria, July 2002.
  9. Y. Guan, X. Fu, D. Xuan, P.U. Shenoy, R. Bettati, and W. Zhao, NetCamo: camouflaging network traffic for QoS-guaranteed mission critical applications, IEEE Transactions on Systems, Man, and Cybernetics, Vol 31, No. 4, July 2001, pp. 253 - 265.
  10. M.R. Hribar, V.E. Taylor, D.E. Boyce, Implementing parallel shortest path for parallel transportation applications, Parallel Computing, 31, pp. 1537-1568, 2001
  11. H. Lee and J.L. Welch, Randomized Shared Queues Applied to Distributed Optimization Algorithms, Proc. 12th International Symposium on Algorithms and Computation (ISAAC), December 2001.
  12. H. Lee and J.L. Welch, Applications of probabilistic quorums to iterative algorithms, Proc. 21st IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 21-30, April 2001.
  13. D. Leonard, V. Rai, D. Loguinov, On Lifetime-Based Node Failure and Stochastic Resilience of Decentralized Peer-to-Peer Networks, ACM Sigmetrics, 2005
  14. V.E. Taylor, R.L. Stevens, K.E. Arnold, Parallel molecular dynamics: Implications for massively parallel machines, J. Parallel and Distributed Computing, 45, pp. 166-175, 1997
  15. S. Voorhies, H. Lee, and A. Klappenecker, Randomized caching, probabilistic queuing, and denial of service attacks, preprint, 2003.
  • X. Wang, Y. Zhang, X. Li, and D. Loguinov, On Zone-Balancing of Peer-to-Peer Networks: Analysis of Random Node Join, ACM Sigmetrics, 2004.