Design and Analysis of Algorithms
Project status: Active
Research Areas
People
| Claire Mathieu |
| Eli Upfal |
Publications
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 ]
Azar, Y., Broder, A., Karlin, A., and Upfal, E. Balanced allocations. SIAM Journal on Computing 29 (2000), 180-200. [ 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 ]
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 ]
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 ]
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 ]
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 ]
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 ]
Upfal, E. Tolerating linear number of faults in networks of bounded degree. Journal of Information and Computation 114 (1994), 312-320.
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 ]
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.
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 ]
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 ]
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.
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.
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.
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.
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.
Upfal, E., and Wigderson, A. How to share memory in a distributed system. Journal of the ACM 34 (1987), 116-127.
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.
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.
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.
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., 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.
Shamir, E., and Upfal, E. Fast construction of disjoint paths in communication networks. In Proceedings of the Conference on Foundations on Computation Theory (1983).
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. Formal correctness proofs of a nondeterministic program. Information Processing Letters 14 (1982), 86-92.
E.Shamir, and Upfal, E. One factor in random graphs. Israel Journal of Math 39 (1981), 296-302.
| Page Owner: Webmaster | Last Modified: Mon Oct 23 14:57:09 2006 |