# Edith Cohen

According to our database

Collaborative distances:

^{1}, Edith Cohen authored at least 127 papers between 1989 and 2020.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

2020

Sample Complexity Bounds for Influence Maximization.

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Influence Maximization with Few Simulations.

CoRR, 2019

Sampling Sketches for Concave Sublinear Functions of Frequencies.

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Self-similar Epochs: Value in arrangement.

Proceedings of the 36th International Conference on Machine Learning, 2019

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.

POMACS, 2018

LSH Microbatches for Stochastic Gradients: Value in Rearrangement.

CoRR, 2018

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

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

2017

Clustering over Multi-Objective Samples: The one2all Sample.

CoRR, 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

Estimating Frequency Statistics through Distinct Count Measurements.

CoRR, 2016

Semi-Supervised Learning for Asymmetric Graphs through Reach and Distance Diffusion.

CoRR, 2016

Efficient Distinct Heavy Hitters for DNS DDoS Attack Detection.

CoRR, 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

All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis.

IEEE Trans. Knowl. Data Eng., 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

Timed Influence: Computation and Maximization.

CoRR, 2014

Variance Competitiveness for Monotone Estimation: Tightening the Bounds.

CoRR, 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

A Labeling Approach to Incremental Cycle Detection.

CoRR, 2013

Scalable Neighborhood Sketching and Distance Distribution Estimation in Graph Datasets: Revisited, Unified, and Improved.

CoRR, 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

A Case for Customizing Estimators: Coordinated Samples

CoRR, 2012

How to Estimate Change from Samples

CoRR, 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

Labeling Dynamic XML Trees.

SIAM J. Comput., 2010

On the Interplay between Incentive Compatibility and Envy Freeness

CoRR, 2010

Truth and Envy in Capacitated Allocation Games

CoRR, 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

Variance optimal sampling based estimation of subset sums

CoRR, 2008

Sketch-Based Estimation of Subpopulation-Weight

CoRR, 2008

Processing top-k queries from samples.

Comput. Networks, 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

Associative search in peer to peer networks: Harnessing latent semantics.

Comput. Networks, 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

Maintaining time-decaying stream aggregates.

J. Algorithms, 2006

A short walk in the Blogistan.

Comput. Networks, 2006

2005

Performance aspects of distributed caches using TTL-based consistency.

Theor. Comput. Sci., 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

Balanced-Replication Algorithms for Distribution Trees.

SIAM J. Comput., 2004

Guest Editors' foreword.

J. Comput. Syst. Sci., 2004

Optimal oblivious routing in polynomial time.

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

Reachability and Distance Queries via 2-Hop Labels.

SIAM J. Comput., 2003

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

IEEE Journal on Selected Areas in Communications, 2003

Connection caching: model and algorithms.

J. Comput. Syst. Sci., 2003

Proactive caching of DNS records: addressing a performance bottleneck.

Comput. Networks, 2003

A case for associative peer to peer overlays.

Computer Communication Review, 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

2002

Restoration by path concatenation: fast recovery of MPLS paths.

Distributed Computing, 2002

Prefetching the means for document transfer: a new approach for reducing Web latency.

Comput. Networks, 2002

Refreshment policies for Web content caches.

Comput. Networks, 2002

Competitive Analysis of the LRFU Paging Algorithm.

Algorithmica, 2002

Exploiting Regularities in Web Traffic Patterns for Cache Replacement.

Algorithmica, 2002

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

Algorithmica, 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

2001

Finding Interesting Associations without Support Pruning.

IEEE Trans. Knowl. Data Eng., 2001

All-Pairs Small-Stretch Paths.

J. Algorithms, 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.

Proceedings of the ACM SIGCOMM 2001 Conference on Applications, 2001

2000

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

J. ACM, 2000

Connection caching under vaious models of communication.

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

1999

Approximating Matrix Multiplication for Pattern Recognition Tasks.

J. Algorithms, 1999

Managing TCP Connections Under Persistent HTTP.

Comput. Networks, 1999

Connection Caching.

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.

Proceedings of the ACM SIGCOMM 1998 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, August 31, 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

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

J. Algorithms, 1997

Learning Noisy Perceptrons by a Perceptron in Polynomial Time.

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

1996

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

J. Algorithms, 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

New algorithms for generalized network flows.

Math. Program., 1994

Algorithms and Complexity Analysis for Some Flow Problems.

Algorithmica, 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

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

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