Edith Cohen
- Research Area(s)
- Networking
- Algorithms and Theory
- Data Mining and Modeling
Co-Authors
Previous Publications
-
All-Distances Sketches
Encyclopedia of Algorithms (2015)
-
All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis
IEEE Trans. Knowl. Data Eng., vol. 27 (2015), pp. 2320-2334
-
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
Shiri Chechik, Edith Cohen, Haim Kaplan
APPROX-RANDOM (2015), pp. 659-679
-
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
Shiri Chechik, Edith Cohen, Haim Kaplan
CoRR, vol. abs/1503.08528 (2015)
-
Coordinated Sampling
Encyclopedia of Algorithms (2015)
-
Min-Hash Sketches
Encyclopedia of Algorithms (2015)
-
Multi-Objective Weighted Sampling
CoRR, vol. abs/1509.07445 (2015)
-
Reverse Ranking by Graph Structure: Model and Scalable Algorithms
Eliav Buchnik, Edith Cohen
CoRR, vol. abs/1506.02386 (2015)
-
Stream Sampling for Frequency Cap Statistics
CoRR, vol. abs/1502.05955 (2015)
-
Stream Sampling for Frequency Cap Statistics
KDD (2015), pp. 159-168
-
Algorithms and estimators for summarization of unaggregated data streams
Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup
J. Comput. Syst. Sci., vol. 80 (2014), pp. 1214-1244
-
All-distances sketches, revisited: HIP estimators for massive graphs analysis
PODS (2014), pp. 88-99
-
Author retrospective for search and replication in unstructured peer-to-peer networks
Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker
ICS 25th Anniversary (2014), pp. 64-82
-
Computing Classic Closeness Centrality, at Scale
Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck
CoRR, vol. abs/1409.0035 (2014)
-
Computing classic closeness centrality, at scale
Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck
COSN (2014), pp. 37-50
-
Distance queries from sampled data: accurate and efficient
KDD (2014), pp. 681-690
-
Estimation for monotone sampling: competitiveness and customization
PODC (2014), pp. 124-133
-
Probe scheduling for efficient detection of silent failures
Edith Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Danny Raz, Yoav Tzur
Perform. Eval., vol. 79 (2014), pp. 73-89
-
Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck
CIKM (2014), pp. 629-638
-
Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck
CoRR, vol. abs/1408.6282 (2014)
-
Timed Influence: Computation and Maximization
Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck
CoRR, vol. abs/1410.6976 (2014)
-
Variance Competitiveness for Monotone Estimation: Tightening the Bounds
CoRR, vol. abs/1406.6490 (2014)
-
A Labeling Approach to Incremental Cycle Detection
Edith Cohen, Amos Fiat, Haim Kaplan, Liam Roditty
CoRR, vol. abs/1310.8381 (2013)
-
On the Tradeoff between Stability and Fit
Edith Cohen, Graham Cormode, Nick G. Duffield, Carsten Lund
CoRR, vol. abs/1302.2137 (2013)
-
Probe Scheduling for Efficient Detection of Silent Failures
Edith Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Danny Raz, Yoav Tzur
CoRR, vol. abs/1302.0792 (2013)
-
Scalable Neighborhood Sketching and Distance Distribution Estimation in Graph Datasets: Revisited, Unified, and Improved
CoRR, vol. abs/1306.3284 (2013)
-
Scalable similarity estimation in social networks: closeness, node labels, and random edge lengths
Edith Cohen, Daniel Delling, Fabian Fuchs, Andrew V. Goldberg, Moisés Goldszmidt, Renato F. Werneck
COSN (2013), pp. 131-142
-
Scheduling Subset Tests: One-Time, Continuous, and How They Relate
Edith Cohen, Haim Kaplan, Yishay Mansour
APPROX-RANDOM (2013), pp. 81-95
-
What You Can Do with Coordinated Samples
Edith Cohen, Haim Kaplan
APPROX-RANDOM (2013), pp. 452-467
-
A Case for Customizing Estimators: Coordinated Samples
Edith Cohen, Haim Kaplan
CoRR, vol. abs/1212.0243 (2012)
-
Don't let the negatives bring you down: sampling from streams of signed updates
Edith Cohen, Graham Cormode, Nick G. Duffield
SIGMETRICS (2012), pp. 343-354
-
Envy-Free Makespan Approximation
Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
SIAM J. Comput., vol. 41 (2012), pp. 12-25
-
How to Estimate Change from Samples
Edith Cohen, Haim Kaplan
CoRR, vol. abs/1203.4903 (2012)
-
What you can do with Coordinated Samples
Edith Cohen, Haim Kaplan
CoRR, vol. abs/1206.5637 (2012)
-
Efficient Stream Sampling for Variance-Optimal Estimation of Subset Sums
Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup
SIAM J. Comput., vol. 40 (2011), pp. 1402-1431
-
Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information
Edith Cohen, Haim Kaplan
CoRR, vol. abs/1109.1325 (2011)
-
Get the most out of your sample: optimal unbiased estimators using partial information
Edith Cohen, Haim Kaplan
PODS (2011), pp. 13-24
-
Structure-Aware Sampling: Flexible and Accurate Summarization
Edith Cohen, Graham Cormode, Nick G. Duffield
PVLDB, vol. 4 (2011), pp. 819-830
-
Structure-Aware Sampling: Flexible and Accurate Summarization
Edith Cohen, Graham Cormode, Nick G. Duffield
CoRR, vol. abs/1102.5146 (2011)
-
Structure-aware sampling on data streams
Edith Cohen, Graham Cormode, Nick G. Duffield
SIGMETRICS (2011), pp. 197-208
-
Truth, Envy, and Truthful Market Clearing Bundle Pricing
Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
WINE (2011), pp. 97-108
-
Envy-free makespan approximation: extended abstract
Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
EC (2010), pp. 159-166
-
Labeling Dynamic XML Trees
Edith Cohen, Haim Kaplan, Tova Milo
SIAM J. Comput., vol. 39 (2010), pp. 2048-2074
-
On the Interplay between Incentive Compatibility and Envy Freeness
Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
CoRR, vol. abs/1003.5328 (2010)
-
Truth and Envy in Capacitated Allocation Games
Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
CoRR, vol. abs/1003.5326 (2010)
-
Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets
Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup
PVLDB, vol. 2 (2009), pp. 431-442
-
Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments
Edith Cohen, Haim Kaplan, Subhabrata Sen
PVLDB, vol. 2 (2009), pp. 646-657
-
Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments
Edith Cohen, Haim Kaplan, Subhabrata Sen
CoRR, vol. abs/0906.4560 (2009)
-
Decay Models
Encyclopedia of Database Systems (2009), pp. 757-761
-
Envy-Free Makespan Approximation
Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky
CoRR, vol. abs/0909.1072 (2009)
-
Leveraging Discarded Samples for Tighter Estimation of Multiple-Set Aggregates
Edith Cohen, Haim Kaplan
CoRR, vol. abs/0903.0625 (2009)
-
Leveraging discarded samples for tighter estimation of multiple-set aggregates
Edith Cohen, Haim Kaplan
SIGMETRICS/Performance (2009), pp. 251-262
-
Stream sampling for variance-optimal estimation of subset sums
Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup
SODA (2009), pp. 1255-1264
-
Confident estimation for multistage measurement sampling and aggregation
Edith Cohen, Nick G. Duffield, Carsten Lund, Mikkel Thorup
SIGMETRICS (2008), pp. 109-120
-
Estimating Aggregates over Multiple Sets
Edith Cohen, Haim Kaplan
ICDM (2008), pp. 761-766
-
Processing top-k queries from samples
Edith Cohen, Nadav Grossaug, Haim Kaplan
Computer Networks, vol. 52 (2008), pp. 2605-2622
-
Sketch-Based Estimation of Subpopulation-Weight
Edith Cohen, Haim Kaplan
CoRR, vol. abs/0802.3448 (2008)
-
Tighter estimation using bottom k sketches
Edith Cohen, Haim Kaplan
PVLDB, vol. 1 (2008), pp. 213-224
-
Variance optimal sampling based estimation of subset sums
Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup
CoRR, vol. abs/0803.0473 (2008)
-
Algorithms and estimators for accurate summarization of internet traffic
Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup
Internet Measurement Comference (2007), pp. 265-278
-
Associative search in peer to peer networks: Harnessing latent semantics
Edith Cohen, Amos Fiat, Haim Kaplan
Computer Networks, vol. 51 (2007), pp. 1861-1881
-
Bottom-k sketches: better and more efficient estimation of aggregates
Edith Cohen, Haim Kaplan
SIGMETRICS (2007), pp. 353-354
-
Sketching unaggregated data streams for subpopulation-size queries
Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup
PODS (2007), pp. 253-262
-
Spatially-decaying aggregation over a network
Edith Cohen, Haim Kaplan
J. Comput. Syst. Sci., vol. 73 (2007), pp. 265-288
-
Summarizing data using bottom-k sketches
Edith Cohen, Haim Kaplan
PODC (2007), pp. 225-234
-
A short walk in the Blogistan
Edith Cohen, Balachander Krishnamurthy
Computer Networks, vol. 50 (2006), pp. 615-630
-
Maintaining time-decaying stream aggregates
Edith Cohen, Martin J. Strauss
J. Algorithms, vol. 59 (2006), pp. 19-36
-
Making routing robust to changing traffic demands: algorithms and evaluation
David Applegate, Edith Cohen
IEEE/ACM Trans. Netw., vol. 16 (2006), pp. 1193-1206
-
Processing top k queries from samples
Edith Cohen, Nadav Grossaug, Haim Kaplan
CoNEXT (2006), pp. 7
-
Packet classification in large ISPs: design and evaluation of decision tree classifiers
Edith Cohen, Carsten Lund
SIGMETRICS (2005), pp. 73-84
-
Performance aspects of distributed caches using TTL-based consistency
Edith Cohen, Eran Halperin, Haim Kaplan
Theor. Comput. Sci., vol. 331 (2005), pp. 73-96
-
Balanced-Replication Algorithms for Distribution Trees
Edith Cohen, Haim Kaplan
SIAM J. Comput., vol. 34 (2004), pp. 227-247
-
Coping with network failures: routing strategies for optimal demand oblivious restoration
David Applegate, Lee Breslau, Edith Cohen
SIGMETRICS (2004), pp. 270-281
-
Efficient estimation algorithms for neighborhood variance and other moments
Edith Cohen, Haim Kaplan
SODA (2004), pp. 157-166
-
Guest Editors' foreword
Edith Cohen, Venkatesan Guruswami
J. Comput. Syst. Sci., vol. 68 (2004), pp. 701
-
Optimal oblivious routing in polynomial time
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
J. Comput. Syst. Sci., vol. 69 (2004), pp. 383-394
-
Spatially-decaying aggregation over a network: model and algorithms
Edith Cohen, Haim Kaplan
SIGMOD Conference (2004), pp. 707-718
-
A case for associative peer to peer overlays
Edith Cohen, Amos Fiat, Haim Kaplan
Computer Communication Review, vol. 33 (2003), pp. 95-100
-
Associative Search in Peer to Peer Networks: Harnessing Latent Semantics
Edith Cohen, Amos Fiat, Haim Kaplan
INFOCOM (2003)
-
Connection caching: model and algorithms
Edith Cohen, Haim Kaplan, Uri Zwick
J. Comput. Syst. Sci., vol. 67 (2003), pp. 92-126
-
Efficient sequences of trials
Edith Cohen, Amos Fiat, Haim Kaplan
SODA (2003), pp. 737-746
-
Maintaining time-decaying stream aggregates
Edith Cohen, Martin Strauss
PODS (2003), pp. 223-233
-
Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs
David Applegate, Edith Cohen
SIGCOMM (2003), pp. 313-324
-
Optimal oblivious routing in polynomial time
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
STOC (2003), pp. 383-388
-
Predicting and bypassing end-to-end Internet service degradations
Anat Bremler-Barr, Edith Cohen, Haim Kaplan, Yishay Mansour
IEEE Journal on Selected Areas in Communications, vol. 21 (2003), pp. 961-978
-
Proactive caching of DNS records: addressing a performance bottleneck
Edith Cohen, Haim Kaplan
Computer Networks, vol. 41 (2003), pp. 707-726
-
Reachability and Distance Queries via 2-Hop Labels
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
SIAM J. Comput., vol. 32 (2003), pp. 1338-1355
-
Balanced-Replication Algorithms for Distribution Trees
Edith Cohen, Haim Kaplan
ESA (2002), pp. 297-309
-
Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach
Edith Cohen, Haim Kaplan
Algorithmica, vol. 32 (2002), pp. 459-466
-
Competitive Analysis of the LRFU Paging Algorithm
Edith Cohen, Haim Kaplan, Uri Zwick
Algorithmica, vol. 33 (2002), pp. 511-516
-
Exploiting Regularities in Web Traffic Patterns for Cache Replacement
Edith Cohen, Haim Kaplan
Algorithmica, vol. 33 (2002), pp. 300-334
-
Labeling Dynamic XML Trees
Edith Cohen, Haim Kaplan, Tova Milo
PODS (2002), pp. 271-281
-
Predicting and bypassing end-to-end internet service degradations
Anat Bremler-Barr, Edith Cohen, Haim Kaplan, Yishay Mansour
Internet Measurement Workshop (2002), pp. 307-320
-
Prefetching the means for document transfer: a new approach for reducing Web latency
Edith Cohen, Haim Kaplan
Computer Networks, vol. 39 (2002), pp. 437-455
-
Reachability and distance queries via 2-hop labels
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
SODA (2002), pp. 937-946
-
Refreshment policies for Web content caches
Edith Cohen, Haim Kaplan
Computer Networks, vol. 38 (2002), pp. 795-808
-
Replication strategies in unstructured peer-to-peer networks
Edith Cohen, Scott Shenker
SIGCOMM (2002), pp. 177-190
-
Restoration by path concatenation: fast recovery of MPLS paths
Yehuda Afek, Anat Bremler-Barr, Haim Kaplan, Edith Cohen, Michael Merritt
Distributed Computing, vol. 15 (2002), pp. 273-283
-
Search and replication in unstructured peer-to-peer networks
Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker
ICS (2002), pp. 84-95
-
Search and replication in unstructured peer-to-peer networks
Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker
SIGMETRICS (2002), pp. 258-259
-
Aging through cascaded caches: performance issues in the distribution of web content
Edith Cohen, Haim Kaplan
SIGCOMM (2001), pp. 41-53
-
All-Pairs Small-Stretch Paths
Edith Cohen, Uri Zwick
J. Algorithms, vol. 38 (2001), pp. 335-353
-
Competitive Analysis of the LRFU Paging Algorithm
Edith Cohen, Haim Kaplan, Uri Zwick
WADS (2001), pp. 148-154
-
Finding Interesting Associations without Support Pruning
Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, Jeffrey D. Ullman, Cheng Yang
IEEE Trans. Knowl. Data Eng., vol. 13 (2001), pp. 64-78
-
Performance Aspects of Distributed Caches Using TTL-Based Consistency
Edith Cohen, Eran Halperin, Haim Kaplan
ICALP (2001), pp. 744-756
-
Proactive Caching of DNS Records: Addressing a Performance Bottleneck
Edith Cohen, Haim Kaplan
SAINT (2001), pp. 85-94
-
Refreshment Policies for Web Content Caches
Edith Cohen, Haim Kaplan
INFOCOM (2001), pp. 1398-1406
-
Restoration by path concatenation: fast recovery of MPLS paths
Anat Bremler-Barr, Yehuda Afek, Haim Kaplan, Edith Cohen, Michael Merritt
PODC (2001), pp. 43-52
-
Restoration path concatenation: fast recovery of MPLS paths
Anat Bremler-Barr, Yehuda Afek, Haim Kaplan, Edith Cohen, Michael Merritt
SIGMETRICS/Performance (2001), pp. 316-317
-
The Age Penalty and Its Effect on Cache Performance
Edith Cohen, Haim Kaplan
USITS (2001), pp. 73-84
-
Connection caching under vaious models of communication
Edith Cohen, Haim Kaplan, Uri Zwick
SPAA (2000), pp. 54-63
-
Finding Interesting Associations without Support Pruning
Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, Jeffrey D. Ullman, Cheng Yang
ICDE (2000), pp. 489-499
-
Polylog-time and near-linear work approximation scheme for undirected shortest paths
J. ACM, vol. 47 (2000), pp. 132-166
-
Prefetching the Means for Document Transfer: A New Approach for Reducing Web Latency
Edith Cohen, Haim Kaplan
INFOCOM (2000), pp. 854-863
-
Approximating Matrix Multiplication for Pattern Recognition Tasks
Edith Cohen, David D. Lewis
J. Algorithms, vol. 30 (1999), pp. 211-252
-
Connection Caching
Edith Cohen, Haim Kaplan, Uri Zwick
STOC (1999), pp. 612-621
-
Efficient Algorithms for Predicting Requests to Web Servers
Edith Cohen, Balachander Krishnamurthy, Jennifer Rexford
INFOCOM (1999), pp. 284-293
-
Exploiting Regularities in Web Traffic Patterns for Cache Replacement
Edith Cohen, Haim Kaplan
STOC (1999), pp. 109-118
-
LP-based Analysis of Greedy-dual-size
Edith Cohen, Haim Kaplan
SODA (1999), pp. 879-880
-
Managing TCP Connections Under Persistent HTTP
Edith Cohen, Haim Kaplan, Jeffrey D. Oldham
Computer Networks, vol. 31 (1999), pp. 1709-1723
-
Evaluating Server-Assisted Cache Replacement in the Web
Edith Cohen, Balachander Krishnamurthy, Jennifer Rexford
ESA (1998), pp. 307-319
-
Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
SIAM J. Comput., vol. 28 (1998), pp. 210-236
-
Improving End-to-End Performance of the Web Using Server Volumes and Proxy Filters
Edith Cohen, Balachander Krishnamurthy, Jennifer Rexford
SIGCOMM (1998), pp. 241-253
-
Structure Prediction and Computation of Sparse Matrix Products
J. Comb. Optim., vol. 2 (1998), pp. 307-332
-
All-Pairs Small-Stretch Paths
Edith Cohen, Uri Zwick
SODA (1997), pp. 93-102
-
Approximating Matrix Multiplication for Pattern Recognition Tasks
Edith Cohen, David D. Lewis
SODA (1997), pp. 682-691
-
Learning Noisy Perceptrons by a Perceptron in Polynomial Time
FOCS (1997), pp. 514-523
-
Size-Estimation Framework with Applications to Transitive Closure and Reachability
J. Comput. Syst. Sci., vol. 55 (1997), pp. 441-453
-
Using Selective Path-Doubling for Parallel Shortest-Path Computations
J. Algorithms, vol. 22 (1997), pp. 30-56
-
Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition
J. Algorithms, vol. 21 (1996), pp. 331-357
-
On Optimizing Multiplications of Sparse Matrices
IPCO (1996), pp. 219-233
-
Approximate Max-Flow on Small Depth Networks
SIAM J. Comput., vol. 24 (1995), pp. 579-597
-
Improvise: Interactive Multimedia Process Visualization Environment
Naser S. Barghouti, Eleftherios Koutsofios, Edith Cohen
ESEC (1995), pp. 28-43
-
Algorithms and Complexity Analysis for Some Flow Problems
Edith Cohen, Nimrod Megiddo
Algorithmica, vol. 11 (1994), pp. 320-340
-
Estimating the Size of the Transitive Closure in Linear Time
FOCS (1994), pp. 190-200
-
Improved Algorithms for Linear Inequalities With Two Variables per Inequality
Edith Cohen, Nimrod Megiddo
SIAM J. Comput., vol. 23 (1994), pp. 1313-1347
-
New algorithms for generalized network flows
Edith Cohen, Nimrod Megiddo
Math. Program., vol. 64 (1994), pp. 325-336
-
Polylog-time and near-linear work approximation scheme for undirected shortest paths
STOC (1994), pp. 16-26
-
Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition
SPAA (1993), pp. 57-67
-
Fast algorithms for constructing t-spanners and paths with stretch t
FOCS (1993), pp. 648-658
-
Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Periodic Graphs
Edith Cohen, Nimrod Megiddo
J. ACM, vol. 40 (1993), pp. 791-830
-
Using Selective Path-Doubling for Parallel Shortest-Path Computations
ISTCS (1993), pp. 78-87
-
Approximate Max Flow on Small Depth Networks
FOCS (1992), pp. 648-658
-
New Algorithms for Generalized Network Flows
Edith Cohen, Nimrod Megiddo
ISTCS (1992), pp. 103-114
-
Algorithms and Complexity Analysis for Some Flow Problems
Edith Cohen, Nimrod Megiddo
SODA (1991), pp. 120-130
-
Improved Algorithms for Linear Inequalities with Two Variables per Inequality (Extended Abstract)
Edith Cohen, Nimrod Megiddo
STOC (1991), pp. 145-155
-
NP-Completeness of graph decomposition problems
Edith Cohen, Michael Tarsi
J. Complexity, vol. 7 (1991), pp. 200-212
-
Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (Preliminary Version)
Edith Cohen, Nimrod Megiddo
STOC (1989), pp. 523-534

