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 Efficiency 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 Artificial Intelligence (UAI­2001), 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 Strate­gies for Multi-Market Commodity Trading.” The Fifth International Conference on Artificial 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 Computa­tional 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 Artificial 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 buffers”. 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 ex­pander 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 buffers.” Proceedings of the 37th IEEE Symp. on Foundations of Computer Science. Burlington, 1996, pp.390–399.

S. Preminger and E. Upfal. “Safe and efficient traffic laws for mobile robots”. Scan­dinavian 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 diffraction trees” Pro­ceedings 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 Efficient 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 deflection 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”. Pro­ceedings 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 Sym­posium 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. “Efficient 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”. Pro­ceedings 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 satisfiability and maximum satisfia­bility 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 Sympo­sium 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 eval­uating 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 tradeoff between space and efficiency 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 tradeoff 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 tradeoff 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 tradeoff between search and update time for the implicit dictionary problem”. International Colloquium on Automata, Languages and Programming. In Lecture Notes in Com­puter 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 efficient implementation of shared mem­ory”. 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 computa­tionally equivalent?” Proceedings of the ACM SIGACT Symp. on Theory of Comput­ing. 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”. Pro­ceedings 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 parallelcom­putation”. 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 net­works”. 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 ²N)beats”. Proceedings ofthe ACM SIGACT -SIGOPS Symp. on Principles of Distributed Computing. Ottawa, 1982, pp. 238-241. B1. E. Upfal, “Efficient Schemes for parallel communication”. Proceedings of the ACM SIGACT -SIGOPS Symp. on Principles of Distributed Computing. Ottawa, 1982, pp.55-59.

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