# Edith Cohen

According to our database

Collaborative distances:

^{1}, Edith Cohen authored at least 112 papers between 1989 and 2018.Collaborative distances:

## Awards

## ACM Fellow

ACM Fellow 2017, "For contributions to the design of efficient algorithms for networking and big data".

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2018

Decay Models.

Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018

Stream Sampling Framework and Application for Frequency Cap Statistics.

ACM Trans. Algorithms, 2018

Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity.

Proceedings of the Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems, 2018

Clustering Small Samples With Quality Guarantees: Adaptivity With One2all PPS.

Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017

HyperLogLog Hyperextended: Sketches for Concave Sublinear Frequency Statistics.

Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13, 2017

Mitigating DNS random subdomain DDoS attacks by distinct heavy hitters sketches.

Proceedings of the fifth ACM/IEEE Workshop on Hot Topics in Web Systems and Technologies, 2017

2016

Min-Hash Sketches.

Encyclopedia of Algorithms, 2016

Coordinated Sampling.

Encyclopedia of Algorithms, 2016

All-Distances Sketches.

Encyclopedia of Algorithms, 2016

On the Tradeoff between Stability and Fit.

ACM Trans. Algorithms, 2016

Reverse Ranking by Graph Structure: Model and Scalable Algorithms.

Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, 2016

Greedy Maximization Framework for Graph-Based Influence Functions.

Proceedings of the Fourth IEEE Workshop on Hot Topics in Web Systems and Technologies, 2016

2015

Stream Sampling for Frequency Cap Statistics.

Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015

Multi-objective Weighted Sampling.

Proceedings of the Third IEEE Workshop on Hot Topics in Web Systems and Technologies, 2015

Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees.

Proceedings of the Approximation, 2015

2014

Probe scheduling for efficient detection of silent failures.

Perform. Eval., 2014

Algorithms and estimators for summarization of unaggregated data streams.

J. Comput. Syst. Sci., 2014

All-distances sketches, revisited: HIP estimators for massive graphs analysis.

Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

Estimation for monotone sampling: competitiveness and customization.

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Distance queries from sampled data: accurate and efficient.

Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014

Author retrospective for search and replication in unstructured peer-to-peer networks.

Proceedings of the ACM International Conference on Supercomputing 25th Anniversary Volume, 2014

Computing classic closeness centrality, at scale.

Proceedings of the second ACM conference on Online social networks, 2014

Sketch-based Influence Maximization and Computation: Scaling up with Guarantees.

Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, 2014

2013

Scalable similarity estimation in social networks: closeness, node labels, and random edge lengths.

Proceedings of the Conference on Online Social Networks, 2013

Scheduling Subset Tests: One-Time, Continuous, and How They Relate.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

What You Can Do with Coordinated Samples.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Envy-Free Makespan Approximation.

SIAM J. Comput., 2012

Don't let the negatives bring you down: sampling from streams of signed updates.

Proceedings of the ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, 2012

2011

Efficient Stream Sampling for Variance-Optimal Estimation of Subset Sums.

SIAM J. Comput., 2011

Structure-Aware Sampling: Flexible and Accurate Summarization.

PVLDB, 2011

Truth, Envy, and Truthful Market Clearing Bundle Pricing.

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

Structure-aware sampling on data streams.

Proceedings of the SIGMETRICS 2011, 2011

Get the most out of your sample: optimal unbiased estimators using partial information.

Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

2010

Envy-free makespan approximation: extended abstract.

Proceedings of the Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), 2010

2009

Decay Models.

Proceedings of the Encyclopedia of Database Systems, 2009

Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments.

PVLDB, 2009

Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets.

PVLDB, 2009

Stream sampling for variance-optimal estimation of subset sums.

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Leveraging discarded samples for tighter estimation of multiple-set aggregates.

Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems, 2009

2008

Tighter estimation using bottom k sketches.

PVLDB, 2008

Confident estimation for multistage measurement sampling and aggregation.

Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2008

Estimating Aggregates over Multiple Sets.

Proceedings of the 8th IEEE International Conference on Data Mining (ICDM 2008), 2008

2007

Spatially-decaying aggregation over a network.

J. Comput. Syst. Sci., 2007

Bottom-k sketches: better and more efficient estimation of aggregates.

Proceedings of the 2007 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2007

Sketching unaggregated data streams for subpopulation-size queries.

Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007

Summarizing data using bottom-k sketches.

Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

Algorithms and estimators for accurate summarization of internet traffic.

Proceedings of the 7th ACM SIGCOMM Internet Measurement Conference, 2007

2006

Making routing robust to changing traffic demands: algorithms and evaluation.

IEEE/ACM Trans. Netw., 2006

A short walk in the Blogistan.

Computer Networks, 2006

Processing top k queries from samples.

Proceedings of the 2006 ACM Conference on Emerging Network Experiment and Technology, 2006

2005

Packet classification in large ISPs: design and evaluation of decision tree classifiers.

Proceedings of the International Conference on Measurements and Modeling of Computer Systems, 2005

2004

Guest Editors' foreword.

J. Comput. Syst. Sci., 2004

Efficient estimation algorithms for neighborhood variance and other moments.

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Spatially-decaying aggregation over a network: model and algorithms.

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2004

Coping with network failures: routing strategies for optimal demand oblivious restoration.

