Eli Upfal's Publications
2008
Broder, A., Kirsch, A., Kumar, R., Mitzenmacher, M., Upfal, E., and Vassilvitskii, S. The hiring problem and Lake Wobegon strategies. SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1184-1193.
Katriel, I., Kenyon-Mathieu, C., and Upfal, E. Commitment under uncertainity: Two-stage stochastic matching problems. Theoretical Computer Science 408 (2008), 213-223.
Kleinberg, R., Slivkins, A., and Upfal, E. Multi-armed Bandits in metric spaces. Proceedings of the 40th ACM Symposium on Theory of Computing (STOC 2008), pp. 681-690.
Radlinski, F., Chakrabarti, D., Kumar, R., and Upfal, E. Mortal Multi-Armed Bandits. Proceedings of the 22nd Annual Conference on Neural Information Processing Systems (NIPS 2008).
Slivkins, A., and Upfal, E. Adapting to a Changing Environment: the Brownian Restless Bandits. Proceedings of the 21st Annual Conference on Learning Theory (COLT), pp. 343-354.
2007
Chierichetti, F., Panconesi, A., Raghavan, P., M.Sozio, Tiberi, A., and Upfal, E. Finding Near Neighbors Through Cluster Pruning. Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principals of Database Systems (PODS).
Katriel, I., Kenyon-Mathieu, C., and Upfal, E. Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems. ICALP 2007, pp. 171-182.
Katriel, I., Sellmann, M., Upfal, E., and Hentenryck, P. V. Propagating Knapsack Constraints in Sublinear Time. Twenty-Second Conference on Artificial Intelligence (AAAI'07).
2006
Pandurangan, G., and Upfal, E. Entropy-Based Bounds for Online Algorithms. ACM Transactions on Algorithms (2006). [ pdf ]
2005
Sheffler, W., Upfal, E., Sedivy, J., and Noble, W. S. A learned comparative expression measure for Affymetrix GeneChip DNA microarrays. In Proceedings of the Computational Systems Bioinformatics Conference (Aug. 2005), pp. 144-154.
Anagnostopoulos, A., Kirsch, A., and Upfal, E. Stability and efficiency of a random local load balancing protocol. SIAM Journal on Computing 34 (2005), 616-639. [ pdf ]
Anagnostopoulos, A., Kontoyiannis, I., and Upfal, E. Steady state analysis of balanced-allocation routing. Random Structures & Algorithms 26 (2005), 446-467. [ pdf ]
Mitzenmacher, M., and Upfal, E. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
Pandurangan, G., Raghavan, P., and Upfal, E. Using PageRank to characterize web structure. Internet Mathematics 3.1 (2005), 120. [ pdf ]
Preparata, F., Upfal, E., and Heath, S. Sequence reconstruction from nucleic acid micro-array data. In Analytical Techniques for DNA Sequencing, B. Nunnally, Ed. M. Dekker, 2005, pp. 177-193.
2004
Anagnostopoulos, A., Bent, R., Upfal, E., and Hentenryck, P. V. A simple and deterministic competitive algorithm for online facility locations. Information and Computation 194, 2 (Nov. 2004), 175-202. [ pdf ]
Flaxman, A., Frieze, A., and Upfal, E. Efficient communication in an ad-hoc network. Journal of Algorithms 52 (2004), 1-7. [ pdf ]
2003
Anagnostopoulos, A., Kirsch, A., and Upfal, E. Stability and efficiency of a random local load balancing protocol. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS) (Nov. 2003), pp. 472-481. [ pdf ]
Anagnostopoulos, A., Kontoyiannis, I., and Upfal, E. The advantage of balanced-allocation routing for ATM networks. In Proceedings of the IEEE International Symposium on Information Theory (ISIT-2003) (June 2003). [ pdf ]
McDiarmid, C., Luzak, M., and Upfal, E. On-line routing of random calls. Probability Theory and Related Fields 125 (2003), 457-482. [ pdf ]
Pandurangan, G., Raghavan, P., and Upfal, E. Building low-diameter peer-to-peer networks. IEEE Journal on Selected Areas in Communication 21 (2003), 995-1002. [ pdf ]
Upfal, E. Tutorial: Performance analysis of dynamic network processes. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science (2003). [ pdf ]
2002
Pandurangan, G., Raghavan, P., and Upfal, E. Using PageRank to characterize web structure. In Proceedings of the 8th Annual International Conference on Combinatorics and Computing (COCOON) (2002), pp. 330-339. [ pdf ]
2001
Hauskrecht, M., and Upfal, E. A clustering approach to solving large stochastic planning problems. In Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI-2001) (Aug. 2001), pp. 219-226. [ pdf ]
Broder, A., Frieze, A., and Upfal, E. A general approach to dynamic packet routing with bounded buffers. J. of the ACM 48 (2001), 324-349. [ pdf ]
Hauskrecht, M., Ortiz, L., Tsochantaridis, I., and Upfal, E. Efficient methods for computing investment strategies for multi-market commodity trading. Applied Artificial Intelligence 15 (2001), 429-452. [ pdf ]
Pandurangan, G., Raghavan, P., and Upfal, E. Building low-diameter P2P networks. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (2001), pp. 492-499. [ pdf ]
Pandurangan, G., and Upfal, E. Can entropy characterize performance of online algorithms? In Proceedings of the 12th ACM Society for Industrial and Applied Mathematics Symposium on Discrete Algorithms (Jan. 2001), pp. 727-734. [ pdf ]
Shavit, N., Upfal, E., and Zemach, A. A wait-free sorting algorithm. Theory of Computer Systems 34 (2001), 519-544. [ pdf ]
2000
Hauskrecht, M., Ortiz, L., Tsochantaridis, I., and Upfal, E. Computing global strategies for multi-market commodity trading. In Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS2000) (Apr. 2000), pp. 159-166. [ pdf ]
Preparata, F., and Upfal, E. Sequencing-by-hybridization at the information-theory bound: an optimal algorithm. In Proceedings of the Fourth Annual International Conference on Computational Molecular Biology (Tokyo, Apr. 2000), pp. 245-253. [ pdf ]
Azar, Y., Broder, A., Karlin, A., and Upfal, E. Balanced allocations. SIAM Journal on Computing 29 (2000), 180-200. [ pdf ]
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A. S., and Upfal, E. Stochastic models for the web graph. In Proceedings of the 41th IEEE Symposium on Foundations of Computer Science (2000), pp. 57-65. [ pdf ]
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A. S., and Upfal, E. The web as a graph. In Proceedings of the 19th ACM Symposium on Principles of Database Systems (2000), pp. 1-10. [ pdf ]
Pandurangan, G., and Upfal, E. Static and dynamic evaluation of QoS properties. Journal of Interconnection Networks 1 (2000), 135-150. [ pdf ]
Preparata, F., and Upfal, E. Sequencing-by-Hybridization at the information-theory bound: an optimal algorithm. Journal of Computational Biology 7, 3-4 (2000), 621-630.
1999
Hauskrecht, M., Pandurangan, G., and Upfal, E. Computing near optimal strategies for stochastic investment planning problems. In Proceedings of the 16th International Joint Conference on Artificial Intelligence (July 1999), pp. 1310-1315. [ pdf ]
Preparata, F., Frieze, A., and Upfal, E. On the power of universal bases in sequencing by hybridization. In Proceedings of the Third Annual International Conference on Computational Molecular Biology (Lyon, France, Apr. 1999), pp. 295-301. [ pdf ]
Broder, A., Frieze, A., and Upfal, E. Static and dynamic path selection on expander graphs: a random walk approach. Random Structure & Algorithms 14 (1999), 87-109. [ pdf ]
Frieze, A. M., Preparata, F. P., and Upfal, E. Optimal reconstruction of a sequence from its probes. Journal of Computational Biology 6 (1999), 361-368. [ pdf ]
Luczak, M., and Upfal, E. Reducing network congestion and blocking probability through balanced allocation. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (1999), pp. 587-595. [ pdf ]
Pandurangan, G., and Upfal, E. Static and dynamic evaluation of QoS properties. In Proceedings of the 31st ACM Symposium on Theory of Computing (1999), pp. 566-573. [ pdf ]
Reddy, A., and Upfal, E. Real-time communication scheduling in a multicomputer video server. Journal of Parallel and Distributed Computing 58 (1999), 425-445. [ pdf ]
1998
Upfal, E. Design and analysis of dynamic processes: a stochastic approach. In Proceedings of the 6th Annual European Symposium on Algorithms (Venice, Italy, Aug. 1998), pp. 26-34. [ pdf ]
Broder, A., Frieze, A., and Upfal, E. Dynamic packet routing on arrays with bounded buffers. In Proceedings of the Third Latin American Symposium on Theoretical Informatics (LATIN '98) (Apr. 1998), pp. 273-281. [ pdf ]
Broder, A., Frieze, A., Suen, S., and Upfal, E. Optimal construction of edge-disjoint paths in random graphs. SIAM Journal on Computing 28 (1998), 541-573. [ pdf ]
Cole, R., Frieze, A., Maggs, B., Mitzenmacher, M., Richa, A., Sitaraman, R., and Upfal, E. On balls and bins with deletions. In Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (1998). [ pdf ]
Pelc, A., and Upfal, E. Reliable fault diagnosis with few tests. Combinatorics, Probability and Computing 7 (1998), 323-333. [ pdf ]
Raghavan, P., and Upfal, E. Stochastic contention resolution with short delays. SIAM J. on Computing 28 (1998), 709-719. [ pdf ]
Shavit, N., Upfal, E., and Zemach, A. A steady state analysis of diffracting trees. Theory of Computing Systems 31 (1998), 403-423. [ pdf ]
1997
Upfal, E. Stochastic analysis of dynamic processes. In Proceedings of the 11th International Symposium on Fundamentals of Computation Theory (Krakow, Poland, Sept. 1997), pp. 85-92.
Borodin, A., Raghavan, P., Schieber, B., and Upfal, E. How much can hardware help routing? Journal of the ACM 44 (1997), 726-741. [ pdf ]
Broder, A., Frieze, A., and Upfal, E. Static and dynamic path selection on expander graphs: a random walk approach. In Proceedings of the 29th ACM Symposium on Theory of Computing (1997), pp. 531-539. [ pdf ]
Bruck, J., Ho, C.-T., Kipnis, S., Upfal, E., and Weathersby, D. Efficient algorithms for all-to-all communication in multiport message-passing systems. IEEE Trans. on Parallel and Distributed Computing 8 (1997), 1143-1156. [ pdf ]
Shavit, N., Upfal, E., and Zemach, A. A wait-free sorting algorithm. In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing (1997), pp. 121-128. [ pdf ]
1996
Preminger, S., and Upfal, E. Safe and efficient traffic laws for mobile robots. In Proceedings of the Scandinavian Workshop on Algorithm Theory (July 1996), pp. 357-367.
Broder, A., and Upfal, E. Dynamic deflection routing on arrays. In Proceedings of the 28th ACM Symposium on Theory of Computing (1996), pp. 348-355. [ pdf ]
Broder, A., Frieze, A., Suen, S., and Upfal, E. An efficient algorithm for the vertex-disjoint paths problem in random graphs. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (1996), pp. 261-268. [ pdf ]
Broder, A., Frieze, A., and Upfal, E. A general approach to dynamic packet routing with bounded buffers. In Proceedings of the 37th IEEE Symposium on the Foundations of Computer Science (1996), pp. 390-399. [ pdf ]
Felperin, S., Raghavan, P., and Upfal, E. A theory of wormhole routing in parallel computers. IEEE Transactions on Computing 45 (1996), 704-713. [ pdf ]
Shavit, N., Upfal, E., and Zemach, A. A steady state analysis of diffraction trees. In Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures (1996), pp. 33-41. [ pdf ]
Upfal, E., Felperin, S., and Snir, M. Randomized routing with shorter paths. IEEE Transactions on Parallel and Distributed Computing 7 (1996), 356-362. [ pdf ]
1995
Broder, A. Z., Dyer, M. E., Frieze, A. M., Raghavan, P., and Upfal, E. The worst-case running time of the random simplex algorithm is exponential in the height. Information Processing Letters 56 (1995), 79-81. [ pdf ]
Raghavan, P., and Upfal, E. Stochastic contention resolution with short delays. In Proceedings of the 27th ACM Symposium on Theory of Computing (1995), pp. 229-237. [ pdf ]
1994
Azar, Y., Broder, A., Karlin, A., and Upfal, E. Balanced allocations. In Proceedings of the 26th ACM Symposium on Theory of Computing (1994), pp. 593-602. [ pdf ]
Broder, A., Frieze, A., and Upfal, E. The existence and construction of edge disjoing paths on expander graphs. SIAM Journal on Computing 23 (1994), 976-989.
Broder, A., Frieze, A., Shamir, E., and Upfal, E. Near-perfect token distribution. Random Structure & Algorithms 5 (1994), 559-572.
Broder, A., Frieze, A., Suen, S., and Upfal, E. Optimal construction of edge-disjoint paths in random graphics. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (1994), pp. 603-612.
Broder, A., Karlin, A., Raghavan, P., and Upfal, E. Trading space for time in undirected s-t connectivity. SIAM Journal on Computing 23 (1994), 324-334. [ pdf ]
Feige, U., Peleg, D., Raghavan, P., and Upfal, E. Computing with noisy information. SIAM Journal on Computing 23 (1994), 1001-1018. [ pdf ]
Raghavan, P., and Upfal, E. Efficient routing in all-optical networks. In Proceedings of the 26th ACM Symposium on Theory of Computing (1994), pp. 134-143. [ pdf ]
Upfal, E. On the theory of interconnection networks for parallel computers. In Proceedings of the 21st International Colloquium on Automata, Languages and Programming (1994), Springer, pp. 473-486. [ pdf ]
Upfal, E. Tolerating linear number of faults in networks of bounded degree. Journal of Information and Computation 114 (1994), 312-320.
1993
Borodin, A., Raghavan, P., Schieber, B., and Upfal, E. How much can hardware help routing? In Proceedings of the 25th ACM Symposium on Theory of Computing (1993), pp. 573-582. [ pdf ]
Broder, A., Frieze, A., and Upfal, E. On the satisfiability and maximum satisfiability on random 3-CNF Formulas. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (1993), pp. 322-330. [ pdf ]
Upfal, E., Felperin, S., and Snir, M. Randomized routing with shorter paths. In Proceedings of the Fifth Annual ACM Symposium on Parallel Algorithms and Architectures (1993), pp. 283-292. [ pdf ]
1992
Broder, A., Frieze, A., and Upfal, E. The existence and construction of edge disjoint paths on expander graphs. In Proceedings of the 24th ACM Symposium on Theory of Computing (1992), pp. 140-149.
Broder, A., Frieze, A., Shamir, E., and Upfal, E. Near-perfect token distribution. In Proceedings of the International Colloquium on Automata, Languages and Programming (1992), pp. 308-317.
Felperin, S., Raghavan, P., and Upfal, E. An experimental study of wormhole routing in parallel computers. In Parallel Architectures and Their Efficient Use, Proceedings of the First Heinz Nixdorf Symposium (Paderborn, Germany, 1992), pp. 156-165.
Felperin, S., Raghavan, P., and Upfal, E. A theory of wormhole routing in parallel computers. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science (1992), pp. 563-572. [ pdf ]
Upfal, E. An O(log N) deterministic packet routing algorithm. Journal of the ACM 39 (1992), 55-70. [ pdf ]
Upfal, E. Tolerating linear number of faults in networks of bounded degree. In Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing (1992), pp. 83-89. [ pdf ]
1991
Assaf, S., and Upfal, E. Fault tolerant sorting network. SIAM Journal on Discrete Mathematics 4 (1991), 472-480.
Broder, A., Karlin, A., Raghavan, P., and Upfal, E. On the parallel complexity of evaluating game-trees. In Proceedings of the Second ACM-SIAM Symposium on Discrete Algorithms (1991), pp. 404-413.
Rudolph, L., Slivkin-Allalouf, M., and Upfal, E. A simple load balancing scheme for task allocation in parallel machines. In Proceedings of the Third Annual ACM Symposium on Parallel Computing (1991), pp. 237-245. [ pdf ]
1990
Feige, U., Peleg, D., Raghavan, P., and Upfal, E. Randomized broadcast in networks. In Proceedings of the First International Symposium of the Special Interest Group on Algorithms (SIGAL 1990) (Aug. 1990), pp. 128-137.
Assaf, S., and Upfal, E. Fault tolerant sorting network. In Proceedings of the IEEE Symposium on Foundations of Computer Science (1990), pp. 275-284. [ pdf ]
Feige, U., Peleg, D., Raghavan, P., and Upfal, E. Computing with noisy information. In Proceedings of the ACM Symposium on Theory of Computing (1990), pp. 128-137.
Peleg, P., and Upfal, E. A time-randomness tradeoff for oblivious routing. SIAM Journal on Computing 19 (1990), 256-266.
1989
Broder, A., Karlin, A., Raghavan, P., and Upfal, E. Trading space for time in undirected s-t connectivity. In Proceedings of the ACM Symposium on Theory of Computing (1989), pp. 543-549.
Peleg, D., and Upfal, E. Constructing disjoint paths on expander graphs. Combinatorica 9 (1989), 289-313.
Peleg, D., and Upfal, E. A tradeoff between space and efficiency for routing tables. Journal of the ACM 36 (1989), 510-530.
Peleg, D., and Upfal, E. The token distribution problem. SIAM Journal on Computing 18 (1989), 229-243.
Upfal, E. An O(logN) deterministic packet routing algorithm. In Proceedings of the ACM Symposium on Theory of Computing (1989), pp. 241-250.
1988
Borodin, A., Fich, F., auf der Heide, F. M., Upfal, E., and Wigderson, A. A tradeoff between search and update time for the implicit dictionary problem. Theoretical Computer Science 58 (1988), 57-68.
Dwork, C., Peleg, D., Pippenger, N., and Upfal, E. Fault tolerance in network of bounded degree. SIAM Journal on Computing 17 (1988), 975-988.
Karlin, A., and Upfal, E. Parallel Hashing - an efficient implementation of shared memory. Journal of the ACM 35 (1988), 876-892.
Karp, R., Upfal, E., and Wigderson, A. The complexity of parallel search. Journal of Computer and System Sciences 36 (1988), 225-253.
Krizanc, D., Peleg, D., and Upfal, E. A time-randomness tradeoff for oblivious routing. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (1988), pp. 93-102.
Peleg, D., and Upfal, E. A tradeoff between space and efficiency for routing tables. In Proceedings of the ACM Symposium on Theory of Computing (1988), pp. 43-52.
1987
Borodin, A., Fich, F., auf der Heide, F. M., Upfal, E., and Wigderson, A. Time space tradeoff for element distinctness. SIAM Journal on Computing 16 (1987), 97-99.
Peleg, D., and Upfal, E. Constructing disjoint paths on expander graphs. In Proceedings of the ACM Symposium on Theory of Computing (1987), pp. 264-273.
Peleg, D., and Upfal, E. The generalized packet routing problem. Theoretical Computer Science 53 (1987), 281-293.
Shamir, E., and Upfal, E. A probabilistic approach to the load-sharing problem. Journal of Parallel and Distributed Computing 4 (1987), 521-530.
Upfal, E., and Wigderson, A. How to share memory in a distributed system. Journal of the ACM 34 (1987), 116-127.
1986
Borodin, A., Fich, F., auf der Heide, F. M., Upfal, E., and Wigderson, A. A tradeoff between search and update time for the implicit dictionary problem. In Proceedings of the International Colloquium on Automata, Languages and Programming (1986), pp. 50-59.
Borodin, A., Fich, F., auf der Heide, F. M., Upfal, E., and Wigderson, A. Time space tradeoff for element distinctness. In Proceedings of the 3rd Annual Symposium on Theoretical Aspects of Computer Science (1986), pp. 353-358.
Dolev, D., Upfal, E., and Warmuth, M. The parallel complexity of scheduling with precedence constrains. Journal of Parallel and Distributed Computing 3 (1986), 553-576.
Dwork, C., Peleg, D., Pippenger, N., and Upfal, E. Fault tolerance in networks of bounded degree. In Proceedings of the ACM Symposium on Theory of Computing (1986), pp. 370-379.
Karlin, A., and Upfal, E. Parallel Hashing - an efficient implementation of shared memory. In Proceedings of the ACM Symposium on Theory of Computing (1986), pp. 160-168.
Karp, R., Upfal, E., and Wigderson, A. Constructing a perfect matching is in Random NC. Combinatorica 6 (1986), 35-48.
Peleg, D., and Upfal, E. The token distribution problem. In Proceedings of the IEEE Symposium on Foundations of Computer Science (1986), pp. 418-427.
1985
Karp, R., Upfal, E., and Wigderson, A. The complexity of parallel computation on matroids. In Proceedings of the IEEE Symposium on Foundations of Computer Science (1985), pp. 541-550.
Karp, R., Upfal, E., and Wigderson, A. Constructing a perfect matching is in Random-NC. In Proceedings of the ACM Symposium on Theory of Computing (1985), pp. 22-32.
Karp, R., Upfal, E., and Wigderson, A. Are search and decision problems computationally equivalent? In Proceedings of the ACM Symposium on Theory of Computing (1985), pp. 464-475.
J.Schmidt-Pruzan, Shamir, E., and Upfal, E. Random hypergraph coloring algorithms and the weak chromatic number. Journal of Graph Theory 8 (1985), 347-362.
Shamir, E., and Upfal, E. A fast parallel construction of disjoint paths in networks. Topics in the Theory of Computing, Annals of Discrete Mathematics 24 (1985), 141-154.
1984
Dolev, D., Upfal, E., and Warmuth, M. Scheduling trees in parallel. In Algorithms and Architectures, Proceedings of the International Workshop on Parallel Computing and Very Large-Scale Integration (1984), pp. 91-102.
Shamir, E., and Upfal, E. Large regular factors in random graphs. Annals of Discrete Math 20 (1984), 271-282.
Upfal, E. Efficient schemes for parallel communication. Journal of the ACM 31 (1984), 507-517.
Upfal, E., and Wigderson, A. How to share memory in a distributed system. In Proceedings of the IEEE Symposium on Foundations of Computer Science (1984), pp. 171-180.
Upfal, E. Probabilistic relation between desirable and feasible models of parallel computation. In Proceedings of the ACM Symposium on Theory of Computing (1984), pp. 258-265.
1983
Shamir, E., and Upfal, E. Fast construction of disjoint paths in communication networks. In Proceedings of the Conference on Foundations on Computation Theory (1983).
1982
Shamir, E., and Upfal, E. N - processors graphs distributively achieve Perfect Matching in 0(log2N) beats. In Proceedings of the ACM SIGACT - SIGOPS Symposium on Principles of Distributed Computing (1982), pp. 238-241.
Shamir, E., and Upfal, E. One-factor in random graphs based on vertex choice. Discrete Math 41 (1982), 281-286.
Shamir, E., and Upfal, E. Sequential and distributed graph coloring algorithms with performance analyses in random graphs spaces. Journal of Algorithms 5 (1982), 488-501.
Upfal, E. Efficient schemes for parallel communication. In Proceedings of the ACM SIGACT - SIGOPS Symposium on Principles of Distributed Computing (1982), pp. 55-59.
Upfal, E. Formal correctness proofs of a nondeterministic program. Information Processing Letters 14 (1982), 86-92.
1981
E.Shamir, and Upfal, E. One factor in random graphs. Israel Journal of Math 39 (1981), 296-302.
| Page Owner: Eli Upfal | Last Modified: Thu Sep 24 13:42:35 2009 |