** **__2003__
__2002__
__2001__
__
__**2000****
**
**
**__
____1999__
__1998__
__1997__
__
__**1996****
**
**
**__
____1995__
__1994__
__
____1993__

** **__1992__**
**
**
**__1991__
__1990__
__1989__
**
1988****
**
__
____1987__
__1986__
__1985__
__
__**1984****
**
**
**__1983__
__
____1982__

**Papers in Refereed Conferences:
**

**2009**

A. Kirsch, M. Mitzenmacher, A. Pietracaprina, G. Pucci, E. Upfal and F. Vandin.__ "An ____Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets____"__. PODS

A. Anagnostopoulos, R. Kumar, M. Mahdian and E. Upfal.* *__"Sort Me If You Can: How to Sort Dynamic Data____"__. ICALP

**2008**

A. Slivkins and Eli Upfal.

__"Adapting to a Changing Environment: the
Brownian Restless Bandits"__

{\sl Proceedings of the 21st Annual Conference
on Learning Theory (COLT 2008)}.

F. Radlinski, D. Chakrabarti, R. Kumar, E. Upfal.

"*Mortal Multi-Armed Bandits*". Proceedings of the
22nd Annual Conference on Neural Information
Processing Systems (NIPS 2008).

R. Kleinberg, A. Slivkins and Eli Upfal.

"*Multi-armed bandits in metric spaces*."
Proceedings of the 40th ACM Symposium on Theory
of Computing (STOC 2008), pp. 681-690.

A. Z. Broder, A. Kirsch, R. Kumar, M.
Mitzenmacher, E. Upfal and S. Vassilvitskii.

"The hiring problem and Lake Wobegon
strategies".

SODA '08: Proceedings of the nineteenth annual
ACM-SIAM symposium on Discrete algorithms,

2008, pp. 1184--1193.

**2007**

I. Katriel, M. Sellmann, E. Upfal, and P. Van
Hentenryck.

"Propagating Knapsack Constraints in Sublinear
Time.

Proceedings of the Twenty-Second Conference on
Artificial Intelligence, (AAAI’07),Vancouver,
Canada.

I. Katriel, C. Kenyon and E. Upfal.

"Commitment Under Uncertainty: Two-Stage
Stochastic Matching Problems".

Proceedings of the 34th International Colloquium
on Automata, Languages and Programming (ICALP),
Wrocaw, Poland. Luly, 2007.

F. Chierichetti, A. Panconesi, P.Raghavan, M.
Sozio, A. Tiberi and E. Upfal.

"Finding Near Neighbors Through Cluster
Pruning".

Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles
of Database Systems (PODS),

Beijing, China. June 10-15, 2007.

**2005**

Will Sheffler, Eli Upfal, John Sedivy and
William Stafford Noble.

"A learned comparative expression measure for
Affymetrix GeneChip DNA microarrays."

Proceedings of the Computational Systems Bioinformatics Conference, August
8-11, 2005, Stanford, CA. pp. 144-154.

**2003**

__
____A. Anagnostopoulos, A.
Kirsch and Eli Upfal. Stability and Eﬃciency
of a Random Local Load Balancing Protocol.
28th Annual
Symposium on Foundations of Computer Science (FOCS),
Boston, MA, November 2003. __

__
____A. Anagnostopoulos, I. Kontoyiannis and E.
Upfal. “The Advantage of Balanced-ation
Routing for ATM Networks”
2003 IEEE
International Symposium on Information Theory
(ISIT-2003), Yokohama, Japan, June 2003.
__

**2002**

__G. Pandurangan,
P. Raghavan, and E. Upfal. “Using PageRank to
Characterize Web Structure”,
Proceedings ofthe
8th Annual International Conference on
Combinatorics and Computing (COCOON),
Singapore, 2002, LNCS 2387, Springer-Verlag ,
pages 330-339. __

**2001**

__Gopal Pandurangan, Prabhakar Raghavan and Eli Upfal.
“Building Low-diameter P2P Networks”.
42nd Annual
Symposium on Foundations of Computer Science,
Las Vegas, Nevada, 2001, pp. 492–499. __

__M. Hauskrecht and E. Upfal. “A Clustering Approach to
Solving Large Stochastic Planning Problems”.
17th Conference on
Uncertainty in Artiﬁcial Intelligence (UAI2001),
August 2001. __

__G. Pandurangan and E. Upfal. “Can Entropy Characterize
Performance of Online Algorithms?”
12th ACM-SIAM
Symposium on Discrete Algorithms, January
2001. __

