2008 |
124 | EE | Aleksandrs Slivkins,
Eli Upfal:
Adapting to a Changing Environment: the Brownian Restless Bandits.
COLT 2008: 343-354 |
123 | EE | Deepayan Chakrabarti,
Ravi Kumar,
Filip Radlinski,
Eli Upfal:
Mortal Multi-Armed Bandits.
NIPS 2008: 273-280 |
122 | EE | Andrei Z. Broder,
Adam Kirsch,
Ravi Kumar,
Michael Mitzenmacher,
Eli Upfal,
Sergei Vassilvitskii:
The hiring problem and Lake Wobegon strategies.
SODA 2008: 1184-1193 |
121 | EE | Robert Kleinberg,
Aleksandrs Slivkins,
Eli Upfal:
Multi-armed bandits in metric spaces.
STOC 2008: 681-690 |
120 | EE | Robert Kleinberg,
Aleksandrs Slivkins,
Eli Upfal:
Multi-Armed Bandits in Metric Spaces
CoRR abs/0809.4882: (2008) |
119 | EE | Irit Katriel,
Claire Kenyon-Mathieu,
Eli Upfal:
Commitment under uncertainty: Two-stage stochastic matching problems.
Theor. Comput. Sci. 408(2-3): 213-223 (2008) |
2007 |
118 | | Martin Dietzfelbinger,
Shang-Hua Teng,
Eli Upfal,
Berthold Vöcking:
Probabilistic Methods in the Design and Analysis of Algorithms, 23.09. - 28.09.2007
Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2007 |
117 | | Irit Katriel,
Meinolf Sellmann,
Eli Upfal,
Pascal Van Hentenryck:
Propagating Knapsack Constraints in Sublinear Time.
AAAI 2007: 231-236 |
116 | EE | Irit Katriel,
Claire Kenyon-Mathieu,
Eli Upfal:
Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems.
ICALP 2007: 171-182 |
115 | EE | Flavio Chierichetti,
Alessandro Panconesi,
Prabhakar Raghavan,
Mauro Sozio,
Alessandro Tiberi,
Eli Upfal:
Finding near neighbors through cluster pruning.
PODS 2007: 103-112 |
114 | EE | Martin Dietzfelbinger,
Shang-Hua Teng,
Eli Upfal,
Berthold Vöcking:
07391 Abstracts Collection - Probabilistic Methods in the Design and Analysis of Algorithms.
Probabilistic Methods in the Design and Analysis of Algorithms 2007 |
113 | EE | Gopal Pandurangan,
Eli Upfal:
Entropy-based bounds for online algorithms.
ACM Transactions on Algorithms 3(1): (2007) |
2006 |
112 | | Gopal Pandurangan,
Prabhakar Raghavan,
Eli Upfal:
Using PageRank to Characterize Web Structure.
Internet Mathematics 3(1): (2006) |
2005 |
111 | EE | Will Sheffler,
Eli Upfal,
John Sedivy,
William Stafford Noble:
A Learned Comparative Expression Measure for Affymetrix GeneChip DNA Microarrays.
CSB 2005: 144-154 |
110 | EE | Aris Anagnostopoulos,
Ioannis Kontoyiannis,
Eli Upfal:
Steady state analysis of balanced-allocation routing.
Random Struct. Algorithms 26(4): 446-467 (2005) |
109 | EE | Aris Anagnostopoulos,
Adam Kirsch,
Eli Upfal:
Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input.
SIAM J. Comput. 34(3): 616-639 (2005) |
2004 |
108 | EE | Aris Anagnostopoulos,
Russell Bent,
Eli Upfal,
Pascal Van Hentenryck:
A simple and deterministic competitive algorithm for online facility location.
Inf. Comput. 194(2): 175-202 (2004) |
107 | EE | Abraham Flaxman,
Alan M. Frieze,
Eli Upfal:
Efficient communication in an ad-hoc network.
J. Algorithms 52(1): 1-7 (2004) |
2003 |
106 | EE | Eli Upfal:
Performance Analysis of Dynamic Network Processes.
FOCS 2003: 18- |
105 | EE | Aris Anagnostopoulos,
Adam Kirsch,
Eli Upfal:
Stability and Efficiency of a Random Local Load Balancing Protocol.
FOCS 2003: 472-481 |
2002 |
104 | EE | Gopal Pandurangan,
Prabhakar Raghavan,
Eli Upfal:
Using PageRank to Characterize Web Structure.
COCOON 2002: 330-339 |
2001 |
103 | | Gopal Pandurangan,
Prabhakar Raghavan,
Eli Upfal:
Building Low-Diameter P2P Networks.
FOCS 2001: 492-499 |
102 | EE | Gopal Pandurangan,
Eli Upfal:
Can entropy characterize performance of online algorithms?.
SODA 2001: 727-734 |
101 | EE | Milos Hauskrecht,
Eli Upfal:
A Clustering Approach to Solving Large Stochastic Matching Problems.
UAI 2001: 219-226 |
100 | | Milos Hauskrecht,
Luis E. Ortiz,
Ioannis Tsochantaridis,
Eli Upfal:
Efficient Methods for Computing Investment Strategies for Multi-Market Commodity Trading.
Applied Artificial Intelligence 15(5): 429-452 (2001) |
99 | EE | Andrei Z. Broder,
Alan M. Frieze,
Eli Upfal:
A general approach to dynamic packet routing with bounded buffers.
J. ACM 48(2): 324-349 (2001) |
2000 |
98 | | Milos Hauskrecht,
Luis E. Ortiz,
Ioannis Tsochantaridis,
Eli Upfal:
Computing Global Strategies for Multi-Market Commodity Trading.
AIPS 2000: 159-166 |
97 | | Ravi Kumar,
Prabhakar Raghavan,
Sridhar Rajagopalan,
D. Sivakumar,
Andrew Tomkins,
Eli Upfal:
Random graph models for the web graph.
FOCS 2000: 57-65 |
96 | EE | Ravi Kumar,
Prabhakar Raghavan,
Sridhar Rajagopalan,
D. Sivakumar,
Andrew Tomkins,
Eli Upfal:
The Web as a Graph.
PODS 2000: 1-10 |
95 | EE | Franco P. Preparata,
Eli Upfal:
Sequencing-by-hybridization at the information-theory bound: an optimal algorithm.
RECOMB 2000: 245-253 |
94 | | Franco P. Preparata,
Eli Upfal:
Sequencing-by-Hybridization at the Information-Theory Bound: An Optimal Algorithm.
Journal of Computational Biology 7(3-4): 621-630 (2000) |
93 | | Gopal Pandurangan,
Eli Upfal:
Static and Dynamic Evaluation of QoS Properties.
Journal of Interconnection Networks 1(2): 135-150 (2000) |
1999 |
92 | EE | Malwina J. Luczak,
Eli Upfal:
Reducing Network Congestion and Blocking Probability Through Balanced Allocation.
FOCS 1999: 587-595 |
91 | | Milos Hauskrecht,
Gopal Pandurangan,
Eli Upfal:
Computing Near Optimal Strategies for Stochastic Investment Planning Problems.
IJCAI 1999: 1310-1315 |
90 | EE | Franco P. Preparata,
Alan M. Frieze,
Eli Upfal:
On the power of universal bases in sequencing by hybridization.
RECOMB 1999: 295-301 |
89 | EE | Gopal Pandurangan,
Eli Upfal:
Static and Dynamic Evaluation of QoS Properties.
STOC 1999: 566-573 |
88 | | A. L. Narasimha Reddy,
Eli Upfal:
Real-Time Communication Scheduling in a Multicomputer Video Server.
J. Parallel Distrib. Comput. 58(3): 425-445 (1999) |
87 | | Alan M. Frieze,
Franco P. Preparata,
Eli Upfal:
Optimal Reconstruction of a Sequence from its Probes.
Journal of Computational Biology 6(3/4): (1999) |
86 | | Andrei Z. Broder,
Alan M. Frieze,
Eli Upfal:
Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach.
Random Struct. Algorithms 14(1): 87-109 (1999) |
85 | | Yossi Azar,
Andrei Z. Broder,
Anna R. Karlin,
Eli Upfal:
Balanced Allocations.
SIAM J. Comput. 29(1): 180-200 (1999) |
1998 |
84 | EE | Eli Upfal:
Design and Analysis of Dynamic Processes: A Stocastic Approach.
ESA 1998: 26-34 |
83 | EE | Andrei Z. Broder,
Alan M. Frieze,
Eli Upfal:
Dynamic Packet Routing on Arrays with Bounded Buffers.
LATIN 1998: 273-281 |
82 | EE | Richard Cole,
Alan M. Frieze,
Bruce M. Maggs,
Michael Mitzenmacher,
Andréa W. Richa,
Ramesh K. Sitaraman,
Eli Upfal:
On Balls and Bins with Deletions.
RANDOM 1998: 145-158 |
81 | | Wayne Niblack,
Xiaoming Zhu,
James L. Hafner,
Thomas M. Breuel,
Dulce B. Ponceleon,
Dragutin Petkovic,
Myron Flickner,
Eli Upfal,
Sigfredo I. Nin,
Sanghoon Sull,
Byron Dom,
Boon-Lock Yeo,
Savitha Srinivasan,
Dan Zivkovic,
Mike Penner:
Updates to the QBIC System.
Storage and Retrieval for Image and Video Databases (SPIE) 1998: 150-161 |
80 | | Andrzej Pelc,
Eli Upfal:
Reliable Fault Diagnosis with Few Tests.
Combinatorics, Probability & Computing 7(3): 323-333 (1998) |
79 | | Andrei Z. Broder,
Alan M. Frieze,
Stephen Suen,
Eli Upfal:
Optimal Construction of Edge-Disjoint Paths in Random Graphs.
SIAM J. Comput. 28(2): 541-573 (1998) |
78 | | Prabhakar Raghavan,
Eli Upfal:
Stochastic Contention Resolution With Short Delays.
SIAM J. Comput. 28(2): 709-719 (1998) |
77 | EE | Nir Shavit,
Eli Upfal,
Asaph Zemach:
A Steady State Analysis of Diffracting Trees.
Theory Comput. Syst. 31(4): 403-423 (1998) |
1997 |
76 | | Eli Upfal:
Stochastic Analysis of Dynamic Processes.
FCT 1997: 85-92 |
75 | | Nir Shavit,
Eli Upfal,
Asaph Zemach:
A Wait-Free Sorting Algorithm.
PODC 1997: 121-128 |
74 | EE | Andrei Z. Broder,
Alan M. Frieze,
Eli Upfal:
Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version).
STOC 1997: 531-539 |
73 | EE | Jehoshua Bruck,
Ching-Tien Ho,
Shlomo Kipnis,
Eli Upfal,
Derrick Weathersby:
Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems.
IEEE Trans. Parallel Distrib. Syst. 8(11): 1143-1156 (1997) |
72 | EE | Allan Borodin,
Prabhakar Raghavan,
Baruch Schieber,
Eli Upfal:
How much can hardware help routing?
J. ACM 44(5): 726-741 (1997) |
1996 |
71 | | Andrei Z. Broder,
Alan M. Frieze,
Eli Upfal:
A General Approach to Dynamic Packet Routing with Bounded Buffers (extended abstract).
FOCS 1996: 390-399 |
70 | | Sonne Preminger,
Eli Upfal:
Efficient Traffic Laws for Mobile Robots - Work in Progress (Avstract).
PODC 1996: 155 |
69 | | Andrei Z. Broder,
Alan M. Frieze,
Stephen Suen,
Eli Upfal:
An Efficient Algorithm for the Vertex-Disjoint Paths Problem in Random Graphs.
SODA 1996: 261-268 |
68 | | Nir Shavit,
Eli Upfal,
Asaph Zemach:
A Steady State Analysis of Diffracting Trees (Extended Abstract).
SPAA 1996: 33-41 |
67 | EE | Andrei Z. Broder,
Eli Upfal:
Dynamic Deflection Routing on Arrays (Preliminary Version).
STOC 1996: 348-355 |
66 | | Sonne Preminger,
Eli Upfal:
Safe and Efficient Traffic Laws for Mobile Robots.
SWAT 1996: 357-367 |
65 | | Sergio A. Felperin,
Prabhakar Raghavan,
Eli Upfal:
A Theory of Wormhole Routing in Parallel Computers.
IEEE Trans. Computers 45(6): 704-713 (1996) |
64 | EE | Eli Upfal,
Sergio A. Felperin,
Marc Snir:
Randomized Routing with Shorter Paths.
IEEE Trans. Parallel Distrib. Syst. 7(4): 356-362 (1996) |
1995 |
63 | EE | Prabhakar Raghavan,
Eli Upfal:
Stochastic contention resolution with short delays.
STOC 1995: 229-237 |
62 | EE | Andrei Z. Broder,
Martin E. Dyer,
Alan M. Frieze,
Prabhakar Raghavan,
Eli Upfal:
The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height.
Inf. Process. Lett. 56(2): 79-81 (1995) |
1994 |
61 | | Eli Upfal:
On the Theory of Interconnection Networks for Parallel Computers.
ICALP 1994: 473-486 |
60 | | Andrei Z. Broder,
Alan M. Frieze,
Stephen Suen,
Eli Upfal:
Optimal Construction of Edge-Disjoint Paths in Random Graphs.
SODA 1994: 603-612 |
59 | EE | Prabhakar Raghavan,
Eli Upfal:
Efficient routing in all-optical networks.
STOC 1994: 134-143 |
58 | EE | Yossi Azar,
Andrei Z. Broder,
Anna R. Karlin,
Eli Upfal:
Balanced allocations (extended abstract).
STOC 1994: 593-602 |
57 | | Eli Upfal:
Tolerating a Linear Number of Faults in Networks of Bounded Degree
Inf. Comput. 115(2): 312-320 (1994) |
56 | | Andrei Z. Broder,
Alan M. Frieze,
Eli Shamir,
Eli Upfal:
Near-perfect Token Distribution.
Random Struct. Algorithms 5(4): 559-572 (1994) |
55 | | Andrei Z. Broder,
Anna R. Karlin,
Prabhakar Raghavan,
Eli Upfal:
Trading Space for Time in Undirected s-t Connectivity.
SIAM J. Comput. 23(2): 324-334 (1994) |
54 | | Uriel Feige,
Prabhakar Raghavan,
David Peleg,
Eli Upfal:
Computing with Noisy Information.
SIAM J. Comput. 23(5): 1001-1018 (1994) |
53 | | Andrei Z. Broder,
Alan M. Frieze,
Eli Upfal:
Existence and Construction of Edge-Disjoint Paths on Expander Graphs.
SIAM J. Comput. 23(5): 976-989 (1994) |
1993 |
52 | | Andrei Z. Broder,
Alan M. Frieze,
Eli Upfal:
On the Satisfiability and Maximum Satisfiability of Random 3-CNF Formulas.
SODA 1993: 322-330 |
51 | EE | Eli Upfal,
Sergio Feleprin,
Marc Snir:
Randomized routing with shorter paths.
SPAA 1993: 273-282 |
50 | EE | Allan Borodin,
Prabhakar Raghavan,
Baruch Schieber,
Eli Upfal:
How much can hardware help routing?
STOC 1993: 573-582 |
1992 |
49 | | Sergio A. Felperin,
Prabhakar Raghavan,
Eli Upfal:
A Theory of Wormhole Routing in Parallel Computers (Extended Abstract)
FOCS 1992: 563-572 |
48 | | Sergio A. Felperin,
Prabhakar Raghavan,
Eli Upfal:
An Experimental Study of Wormhole Routing in Parallel Computers.
Heinz Nixdorf Symposium 1992: 156-165 |
47 | | Andrei Z. Broder,
Alan M. Frieze,
Eli Shamir,
Eli Upfal:
Near-perfect Token Distribution.
ICALP 1992: 308-317 |
46 | | Eli Upfal:
Tolerating Linear Number of Faults in Networks of Bounded Degree.
PODC 1992: 83-89 |
45 | | Andrei Z. Broder,
Alan M. Frieze,
Eli Upfal:
Existence and Construction of Edge Disjoint Paths on Expander Graphs
STOC 1992: 140-149 |
44 | EE | Eli Upfal:
An O(log(N)) Deterministic Packet-Routing Scheme.
J. ACM 39(1): 55-70 (1992) |
1991 |
43 | | Andrei Z. Broder,
Anna R. Karlin,
Prabhakar Raghavan,
Eli Upfal:
On the Parallel Complexity of Evaluating Game Trees.
SODA 1991: 404-413 |
42 | EE | Larry Rudolph,
Miriam Slivkin-Allalouf,
Eli Upfal:
A Simple Load Balancing Scheme for Task Allocation in Parallel Machines.
SPAA 1991: 237-245 |
41 | | Shay Assaf,
Eli Upfal:
Fault Tolerant Sorting Networks.
SIAM J. Discrete Math. 4(4): 472-480 (1991) |
1990 |
40 | | Shay Assaf,
Eli Upfal:
Fault Tolerant Sorting Network
FOCS 1990: 275-284 |
39 | | Uriel Feige,
David Peleg,
Prabhakar Raghavan,
Eli Upfal:
Randomized Broadcast in Networks.
SIGAL International Symposium on Algorithms 1990: 128-137 |
38 | | Uriel Feige,
David Peleg,
Prabhakar Raghavan,
Eli Upfal:
Computing with Unreliable Information (Preliminary Version)
STOC 1990: 128-137 |
37 | | Uriel Feige,
David Peleg,
Prabhakar Raghavan,
Eli Upfal:
Randomized Broadcast in Networks.
Random Struct. Algorithms 1(4): 447-460 (1990) |
36 | | David Peleg,
Eli Upfal:
A Time-Randomness Trade-Off for Oblivious Routing.
SIAM J. Comput. 19(2): 256-266 (1990) |
1989 |
35 | | Eli Upfal:
An O(log N) Deterministic Packet Routing Scheme (Preliminary Version)
STOC 1989: 241-250 |
34 | | Andrei Z. Broder,
Anna R. Karlin,
Prabhakar Raghavan,
Eli Upfal:
Trading Space for Time in Undirected s-t Connectivity
STOC 1989: 543-549 |
33 | | David Peleg,
Eli Upfal:
Constructng disjoint paths on expander graphs.
Combinatorica 9(3): 289-313 (1989) |
32 | EE | David Peleg,
Eli Upfal:
A trade-off between space and efficiency for routing tables.
J. ACM 36(3): 510-530 (1989) |
31 | | David Peleg,
Eli Upfal:
The Token Distribution Problem.
SIAM J. Comput. 18(2): 229-243 (1989) |
1988 |
30 | | David Peleg,
Eli Upfal:
A Tradeoff between Space and Efficiency for Routing Tables (Extended Abstract)
STOC 1988: 43-52 |
29 | | Danny Krizanc,
David Peleg,
Eli Upfal:
A Time-Randomness Tradeoff for Oblivious Routing (Extended Abstract)
STOC 1988: 93-102 |
28 | EE | Anna R. Karlin,
Eli Upfal:
Parallel hashing: an efficient implementation of shared memory.
J. ACM 35(4): 876-892 (1988) |
27 | | Richard M. Karp,
Eli Upfal,
Avi Wigderson:
The Complexity of Parallel Search.
J. Comput. Syst. Sci. 36(2): 225-253 (1988) |
26 | | Cynthia Dwork,
David Peleg,
Nicholas Pippenger,
Eli Upfal:
Fault Tolerance in Networks of Bounded Degree.
SIAM J. Comput. 17(5): 975-988 (1988) |
25 | | Allan Borodin,
Faith E. Fich,
Friedhelm Meyer auf der Heide,
Eli Upfal,
Avi Wigderson:
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
Theor. Comput. Sci. 58: 57-68 (1988) |
1987 |
24 | | David Peleg,
Eli Upfal:
Constructing Disjoint Paths on Expander Graphs (Extended Abstract)
STOC 1987: 264-273 |
23 | EE | Eli Upfal,
Avi Wigderson:
How to share memory in a distributed system.
J. ACM 34(1): 116-127 (1987) |
22 | | Eli Shamir,
Eli Upfal:
A Probabilistic Approach to the Load-Sharing Problem in Distributed Systems.
J. Parallel Distrib. Comput. 4(5): 521-530 (1987) |
21 | | Allan Borodin,
Faith E. Fich,
Friedhelm Meyer auf der Heide,
Eli Upfal,
Avi Wigderson:
A Time-Space Tradeoff for Element Distinctness.
SIAM J. Comput. 16(1): 97-99 (1987) |
20 | | David Peleg,
Eli Upfal:
The Generalized Packet Routing Problem.
Theor. Comput. Sci. 53: 281-293 (1987) |
1986 |
19 | | David Peleg,
Eli Upfal:
The Token Distribution Problem (Preliminary Version)
FOCS 1986: 418-427 |
18 | | Allan Borodin,
Faith E. Fich,
Friedhelm Meyer auf der Heide,
Eli Upfal,
Avi Wigderson:
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
ICALP 1986: 50-59 |
17 | | Allan Borodin,
Faith E. Fich,
Friedhelm Meyer auf der Heide,
Eli Upfal,
Avi Wigderson:
A Time-Space Tradeoff for Element Distinctness.
STACS 1986: 353-358 |
16 | | Anna R. Karlin,
Eli Upfal:
Parallel Hashing-An Efficient Implementation of Shared Memory (Preliminary Version)
STOC 1986: 160-168 |
15 | | Cynthia Dwork,
David Peleg,
Nicholas Pippenger,
Eli Upfal:
Fault Tolerance in Networks of Bounded Degree (Preliminary Version)
STOC 1986: 370-379 |
14 | | Richard M. Karp,
Eli Upfal,
Avi Wigderson:
Constructing a perfect matching is in random NC.
Combinatorica 6(1): 35-48 (1986) |
13 | | Danny Dolev,
Eli Upfal,
Manfred K. Warmuth:
The Parallel Complexity of Scheduling with Precedence Constraints.
J. Parallel Distrib. Comput. 3(4): 553-576 (1986) |
1985 |
12 | | Richard M. Karp,
Eli Upfal,
Avi Wigderson:
The Complexity of Parallel Computation on Matroids
FOCS 1985: 541-550 |
11 | | Richard M. Karp,
Eli Upfal,
Avi Wigderson:
Constructing a Perfect Matching is in Random NC
STOC 1985: 22-32 |
10 | | Richard M. Karp,
Eli Upfal,
Avi Wigderson:
Are Search and Decision Problems Computationally Equivalent?
STOC 1985: 464-475 |
1984 |
9 | | Eli Upfal,
Avi Wigderson:
How to Share Memory in a Distributed System (A Preliminary Version)
FOCS 1984: 171-180 |
8 | | Eli Upfal:
A Probabilistic Relation between Desirable and Feasible Models of Parallel Computation (A Preliminary Version)
STOC 1984: 258-265 |
7 | EE | Eli Upfal:
Efficient Schemes for Parallel Communication.
J. ACM 31(3): 507-517 (1984) |
6 | | Eli Shamir,
Eli Upfal:
Sequential and Distributed Graph Coloring Algorithms with Performance Analysis in Random Graph Spaces.
J. Algorithms 5(4): 488-501 (1984) |
1983 |
5 | | Eli Shamir,
Eli Upfal:
A Fast Construction oF Disjoint Paths in Communication Networks.
FCT 1983: 428-438 |
1982 |
4 | | Eli Shamir,
Eli Upfal:
N-Processors Graph Distributively Achieve Perfect Matchings in O(log²N) Beats.
PODC 1982: 238-241 |
3 | | Eli Upfal:
Efficient Schemes for Parallel Communication.
PODC 1982: 55-59 |
2 | EE | Eli Shamir,
Eli Upfal:
One-factor in random graphs based on vertex choice.
Discrete Mathematics 41(3): 281-286 (1982) |
1 | | Eli Upfal:
Formal Correctness Proofs of a Nondeterministic Program.
Inf. Process. Lett. 14(2): 86-92 (1982) |