2005   2004  2003  2001  2000  1999  1998  1997  1996 1995  1994  1992 

 1991  1990  1989  1988  1987  1986  1985  1984  1982  1981 

Papers in Journals:

 

2007

R. Bent, E. Upfal and P. van Hentenryck.  "`Online Stochastic Optimization Under Time Constraints"  Annals of Operations Research, 2007.

G. Pandurangan and E. Upfal.  ``Entropy-Based Bounds for Online Algorithms''
ACM Transactions on Algorithms, Vol. 3:1, 2007.
 

2007

G. Pandurangan, P. Raghavan, and E. Upfal. ``Using PageRank to Characterize Web Structure'', Internet Mathematics, Vol. 3:1 2006, pp. 1–20.
 

2005

A.  Anagnostopoulos, A. Kirsch and E. Upfal. Stability and Efficiency of a Random Local   Load BalancingProtocol. SIAM Journal on Computing, Vol. 34, 2005, pp. 616-639.

A. Anagnostopoulos, I. Kontoyiannis and E. Upfal. Steady state analysis of balanced-allocation routing.  Random Structures & Algorithms, Volume 26, 2005, pp. 446-467.

 
G. Pandurangan, P. Raghavan, and E. Upfal.  Using PageRank to Characterize Web Structure.  Internet Mathematics, Vol. 2, 2005, pp. 217-236.
 

2004   .

  A. Anagnostopoulos, R. Bent, E. Upfaland P. van Hentenryck.  A simple and determin­istic competitive algorithm for online facility locations. Information and Computation, Vol.194, 2004, pp.175–202.

 F. Preparata, S.A. Heath and E. Upfal. “Sequence Construction from nucleic-acid micro-array data”. in Analytical Techniques in DNA Sequencing, eds. B. Nunnally. Marcel Dekker Inc, 2004.

  A. Flaxman, Alan Frieze and E. Upfal “Efficient Communication in an Ad-hoc Net­work”. Journal of Algorithms, Vol. 52, pp. 1-7, 2004.

2003

 G. Pandurangan, P. Raghavan and E. Upfal. “Building Low-Diameter Peer-to-Peer Networks”. IEEE Journal on Selected Areas in Communication, Vol. 21, 995–1002, 2003.

 C. McDiarmid, M. Luzakand E. Upfal. “On-line routing of random calls”. Probability Theory and Related Fields, Vol. 125, 2003, pp. 457–482.

2001

 M. Hauskrecht, L. Ortiz, I. Tsochantaridis, and E. Upfal. “Efficient Methods for Computing Investment Strategies for Multi-Market Commodity Trading.” Applied Artificial Intelligence, Vol. 15, 2001, pp. 429–452.

 A.Z. Broder, A.M. Frieze, and E. Upfal. “A general approach to dynamic packet routing with bounded buffers.” J. of the ACM, Vol. 48, 2001, pp. 324–349.

N. Shavit, E. Upfal and A. Zemach. A Wait-Free Sorting Algorithm. Theory of Computer Systems, Vol. 34, 2001, pp. 519-544.

2000

G. Pandurangan and E. Upfal. Static and Dynamic Evaluation of QoS Properties. Journal of Interconnection Networks, Vol. 1, 2000, pp. 135–150.

F. P. Preparata and E. Upfal. “Sequencing-by-hybridization at the information-theory bound: an optimal algorithm”. Journal of Computational Biology, Vol. 7, 2000, pp. 621–630.

Y. Azar, A. Broder, A. Karlin, and E. Upfal. “Balanced allocations”. SIAM J. on Computing, Vol. 29, 2000, pp. 180–200.

1999

 A.L. N. Reddy and E. Upfal. “Real-Time Communication Scheduling in a Multicom­puter Video Server”. Journal of Parallel and Distributed Computing, Vol. 58, 1999, pp.425–445.

A.M. Frieze, F.P. Preparata, E. Upfal. “Optimal reconstruction of a sequence from its probes”.   Journal of Computational Biology, Vol. 6, 1999, pp. 361-368.

 A.Z. Broder, A.M. Frieze, and E. Upfal. “Static and dynamic path selection on ex­pander graphs: a random walk approach”. Random Structure & Algorithms, Vol. 14, 1999, pp. 87–109.

1998

 A. Pelc and E. Upfal. “Reliable fault diagnosis with few tests”.  Combinatorics, Probability and Computing, Vol. 7, 1998, pp. 323–333.

 N. Shavit, E. Upfal, and A. Zemach. “A steady state analysis of diffracting trees”. Special issue of Theory of Computing Systems, Vol 31, 1998, pp. 403-423.

 A.Z. Broder, A.M. Frieze, S. Suen, and E. Upfal. “Optimal construction of edge-disjoint paths in random graphs.” SIAM J. on Computing, Vol.28, 1998, pp.541–573.

P. Raghavan and E. Upfal. “Stochastic contention resolution with short delays”. SIAM J. on Computing, Vol. 28, 1998, pp. 709–719.

 

1997

J. Bruck, C.–T. Ho, S. Kipnis, E. Upfal, and D. Weathersby.  “Efficient algorithms for all-to-all communication in multiport message-passing systems”. IEEE Trans. on Parallel and Distributed Computing, Vol. 8, 1997, pp 1143–1156.

A. Borodin, P. Raghavan, B. Schieber, and E. Upfal. “How much can hardware help routing?” J. of the ACM, Vol. 44, 1997, pp. 726–741.

1996

S. Felperin, P. Raghavan, and E. Upfal, “A theory of wormhole routing in parallel computers”.   IEEE Transactions on Computing, Vol. 45, 1996, pp. 704–713.