**2000**

__R. Kumar, P. Raghavan,
S. Rajagopalan, D. Sivakumar, A. Tomkins, and
Eli Upfal. “Stochastic models for the Web
graph.” __ __Proceedings of the 41th IEEE Symp. on
Foundations of Computer Science.
__
__November 2000, pp.
57–65. __

M. Hauskrecht, L. Ortiz, I. Tsochantaridis, and E.
Upfal. “Computing Global Strategies for
Multi-Market Commodity Trading.”
The Fifth
International Conference on Artiﬁcial
Intelligence Planning & Scheduling (AIPS2000),
April 2000, pp. 159–166.

F.P. Preparata and E.Upfal.
“Sequencing-by-hybridization at the
information-theory bound: an optimal algorithm.”
Fourth Annual
International Conference on Computational
Molecular Biology. April 2000.

**1999**

__M. L. Luczak and E. Upfal. “Reducing
Network Congestion and Blocking Probability
Through Balanced Allocation”.
Proceedings of the
40th IEEE Symp. on Foundations of Computer
Science. 1999, New York, NY, pp.587-595.
__

__M. Hauskrecht, G. Pandurangan, and E. Upfal.
Computing Near Optimal Strategies for Stochastic
Investment Planning Problems.
Proceedings of the
16th International Joint Conference on Artiﬁcial
Intelligence, pp. 1310–1315, July 1999.
__

G. Pandurangan and E. Upfal. Static and Dynamic
Evaluation of QoS Properties.
Proceedings ofthe
31st ACM Symp. on Theory of Computing.
1999, Atlanta,
Georgia, pp.566–573.

__F.P. Preparata, A.M. Frieze, E. Upfal.On the Power of
Universal Bases in Sequencing by Hybridization.
Third Annual
International Conference on Computational
Molecular Biology. April 11 -14, 1999,
Lyon, France, pp. 295–301. __

**1998**

__R. Cole, A. Frieze, B.M. Maggs, M. Mitzenmacher, A. W.
Richa, R.K. Sitaraman, Eli Upfal. On Balls and
Bins with Deletions.
Randomization and
Approximation Techniques in Computer Science,
2nd Intl. Workshop, Random 98, Barcelona,
Spain, 1998. In LNCS 1518, pp. 145-158 .__

A. Broder, A. Frieze, and E. Upfal. “Dynamic packet
routing on arrays with bounded buﬀers”.
Third Latin
American Symposium on Theoretical Informatics
-LATIN ’98 Campinas, Brazil. April 1998.
In Springer-VerlagLecture
Notes in Computer Science 1380, pp
273–281, 1998.

**1997**

__N. Shavit, E. Upfal, and A. Zemach. “A Wait-Free
Sorting Algorithm”.
SIGACT SIGOPS
Symp. on Principles of Distributed Computing.
Santa Barbara, 1997, pp. 121–128. __

__A.Z. Broder, A.M.
Frieze, and E. Upfal. “Static and dynamic path
selection on expander graphs: a random walk
approach”. __ __Proceedings of the 29th ACM Symp. on Theory of
Computing. El Paso, 1997, pp.531–539.
__

**1996**

__A.Z. Broder, A.M. Frieze, and E. Upfal. “A general
approach to dynamic packet routing with bounded
buﬀers.”
Proceedings of the
37th IEEE Symp. on Foundations of Computer
Science. Burlington, 1996, pp.390–399.
__

S. Preminger and E. Upfal. “Safe and eﬃcient
traﬃc
laws for mobile robots”.
Scandinavian
Workshop on Algorithm Theory, Reykjavik,
July 1996. In Springer-Verlag Lecture Notes in Computer
Science 1097, pp 357–367, 1996.

N. Shavit, E. Upfal, and A. Zemach. “A steady state
analysis of diﬀraction
trees” Proceedings of the Eighth Annual ACM Symp. on
Parallel Algorithms and Architectures.
Padua, 1996, pp.33–41.

A.Z. Broder,
A.M. Frieze, S. Suen, and E. Upfal. “An Eﬃcient
Algorithm for the Vertex-Disjoint Paths Problem
in Random Graphs.” Proceedings of the 7th Annual ACM-SIAM Symposium
on Discrete Algorithms. Atlanta, 1996,
pp261–268.

A.Z. Broder
and E. Upfal. “Dynamic deﬂection routing on
arrays.” Proceedings ofthe 28th ACM Symp. on Theory of
Computing. Philadelphia, 1996,
pp.348–355.