Proceedings of the International Conference on Measurements and Modeling of Computer Systems, 2004

2003

Connection caching: model and algorithms.

J. Comput. Syst. Sci., 2003

A case for associative peer to peer overlays.

Computer Communication Review, 2003

Optimal oblivious routing in polynomial time.

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Efficient sequences of trials.

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs.

Proceedings of the ACM SIGCOMM 2003 Conference on Applications, 2003

Maintaining time-decaying stream aggregates.

Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

Associative Search in Peer to Peer Networks: Harnessing Latent Semantics.

Proceedings of the Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30, 2003

2002

Restoration by path concatenation: fast recovery of MPLS paths.

Distributed Computing, 2002

Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach.

Algorithmica, 2002

Reachability and distance queries via 2-hop labels.

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Search and replication in unstructured peer-to-peer networks.

Proceedings of the International Conference on Measurements and Modeling of Computer Systems, 2002

Replication strategies in unstructured peer-to-peer networks.

Proceedings of the ACM SIGCOMM 2002 Conference on Applications, 2002

Labeling Dynamic XML Trees.

Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2002

Predicting and bypassing end-to-end internet service degradations.

Proceedings of the 2nd ACM SIGCOMM Internet Measurement Workshop, 2002

Search and replication in unstructured peer-to-peer networks.

Proceedings of the 16th international conference on Supercomputing, 2002

Balanced-Replication Algorithms for Distribution Trees.

Proceedings of the Algorithms, 2002

2001

Competitive Analysis of the LRFU Paging Algorithm.

Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

The Age Penalty and Its Effect on Cache Performance.

Proceedings of the 3rd USENIX Symposium on Internet Technologies and Systems, 2001

Restoration path concatenation: fast recovery of MPLS paths.

Proceedings of the Joint International Conference on Measurements and Modeling of Computer Systems, 2001

Aging through cascaded caches: performance issues in the distribution of web content.

SIGCOMM, 2001

Proactive Caching of DNS Records: Addressing a Performance Bottleneck.

Proceedings of the 2001 Symposium on Applications and the Internet (SAINT 2001), 2001

Restoration by path concatenation: fast recovery of MPLS paths.

Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

Refreshment Policies for Web Content Caches.

Proceedings of the Proceedings IEEE INFOCOM 2001, 2001

Performance Aspects of Distributed Caches Using TTL-Based Consistency.

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

2000

Connection caching under vaious models of communication.

Proceedings of the Twelfth annual ACM Symposium on Parallel Algorithms and Architectures, 2000

Prefetching the Means for Document Transfer: A New Approach for Reducing Web Latency.

Proceedings of the Proceedings IEEE INFOCOM 2000, 2000

Finding Interesting Associations without Support Pruning.

Proceedings of the 16th International Conference on Data Engineering, San Diego, California, USA, February 28, 2000

1999

Managing TCP Connections Under Persistent HTTP.

Computer Networks, 1999

Connection Caching.

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Exploiting Regularities in Web Traffic Patterns for Cache Replacement.

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

LP-based Analysis of Greedy-dual-size.

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Efficient Algorithms for Predicting Requests to Web Servers.

Proceedings of the Proceedings IEEE INFOCOM '99, 1999

1998

Fast Algorithms for Constructing t-Spanners and Paths with Stretch t.

SIAM J. Comput., 1998

Structure Prediction and Computation of Sparse Matrix Products.

J. Comb. Optim., 1998

Improving End-to-End Performance of the Web Using Server Volumes and Proxy Filters.

SIGCOMM, 1998

Evaluating Server-Assisted Cache Replacement in the Web.

Proceedings of the Algorithms, 1998

1997

Size-Estimation Framework with Applications to Transitive Closure and Reachability.

J. Comput. Syst. Sci., 1997

All-Pairs Small-Stretch Paths.

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Approximating Matrix Multiplication for Pattern Recognition Tasks.

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Learning Noisy Perceptrons by a Perceptron in Polynomial Time.

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

On Optimizing Multiplications of Sparse Matrices.

Proceedings of the Integer Programming and Combinatorial Optimization, 1996

1995

Approximate Max-Flow on Small Depth Networks.

SIAM J. Comput., 1995

Improvise: Interactive Multimedia Process Visualization Environment.

Proceedings of the 5th European Software Engineering Conference, 1995

1994

Improved Algorithms for Linear Inequalities With Two Variables per Inequality.

SIAM J. Comput., 1994

Polylog-time and near-linear work approximation scheme for undirected shortest paths.

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Estimating the Size of the Transitive Closure in Linear Time

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Periodic Graphs.

J. ACM, 1993

Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition.

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

Using Selective Path-Doubling for Parallel Shortest-Path Computations.

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

Fast algorithms for constructing t-spanners and paths with stretch t

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

New Algorithms for Generalized Network Flows.

Proceedings of the Theory of Computing and Systems, 1992

Approximate Max Flow on Small Depth Networks

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

NP-Completeness of graph decomposition problems.

J. Complexity, 1991

Improved Algorithms for Linear Inequalities with Two Variables per Inequality (Extended Abstract)

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Algorithms and Complexity Analysis for Some Flow Problems.

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

1990

Recognizing Properties of Periodic Graphs.

Proceedings of the Applied Geometry And Discrete Mathematics, 1990

1989

Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (Preliminary Version)

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989