E. Upfal, S. Felperin, and M. Snir. “Randomized routing with shorter paths”. IEEE Transactions on Parallel and Distributed Computing, Vol. 7, 1996, pp. 365-362.

1995

Andrei Z. Broder, Martin E. Dyer, Alan M. Frieze, Prabhakar Raghavan, and Eli Upfal. “The worst-case running time of the random simplex algorithm is exponential in the height”.  Information ProcessingLetters, Vol. 56, 1995, pp. 79–81.  

1994

E. Upfal, “Tolerating linear number of faults in networks of bounded degree”. Journal of Information and Computation, Vol. 114, 1994, pp. 312–320.

A. Broder, A. Frieze, and E. Upfal, “The existence and construction of edge disjoint paths on expander graphs”. SIAM J. on Computing, Vol. 23, 1994, pp. 976–989.

U. Feige, D. Peleg, P. Raghavan and E. Upfal, “Computing with noisy information”. SIAM J. on Computing, Vol. 23, 1994, pp. 1001–1018.

A. Broder, A. Frieze, E. Shamir, and E. Upfal, “Near-perfect token distribution”. Random Structure & Algorithms, Vol. 5, 1994, pp. 559–572.

A. Broder, A. Karlin, P. Raghavan and E. Upfal, “Trading space for time in undirected s − t connectivity”. SIAM J. on Computing, Vol. 23, 1994, pp. 324–334.

1992

E. Upfal, “An O(logN) deterministic packet routing algorithm”.  J. ofthe ACM, Vol. 39, 1992, pp.55-70.

1991

S. Assaf and E. Upfal, “Fault tolerant sorting network”. SIAM J. on Discrete Mathe­matics, Vol. 4, 1991, pp. 472-480.

 

1990

U. Feige, D. Peleg, P. Raghavan, and E. Upfal, “Randomized broadcast in networks”.   Random Structures & Algorithms, Vol. 1, 1990, pp. 447-460.

P. Peleg and E. Upfal, “A time-randomness tradeoff for oblivious routing”.  SIAM J. on Computing, Vol. 19, 1990, pp. 256-266.

1989

D. Peleg and E. Upfal, “A tradeoff between space and efficiency for routing tables”. J. the of ACM, Vol. 36, 1989, pp. 510-530.

  D. Peleg and E. Upfal, “The token distribution problem”.  SIAM J. on Computing, Vol.18, 1989, pp.229-243.

D. Peleg and E. Upfal, “The token distribution problem”.  SIAM J. on Computing, Vol.18, 1989, pp.229-243.

D. Peleg and E. Upfal, “Constructing disjoint paths on expander graphs”. Combina­torica, Vol. 9, 1989, pp. 289-313.

1988

A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal and A. Wigderson, “A tradeoff between search and update time for the implicit dictionary problem”. Theoretical Computer Science, Vol. 58, 1988, pp. 57-68.

A. Karlin and E. Upfal, “Parallel Hashing -an efficient implementation of shared memory”. J. ofthe ACM, Vol 35, 1988, pp. 876-892.

C. Dwork, D. Peleg, N. Pippenger and E. Upfal, “Fault tolerance in network of bounded degree”.  SIAM J. on Computing, Vol. 17, 1988, pp. 975-988.

R.M. Karp, E. Upfaland A. Wigderson, “The complexityof parallelsearch”.  In Special Issue of J. of Computer and System Sciences, Vol. 36, 1988, pp. 225-253.

1987

D. Peleg and E. Upfal, “The generalized packet routing problem”. Theoretical Com­puter Science, Vol.53, 1987, pp.281-293.

E. Shamir and E. Upfal, “A probabilistic approach to the load-sharing problem”. Jour­nal of Parallel and Distributed Computing, Vol.4, 1987, pp.521-530.

E. Upfal and A. Wigderson, “How to share memory in a distributed system”.  J. ofthe ACM, Vol.34, 1987, pp.116-127.

A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal and A. Wigderson, “Time space tradeoff for element distinctness”.  SIAM J. on Computing, Vol.16, 1987, pp.97-99.

1986

D. Dolev, E. Upfal and M. Warmuth, “The parallel complexity of scheduling with precedence constrains”.  Journal of Parallel and Distributed Computing, Vol. 3, 1986, pp.553-576.

R.M. Karp, E. Upfaland A. Wigderson, “Constructinga perfectmatching is in Random NC”.   Combinatorica, Vol. 6, 1986, pp. 35-48.

1985

E. Shamir and E. Upfal, “A fast parallel construction of disjoint paths in networks”. In Topics in the Theory of Computing, M. Karpinski and J. van Leeuwen ed. Annals of Discrete Mathematics, Vol 24, 1985, pp.141-154.

J. Schmidt-Pruzan, E. Shamir and E. Upfal, “Random hypergraphcoloringalgorithms and the weakchromatic number”. Journalof Graph Theory, Vol.8.1985, pp.347-362.

1984

E. Upfal, “Efficient schemes for parallel communication”. J. of the ACM, Vol. 31, 1984, pp. 507-517.

E. Shamir and E. Upfal, “Large regular factors in random graphs”. Annals of Discrete Math, Vol.20, 1984, pp.271-282.  

1982

E. Shamir and E. Upfal, “Sequential and distributed graph coloring algorithms with performance analyses in random graphs spaces”.  Journal of Algorithms, Vol. 5, 1982, pp.488-501.

E. Upfal, “Formal correctness proofs of a nondeterministic program”. Information ProcessingLetters, Vol.14, 1982, pp.86-92.

E. Shamir and E. Upfal, “One-factor in random graphs based on vertex choice”. Dis­crete Math. Vol. 41, 1982, pp. 281-286.

1981

E. Shamir and E. Upfal, “One factor in random graphs”.   Israel Journal of Math. Vol. 39, 1981, pp.296-302.