**1995**

P. Raghavan and E. Upfal. “Stochastic contention
resolution with short delays”.
Proceedings of
the 27th ACM Symp. on Theory of Computing.
Las-Vegas, 1995, pp. 229–237.

**1994**

A.Z. Broder, A.M. Frieze, S. Suen, and E. Upfal.
“Optimal Construction of Edge-Disjoint Paths in
Random Graphs.” Proceedings ofthe 5th Annual ACM-SIAM Symposium
on Discrete Algorithms. Arlington, 1994,
pp. 603–612.

Y. Azar, A. Broder, A. Karlin, and E. Upfal. “Balanced
Allocations”. Proceedings of the 26th ACM Symp. on Theory of
Computing. Montreal, 1994, pp. 593–602.

P. Raghavan and E. Upfal. “Eﬃcient
routing in all-optical networks”.
Proceedings of the
26th ACM Symp. on Theory of Computing. Montreal, 1994, pp. 134–143.
\

**1993**

E. Upfal, S. Felperin, and M. Snir. “Randomized
routing with shorter paths”.
Proceedings of
the Fifth Annual ACM Symp. on Parallel
Algorithms and Architectures. Velen,
1993, pp.283–292.

A.Z. Broder, A.M.
Frieze, and E. Upfal. “On the satisﬁability and
maximum satisﬁability of random 3-CNF
Formulas.” Proceedings of of the Fourth Annual ACM-SIAM
Symp. on Discrete Algorithms.
Austin, 1993, pp. 322–330.

A. Borodin, P. Raghavan, B. Schieber, and E. Upfal.
“How much can hardware help routing?”
Proceedings of the
25th ACM Symp. on Theory of Computing. San Diego, 1993, pp. 573–582.

E. Upfal, “Tolerating linear number of
faults in networks of bounded degree”.
SIGACT -SIGOPS
Symp. on Principles of Distributed Computing.
Vancouver, 1992, pp. 83– 89.

**1992**

S. Felperin, P. Raghavan, and E. Upfal, “A theory of
wormhole routing in parallel computers”
Proceedings ofthe
33rd IEEE Symp. on Foundations of Computer
Science. Pittsburgh, 1992, pp. 563–572.

Broder, A. Frieze, E.
Shamir, and E. Upfal. “Near-perfect token
distribution”. International Colloquium
on Automata, Languages and Programming. In
Lecture Notes in Computer Science 623, Springer-Verlag,
1992, pp. 308–317.

A. Broder, A. Frieze,
and E. Upfal, “The existence and construction of
edge disjoint paths on expander graphs”.
Proceedings of the
24th ACM SIGACT Symp. on Theory of Computing.
Victoria,
1992, pp. 140–149.

**1991**

L. Rudolph, M. Slivkin-Allalouf, and E.
Upfal, ”A simple load balancing scheme for task
allocation in parallel machines”.
Proceedings ofthe
Third Annual ACM Symposium on Parallel
Computing. Hilton Head, South Carolina,
1991, pp. 237-245.

A. Broder, A. Karlin, P. Raghavan, and E.
Upfal, “On the parallel complexity of
evaluating game-trees”.
Proceedings of the
Second ACM-SIAM Symposium on Discrete Algorithms.San
Francisco, 1991, pp.404-413.

**1990**

U. Feige, D. Peleg, P. Raghavan, and E.
Upfal, “Randomized broadcast in networks”.
Proceedings ofthe
First SIGAL International Symposium on
Algorithms, Tokyo, Aug 1990. In
Springer-Verlag
Lecture Notes in Computer Science vol.
450 (T. Asano, T. Ibaraki, H. Imai and T.
Nishizeki, Editors), 1990, pp. 128-137.

S. Assaf and E. Upfal, “Fault tolerant
sorting network”. Proceedings of the IEEE Symposium on Foundations
of Computer Science. St.Louis, 1990,
pp.275–284.

U. Feige, D. Peleg, P. Raghavan and E. Upfal,
“Computing with noisy information”.
Proceedings of the
ACM SIGACT Symp. on Theory of Computing. Baltimore, 1990, pp.128-137.

**1989**

A. Broder, A.
Karlin, P. Raghavan and E. Upfal, “Trading space
for time in undirected
s−t
connectivity”.
Proceedings of the
ACM SIGACT Symp. on Theoryof Computing.
Seattle, 1989,
pp.543-549.

E. Upfal, “An O(logN)
deterministic packet routing algorithm”.
Proceedings of the
ACM SIGACT Symp. on Theory of Computing. Seattle, 1989, pp.241-250.

**1988**

D. Peleg and E. Upfal, “A tradeoﬀ
between space and eﬃciency
for routing tables”.
Proceedings of the
ACM SIGACT Symp. on Theory of Computing. Chicago, 1988, pp.43-52.

D. Krizanc, D. Pelegand E. Upfal, “Atime-randomness
tradeoﬀ
for oblivious routing.”
Proceedings of the
ACM SIGACT Symp. on Theory of Computing. Chicago, 1988, pp.93-102.

**1987**

D. Peleg and e. Upfal, “Constructing disjoint paths on
expander graphs.” Proceedings of the ACM SIGACT Symp. on Theory of
Computing. New York, 1987, pp. 264-273.

**1986**

A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal
and A. Wigderson, “Time space tradeoﬀ
for element distinctness”.
3rd Annual
Symposium on Theoretical Aspects of Computer
Science. France 1986. In
Lecture Notes in
Computer Science 210, Springer-Verlag,
1986, pp. 353-358.

A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal
and A. Wigderson, “A tradeoﬀ
between search and update time for the implicit
dictionary problem”.
International
Colloquium on Automata, Languages and
Programming. In Lecture Notes in Computer
Science 226, Springer-Verlag, 1986,
pp.50-59.

D. Peleg and E. Upfal, “The token
distribution problem”.
Proceedings of the
IEEE Symposium on Foundations of Computer
Science. Toronto, 1986, pp.418-427.

C. Dwork, D. Peleg, N. Pippenger and E.
Upfal, “Fault tolerance in networks of bounded
degree”. Proceedings of the ACM SIGACT Symp. on Theory of
Computing. Berkeley, 1986, pp. 370-379.

A. Karlin and E. Upfal, “Parallel Hashing
-an eﬃcient
implementation of shared memory”.
Proceedings of the
ACM SIGACT Symp. on Theory of Computing. Berkeley, 1986, pp. 160-168.

**1985**

R.M. Karp, E.
Upfal and A. Wigderson, “The complexity of
parallel computation on matroids”.
Proceedings ofthe
IEEE Symposium on Foundations of Computer
Science Portland, 1985, pp.541-550.

R.M. Karp, E. Upfal and A. Wigderson, “Are
search and decision problems computationally
equivalent?” Proceedings of the ACM SIGACT Symp. on Theory of
Computing. Providence, 1985, pp.464-475.

R.M. Karp, E. Upfaland A. Wigderson,
“Constructinga perfectmatching is in Random-NC”.
Proceedings ofthe
ACM SIGACT Symp. on Theoryof Computing. Providence, 1985, pp. 22-32.

**1984**

E. Upfal and A. Wigderson, “How to share
memory in a distributed system”.
Proceedings of
the IEEE Symposium on Foundations of Computer
Science. Palm Beach, 1984, pp. 171-180.

D. Dolev, E.
Upfal and M. Warmuth, “Scheduling trees in
parallel”. Proceedings of VLSI: Algorithms and
Architectures, International Workshop on
Parallel Computing and VLSI,
Italy 1984, pp.
91-102.

E. Upfal,
“Probabilistic relation between desirable and
feasible models of parallelcomputation”.
Proceedings of the
ACM SIGACT Symposium on Theory of Computing.
Washington,
1984, pp.258-265.

**1983**

E. Shamir and E. Upfal, “Fast construction
of disjoint paths in communication networks”.
Proceedings of the
Conference on Foundations of Computation Theory.
In Lecture Notes in Computer Science 158.
Springer 1983, pp. 428-438.

**1982**

E. Shamir and E. Upfal, “N -processors graphs
distributivelyachieve Perfect Matching in
O(log
^{
2}N)beats”.
Proceedings ofthe
ACM SIGACT -SIGOPS Symp. on Principles of
Distributed Computing. Ottawa, 1982, pp.
238-241. B1. E.
Upfal, “Eﬃcient
Schemes for parallel communication”.
Proceedings of the
ACM SIGACT -SIGOPS Symp. on Principles of
Distributed Computing.
Ottawa, 1982,
pp.55-59.

E. Upfal, “Eﬃcient
Schemes for parallel communication”.
Proceedings of the
ACM SIGACT -SIGOPS Symp. on Principles of
Distributed Computing.
Ottawa, 1982,
pp.55-59.