Publications of Edith Cohen

Papers/Presentations available online

List of publications

Papers and presentations available online.

(sorted by topic, given in postscript/compressed postcript/pdf/HTML/ppt formats)

Copyright Notice: Since most of these papers are published, the copyright has been transferred to the respective publishers. Therefore, the papers cannot be duplicated for commercial purposes. The following is ACM's copyright notice; other publishers have similar ones.

Copyright © 199x by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.

Freshness/Aging issues in the performance of Web caches

Refreshment policies for Web content caches. Joint with Haim Kaplan.

proceedings version ; HTML ; full version ; conference citation; journal citation; Infocom 2001 presentation (ppt).
The age penalty and its effect on cache performance. Joint with Haim Kaplan.

proceedings version ; HTML ; conference citation; USITS 2001 presentation (ppt);
Aging through cascaded caches: performance issues in the distribution of Web content. Joint with Haim Kaplan.

proceedings version; full version; conference citation; 1hr presentation (pps, ppt), given at Stanford Networking Seminar) (October 25, 2001); SIGCOMM 2001.
Performance aspects of distributed caches using TTL-based consistency. Joint with Eran Halperin and Haim Kaplan.

proceedings version ; full version ; conference citation; journal citation; ICALP 2001.

Improved Web user-perceived latency through reduced communication-establishment overhead

Prefetching the means for document transfer: A new approach for reducing Web latency. Joint with Haim Kaplan.

full version; journal citation; proceedings version; conference citation; Infocom 2000.
Proactive caching of DNS records: Addressing a performance bottleneck. Joint with Haim Kaplan.

proceedings version ; full version ; presentation (ppt), given at TAU CS Colloquium (April 9, 2000) and Stanford Networking Seminar (May 10, 2000); SAINT'01 presentation (ppt); conference citation. journal citation.

Improved Web performance by enhanced end-to-end communication

Improving end-to-end performance of the Web using server volumes and proxy filters Joint with Balachander Krishnamurthy and Jennifer Rexford.

proceedings version (compressed postcript); presentation (ps) given in SIGCOMM '98 by Bala Krishnamurthy; 1 hour presentation (ps) by Jennifer Rexford; conference citation.
Efficient algorithms for predicting requests to Web servers. Joint with Balachander Krishnamurthy and Jennifer Rexford.

paper ; conference citation ; Infocom 1999.

Peer-to-Peer networks; replication and search in distributed datasets

Replication Strategies in Unstructured Peer-to-Peer Networks. Joint with Scott Shenker.

proceedings version; conference citation ; presentation (ppt) given at SIGCOMM 2002.
A Case for Associative Peer to Peer Overlays. Joint with Haim Kaplan and Amos Fiat.

proceedings version (position paper); conference citation ; HotNets-I 2002.
Associative Search in Peer to Peer Networks: Harnessing Latent Semantics. Joint with Haim Kaplan and Amos Fiat.

conference citation ; journal citation ; presentation (ppt), given at Stanford Networking Seminar (CS 548) (May 15, 2002); proceedings version; Infocom 2003.
Search and replication in unstructured peer-to-peer networks. Joint with Qin Lv, Pei Cao, Kai Li, and Scott Shenker.

conference citation ; 2-page abstract; proceedings version; full version; ICS 2002; Sigmetrics 2002.
Balanced-replication algorithms for distribution trees. Joint with Haim Kaplan.

conference citation; journal citation; proceedings version; full version; ESA 2002.
Efficient Sequences of Trials. Joint with Amos Fiat and Haim Kaplan.

conference citation; proceedings version; SODA 2003.

XML, Data streams, Spatial aggregation

Labeling Dynamic XML Trees. Joint with Tova Milo and Haim Kaplan.

proceedings version ; conference citation ; PODS 2002.
Maintaining Time-Decaying Stream Aggregates. Joint with Martin Strauss.

proceedings version ; journal version ; conference citation ; journal citation ; presentation (ppt); PODS 2003.
Efficient Estimation Algorithms for Neighborhood Variance and Other Moments. Joint with Haim Kaplan .

proceedings version ; conference citation ; SODA 2004.
Spatially-Decaying Aggregation over a Network: Model and Algorithms. Joint with Haim Kaplan .

proceedings version ; conference citation ; jounral citation ; SIGMOD 2004.

Routing, Path selection, Measurements, Packet filtering

Packet Classification in Large ISPs: Design and Evaluation of Decision Tree Classifiers. Joint with Carsten Lund.

conference citation ; proceedings version ; Sigmetrics/Performance 2005.
Making Intra-Domain Routing Robust to Changing and Uncertain Traffic Demands: Understanding Fundamental Tradeoffs. Joint with David Applegate.

conference citation ; journal (full version) citation ; proceedings version ; presentation (ppt) given at SIGCOMM 2003.
Coping with Network Failures: Routing Strategies for Optimal Demand Oblivious Restoration. Joint with David Applegate and Lee Breslau.

conference citation ; proceedings version ; Sigmetrics/Performance 2004.
Optimal oblivious routing in polynomial time. Joint with Yossi Azar, Amos Fiat, Harald Räcke, and Haim Kaplan.

proceedings version ; presentation (ppt); conference citation ; journal citation ; STOC 2003.
Predicting and bypassing end-to-end Internet service degradations. Joint with Anat Bremler-Barr, Haim Kaplan , and Yishay Mansour.
proceedings version ; full version ; Presentation at IMW02 (ppt) (prepared by Anat Bremler-Barr); conference citation ; journal citation ; IMW 2002.
Restoration by path concatenation: Fast recovery of MPLS paths. Joint with Anat Bremler-Barr, Yehuda Afek, Haim Kaplan and Michael Merritt.
proceedings version ; full version ; journal citation; conference citation; SIGMETRICS 2001; PODC 2001.

Cache replacement for Web pages: theory and experiments

Evaluating server-assisted cache replacement in the Web Joint with Balachander Krishnamurthy and Jennifer Rexford.

paper; presentation (ps); conference citation; ESA 1998.
Exploiting regularities in Web traffic patterns for cache replacement. Joint with Haim Kaplan.

paper ; proceedings version; STOC 99 presentation by Haim Kaplan; conference citation; journal citation; STOC 1999.
Caching documents with varying sizes and fetching costs: An LP-Based approach. Joint with Haim Kaplan.

paper ; conference citation; SODA 1999; journal citation.
Competitive analysis of the LRFU paging algorithm. Joint with Haim Kaplan and Uri Zwick.

paper (postscript) ; HTML ; presentation (ppt) by Haim Kaplan; conference citation; journal citation; WADS 2001.

Connection Caching: theory and experiments

Connection caching. Joint with Haim Kaplan and Uri Zwick.
full version ; journal citation; 1hr presentation (ps); proceedings version ; conference citation; STOC 1999.
Connection caching under various models of communication. Joint with Haim Kaplan and Uri Zwick.
paper ; conference citation; SPAA presentation (ps); SPAA 2000.
Managing TCP connections under persistent HTTP. Joint with Haim Kaplan and Jeffrey Oldham.
paper (postscript) ; HTML; conference citation; journal citation ; WWW8 1999.

Information Retrieval / Machine Learning

Learning noisy perceptrons by a perceptron in polynomial time.
paper ; presentation (ps); conference proceedings version; conference citation; FOCS 1997.
Approximating matrix multiplication for pattern recognition tasks. Joint with David Lewis.
paper (1.2M) ; paper without plots (180K) ; presentation (ps); journal citation; conference citation; SODA 1998.
Finding Interesting Associations without Support Pruning. Joint with R. Motwani, M. Datar, S. Fujiware, A. Gionis, P. Indyk, J. Ullman, and C. Yang.

proceedings version ; full version ; conference citation; journal citation; ICDE 2000.

Data summarization

Summarizing data using bottom-k sketches.
Joint with Haim Kaplan .
paper; conference citation; PODC 2007.
Sketches and estimators for subpopulation weight queries.
Joint with Haim Kaplan .
paper; 2-page abstract of estimators and podc 2007 paper conference citation (poster); ACM SIGMETRICS 2007
Sketching unaggregated data streams for subpopulation-size queries.
Joint with Nick Duffield , Haim Kaplan , Carsten Lund , and Mikkel Thorup
paper; conference citation; PODS 2007.
Algorithms and estimators for accurate summarization of Internet traffic.
Joint with Nick Duffield , Haim Kaplan , Carsten Lund , and Mikkel Thorup
paper; conference citation; IMC 2007.
Algorithms and estimators for summarization of unaggregated data streams.
Joint with Nick Duffield , Haim Kaplan , Carsten Lund , and Mikkel Thorup
paper; Journal submission based on IMC 2007 and PODS 2007 papers.
Processing Top-k queries from samples.
Joint with Nadav Grossaug and Haim Kaplan .
paper; conference citation; CONEXT 2006.

Size-Estimation Scheme and Applications

Size-estimation framework with applications to transitive closure and reachability.
paper ; journal citation; conference citation; FOCS 1994 ; presentation (25th Columbia Theory Day, Columbia University, April 7, 1995).
Structure Prediction and Computation of Sparse Matrix Products.
paper; journal citation; conference citation; IPCO 1996; presentation (ps).
(Experimental study applying the estimation framework to optimize sparse matrix multiplications.)
When Piecewise determinism is almost true. Joint with Yi-Min Wang and Gaurav Suri.
paper; conference citation.
(Roll-Back Recovery model for fault tolerance in distributed systems)

Distance and Reachability Queries

Reachability and distance queries via 2-hop labels. Joint with Eran Halperin, Haim Kaplan, and Uri Zwick.
journal citation; conference citation; proceedings version; full version; SODA 2002.

Shortest Paths: Trading Accuracy and Time

All pairs small stretch paths. Joint with Uri Zwick .
paper; conference citation; SODA 1997; journal citation.
Fast algorithms for t-spanners and stretch-t paths.
paper; journal citation; conference citation; FOCS 1993.

Parallel Algorithms: Shortest Paths and Maximum Flow

Polylog-time and near-linear work approximation scheme for undirected shortest-paths.
paper; journal citation; conference citation; STOC 1994.
Efficient parallel shortest-paths in digraphs with a separator decomposition.
paper; journal citation; conference citation; SPAA 1993.
Using selective path-doubling for parallel shortest-path computations.
paper; journal citation; conference citation; ISTCS 1993.
Approximate max-flow on small depth networks.
paper; journal citation; conference citation; FOCS 1992.

Combinatorial Optimization / Linear Programming

Improved algorithms for linear inequalities with two variables per inequality. Joint with Nimrod Megiddo.
paper; journal citation; conference citation; STOC 1991.
New algorithms for generalized network flows. Joint with Nimrod Megiddo.
paper; journal citation; conference citation; ISTCS 1992.
Complexity analysis and algorithms for some flow problems. Joint with Nimrod Megiddo.
paper; journal citation; conference citation; SODA 1991.
Strongly polynomial time and NC algorithms for detecting cycles in periodic graphs. Joint with Nimrod Megiddo.
paper; journal citation; conference citation; STOC 1989.
Recognizing properties of periodic graphs. Joint with Nimrod Megiddo.
paper; journal citation.
Maximizing concave functions in fixed dimension. Joint with Nimrod Megiddo.
paper; journal citation.

Design of a CDMA decoder

Multi-rate detection for the IS-95 CDMA forward traffic channel. Joint with Hui-Ling Lou.
paper; conference citation; GLOBECOM 1995.
Multi-rate detection for the IS-95A CDMA forward traffic channel using the 13kbs speach coder. Joint with Hui-Ling Lou.
paper; multimedia recording of a presentation by Hui-Ling Lou ; conference citation; ICC 1996.

Software tools

Improvise: Interactive Multimedia Process Visualization Environment. Joint with Naser Barghouti and Lefty Koutsofios.
paper; conference citation; ESEC 1995.

Publications List

In reverse chronological order

Conference Papers

Ph.D. Thesis, Books

Journal Papers

Conference Papers:

Algorithms and estimators for accurate summarization of Internet traffic. E. Cohen, N. Duffield, H. Kaplan, C. Lund and M. Thorup.
In Proceedings of the 2007 ACM/SIGCOMM Internet Measurement Conference (IMC 2007). 2007.

Summarizing data using bottom-k sketches. E. Cohen and H. Kaplan.
In Proceedings Twenty-Sixth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2007). 2007.

Sketching unaggregated data streams for subpopulation-size queries. E. Cohen, N. Duffield, H. Kaplan, C. Lund and M. Thorup.
In Proceedings 26th ACM SIGMOD-SIGACT0SIGART Symposium on Principles of Database Systems (PODS 2007). 2007.

Bottom-k sketches: better and more efficient estimation of aggregates. E. Cohen and H. Kaplan.
In Proceedings of the ACM Sigmetrics/Performance Joint International Conference on Measurements and Modeling of Computer Systems (poster). 2007.

Processing Top-k Queries from Samples. E. Cohen, N. Grossaug, and H. Kaplan.
In Proceedings of the 2nd conference on Future Networking Technologies (CoNext). 2006.

Packet Classification in large ISPs: Design and evaluation of decision tree classifiers. E. Cohen and C. Lund.
In Proceedings of the ACM Sigmetrics/Performance Joint International Conference on Measurements and Modeling of Computer Systems. 2005.

Spatially-Decaying Aggregation over a Network: Model and Algorithms. E. Cohen and H. Kaplan.
In Proceedings of the ACM SIGMOD International Conference on Management of Data. 2004.

Coping with Network Failures: Routing Strategies for Optimal Demand Oblivious Restoration. D. Applegate, L. Breslau, and E. Cohen.
In Proceedings of the ACM Sigmetrics/Performance Joint International Conference on Measurements and Modeling of Computer Systems. 2004.

Efficient Estimation Algorithms for Neighborhood Variance and Other Moments. E. Cohen and H. Kaplan
In Proceedings of the ACM-SIAM SODA'04 Conference . 2004.

Making Intra-Domain Routing Robust to Changing and Uncertain Traffic Demands: Understanding Fundamental Tradeoffs. D. Applegate and E. Cohen.
In Proceedings of the ACM SIGCOMM'03 Conference . 2003.

Maintaining Time-Decaying Stream Aggregates E. Cohen and M. Strauss.
In Proc. 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS). 2003.

Optimal oblivious routing in polynomial time. Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Räcke.
In Proc. 35th Annual ACM Symposium on Theory of Computing. ACM, 2003.

Associative Search in Peer to Peer Networks: Harnessing Latent Semantics. E. Cohen, A. Fiat, and H. Kaplan.
In Proceedings of the IEEE INFOCOM'03 Conference. 2003.

Efficient Sequences of Trials. E. Cohen, A. Fiat, and H. Kaplan
In Proceedings of the ACM-SIAM SODA'03 Conference . 2003.

A Case for Associative Peer to Peer Overlays. E. Cohen, A. Fiat, and H. Kaplan
In Proceedings of HotNets-I . 2002.

Replication strategies in unstructured Peer-to-Peer networks. E. Cohen and S. Shenker
In Proceedings of the ACM SIGCOMM'02 Conference . 2002.

Predicting and bypassing end-to-end Internet service degradations. A. Bremler-Barr, E. Cohen, H. Kaplan, and Y. Mansour.
In Proceedings of the 2nd Sigcomm Internet Measurements Workshop. ACM 2002.

Balanced-replication algorithms for distribution trees. E. Cohen and H. Kaplan.
In Proceedings of the 10th European Symposium on Algorithms . LLNCS vol.xxxx, 2002.

Search and replication in unstructured peer-to-peer networks. Q. Lv, P. Cao, E. Cohen, K. Li, S. Shenker.
In Proceedings of the 16th annual ACM International Conference on supercomputing (ICS) 2002; In Proc. 2002 ACM SIGMETRICS conference (2-page poster). 2002.

Labeling dynamic XML trees E. Cohen, H. Kaplan, T. Milo.
In Proc. 21st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS). 2002.

Reachability and distance queries via 2-hop labels. E. Cohen, E. Halperin, H. Kaplan, and U. Zwick.
In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM, 2002.

Aging through cascaded caches: performance issues in the distribution of Web content. E. Cohen, and H. Kaplan
In Proceedings of the ACM SIGCOMM'01 Conference . 2001.

Competitive analysis of the LRFU paging algorithm. E. Cohen, H. Kaplan, and U. Zwick
In Proceedings of the 7th International Workshop on Algorithms and Data Structures . 2001.

Performance aspects of distributed caches using TTL-based consistency. E. Cohen, E. Halperin, and H. Kaplan.
In Proceedings of the ICALP'01 conference, Springer-Verlag, LNCS. 2001.

Restoration by Path Concatenation: Fast Recovery of MPLS Paths. A. Bremler-Barr, Y. Afek, E. Cohen, H. Kaplan, M. Merritt.
In Proceedings of the ACM PODC '01 conference; In Proceedings of the ACM SIGMETRICS '01 conference (2-page Poster). 2001.

Refreshment policies for Web content caches. E. Cohen and H. Kaplan.
In Proceedings of the IEEE INFOCOM'01 Conference. 2001.

The age penalty and its effect on cache performance. E. Cohen and H. Kaplan.
In Proceedings of the 3rd USENIX Symposium on Internet Technologies and Systems (USITS). 2001.

Proactive caching of DNS records: Addressing a performance bottleneck. E. Cohen and H. Kaplan.
In Proc. of the 2001 Symposium on Applications and the Internet (SAINT). IEEE, 2001.

Connection caching under various models of communication. E. Cohen, H. Kaplan, and U. Zwick,
In Proc. 12th Annual ACM Symposium on Parallel Algorithms and Architectures. ACM, 2000.

Prefetching the means for document transfer: A new approach for reducing Web latency E. Cohen and H. Kaplan.
In Proceedings of the IEEE INFOCOM'00 Conference. 2000.

Finding interesting associations without support pruning, R. Motwani, E. Cohen, M. Datar, S. Fujiware, A. Gionis, P. Indyk, J. Ullman, and C. Yang.
In: Proc. of the 16th International conference on Data engineering. IEEE, 2000.

Policies for managing TCP connections under persistent HTTP. E. Cohen, H. Kaplan, and J. D. Oldham.
In Proc. of the 8th World Wide Web conference. 1999.

Connection caching. E. Cohen, H. Kaplan, and U. Zwick,
In Proc. 31st Annual ACM Symposium on Theory of Computing. ACM, 1999.

Exploiting Regularities in Web Traffic Patterns for Cache Replacement. E. Cohen and H. Kaplan,
In Proc. 31st Annual ACM Symposium on Theory of Computing. ACM, 1999.

Efficient Algorithms for Predicting Requests to Web Servers E. Cohen, B. Krishnamurthy, and J. Rexford.
In Proceedings of the IEEE INFOCOM'99 Conference . 1999.

LP-Based Analysis of Greedy-Dual-Size. E. Cohen and H. Kaplan.
In Proc. 10th ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM, 1999.

Improving end-to-end performance of the Web using server volumes and proxy filters. E. Cohen, B. Krishnamurthy, and J. Rexford
In Proceedings of the ACM SIGCOMM'98 Conference . 1998.

Evaluating server-assisted cache replacement in the Web. E. Cohen, B. Krishnamurthy, and J. Rexford
In Proceedings of the 6th European Symposium on Algorithms . LLNCS vol.1461, 1998.

Learning noisy perceptrons by a perceptron in polynomial time. E. Cohen.
In Proc. 38th IEEE Annual Symposium on Foundations of Computer Science. IEEE, 1997.

All pairs small stretch paths. E. Cohen and U. Zwick.
In Proc. 8th ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM, pages 93--102, 1997.

Approximating matrix multiplication for pattern recognition tasks. E. Cohen and D. Lewis.
In Proc. 8th ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM, pages 682--691, 1997.

Optimizing multiplications of sparse matrices. E. Cohen. In W. H. Cunningham, S. T. McCormick, and M. Queyranne, editors, Proc. of the 5th International Conference on Integer Programming and Combinatorial Optimization, pages 219--233. Springer-Verlag, Lecture Notes in Computer Science Vol. 1084, 1996.

Multi-rate detection for the IS-95A CDMA forward traffic channel using the 13kbs speach coder. E. Cohen and H.-L. Lou. In Proc. IEEE International Communications Conference. IEEE, 1996.

When piecewise determinism is almost true. E. Cohen, Y.-M. Wang, and G. Suri.
In Proc. Pacific Rim International Symposium on Fault-Tolerant Systems, pages 66--71, December 1995.

Multi-rate detection for the IS-95 CDMA forward traffic channel. E. Cohen and H.-L. Lou.
In Proc. IEEE Global Telecommunications Conference, pages 1789--1793. IEEE, 1995.

Improvise: Interactive Multimedia Process Visualization Environment. N. S. Barghouti, E. Koutsofios, and E. Cohen.
In Wilhelm Schäfer, editor, Proceedings of the Fifth European Software Engineering Conference (ESEC'95). Springer-Verlag, September 1995.

Estimating the size of the transitive closure in linear time. E. Cohen.
In Proc. 35th IEEE Annual Symposium on Foundations of Computer Science, pages 190--200. IEEE, 1994.

Polylog-time and near-linear work approximation scheme for undirected shortest-paths. E. Cohen.
In Proc. 26th Annual ACM Symposium on Theory of Computing, pages 16--26. ACM, 1994.

Efficient parallel shortest-paths in digraphs with a separator decomposition. E. Cohen.
In Proc. 5th annual ACM Symposium on Parallel Algorithms and Architectures, pages 57--67. ACM, 1993.

Using selective path-doubling for parallel shortest-path computations. E. Cohen.
In Proc. of the 2nd Israeli Symposium on the Theory of Computing and Systems, pages 78--87. IEEE, 1993.

Fast algorithms for t-spanners and stretch-t paths. E. Cohen.
In Proc. 34th IEEE Annual Symposium on Foundations of Computer Science, pages 648--658. IEEE, 1993.

Approximate max-flow on small depth networks. E. Cohen.
In Proc. 33rd IEEE Annual Symposium on Foundations of Computer Science, pages 648--658. IEEE, 1992.

New algorithms for generalized network flows. E. Cohen and N. Megiddo.
In D. Dolev, Z. Galil, and M. Rodeh, editors, Proc. of the 1st Israeli Symposium on the Theory of Computing and Systems, pages 103--114. Springer-Verlag, Lecture Notes in Computer Science Vol. 601, 1992.

Improved algorithms for linear inequalities with two variables per inequality. E. Cohen and N. Megiddo.
In Proc. 23rd Annual ACM Symposium on Theory of Computing, pages 145--155. ACM, 1991.

Complexity analysis and algorithms for some flow problems. E. Cohen and N. Megiddo.
In Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms, pages 120--130. ACM-SIAM, 1991.

Strongly polynomial and NC algorithms for detecting cycles in dynamic graphs. E. Cohen and N. Megiddo.
In Proc. 21st Annual ACM Symposium on Theory of Computing, pages 523--534. ACM, 1989.

Ph.D. Thesis:

Combinatorial Algorithms for Optimization Problems. E. Cohen.
PhD thesis, Department of Computer Science, Stanford University, Stanford, Ca., 1991.

Book chapters:

The Time-to-Live based consistency mechanism. E. Cohen and H. Kaplan.
Web Content Delivery, Tang, X. and Xu, J. and Chanson, S. T., (Eds.), Springer, New York, 2005.
Shortest Paths. E. Cohen.
Handbook of applied optimization, P.M. Pardalos and M.G.C. Resende, (Eds.), Oxford University Press, New York, 2002.

Journal Papers:

Associative Search in Peer to Peer Networks: Harnessing Latent Semantics. E. Cohen, A. Fiat, and H. Kaplan. Computer Networks.51(8):1861--1881, 2007.

Spatially-Decaying Aggregation over a Network. E. Cohen and H. Kaplan. JCSS. 73(3):265-288, 2007.

Making Routing Robust to Changing Traffic Demands: Algorithms and Evaluation. D. Applegate and E. Cohen. IEEE/ACM Transactions on Networking. 16(6):1193-1206, 2006.

A Short Walk in The Blogistan E. Cohen and B. Krishnamurthy.
Computer Networks 50(5):615-630 2006.

Maintaining Time-Decaying Stream Aggregates E. Cohen and M. Strauss.
J. Algorithms , 59(1):19-36, 2006.

Optimal oblivious routing in polynomial time. Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Räcke. JCSS 69(3):383-394 2004. Special issue of selected STOC 2003 papers.

Performance Aspects of Distributed Caches Using TTL-based Consistency. E. Cohen, E. Halperin, and H. Kaplan. Theoretical Computer Science. Special issue of selected ICALP 2001 papers. 331(1):73-96, 2005.

Making Intra-Domain Routing Robust to Changing and Uncertain Traffic Demands: Understanding Fundamental Tradeoffs. D. Applegate and E. Cohen. Computer Communication Review. 33(4), 2003.

Balanced-replication algorithms for distribution trees. E. Cohen and H. Kaplan.
SIAM J. Comput. 34(1):227-247, 2005.

Reachability and distance queries via 2-hop labels. E. Cohen, E. Halperin, H. Kaplan, and U. Zwick.
SIAM J. Comput. 32(5):1338-1355 , 2003.

Predicting and bypassing end-to-end Internet service degradations. A. Bremler-Barr, E. Cohen, H. Kaplan and Y. Mansour.
IEEE J. on Selected Areas in Communication (JSAC special issue in Internet and WWW Measurement, Mapping, and Modeling). 21(6):961-978, 2003.

Proactive caching of DNS records: Addressing a performance bottleneck. E. Cohen and H. Kaplan.
Computer Networks 41(6):707-726, 2003.

Connection caching: model and algorithms. E. Cohen, H. Kaplan, and U. Zwick.
J. Comput. System Sci. 67(1):92-126, 2003.

A Case for Associative Peer to Peer Overlays. E. Cohen, H. Kaplan, and A. Fiat. Computer Communication Review. 33(1):95-100, 2003.

Replication strategies in unstructured Peer-to-Peer networks. E. Cohen and S. Shenker. Computer Communication Review. 32(4):177-190, 2002.

Restoration by Path Concatenation: Fast recovery of MPLS paths. A. Bremler-Barr, Y. Afek, E. Cohen, H. Kaplan, M. Merritt.
Distributed Computing. (Special issue of selected PODC '01 papers) 15:273-283. 2002.

Competitive Analysis of the LRFU Paging Algorithm. E. Cohen, H. Kaplan, and U. Zwick.
Algorithmica. 33:511-516, 2002.

Prefetching the means for document transfer: a new approach for reducing Web latency. E. Cohen and H. Kaplan.
Computer Networks. 39(4): 437-455, 2002.

Exploiting Regularities in Web Traffic Patterns for Cache Replacement. E. Cohen and H. Kaplan.
Algorithmica 33(3):300-334, 2002. (dedicated issue on Internet Algorithmics.)

Refreshment policies for Web content caches. E. Cohen and H. Kaplan.
Computer Networks, 38(6):795-808, 2002.

Caching documents with varying sizes and fetching costs: an LP-based approach. E. Cohen and H. Kaplan.
Algorithmica , 32(3):459-466, 2002.

Aging through cascaded caches: performance issues in the distribution of Web content. E. Cohen and H. Kaplan
Computer Communication Review. 31(4):41-54, 2001.

Finding interesting associations without support pruning. R. Motwani, E. Cohen, M. Datar, S. Fujiware, A. Gionis, P. Indyk, J. Ullman, and C. Yang.
IEEE Transactions on Knowledge and Data Engineering (special issue), 13:64-78 , 2001.

All pairs small stretch paths. E. Cohen and U. Zwick.
J. Algorithms , 38:335-353. 2001.

Polylog-time and near-linear work approximation scheme for undirected shortest-paths. E. Cohen.
J. Assoc. Comput. Mach., 47:132-166, 2000.

Managing TCP Connections under Persistent HTTP. E. Cohen, H. Kaplan, and J. D. Oldham.
Computer Networks. 31:1709--1723, 1999.

Approximating matrix multiplication for pattern recognition tasks. E. Cohen and D. Lewis.
J. Alg. (special issue of selected papers from SODA'97), 30:211-252, 1999.

Structure prediction and computation of sparse matrix products. E. Cohen.
J. Combinatorial Optimization, 2:307-332, 1999.

Fast algorithms for t-spanners and stretch-t paths. E. Cohen.
SIAM J. Comput., 28:210--236, 1999.

Improving end-to-end performance of the Web using server volumes and proxy filters. E. Cohen, B. Krishnamurthy, and J. Rexford
Computer Communication Review. 28(4):241-253. 1998.

Size-estimation framework with applications to transitive closure and reachability. E. Cohen.
J. Comput. System Sci. (special issue of selected papers from FOCS'94). 55:441--453, 1997.

Using selective path-doubling for parallel shortest-path computations. E. Cohen.
J. Alg., 22:30--56, 1997.

Efficient parallel shortest-paths in digraphs with a separator decomposition. E. Cohen.
J. Alg., 21:331--357, 1996.

Approximate max-flow on small depth networks. E. Cohen.
SIAM J. Comput., 24:579--597, 1995.

Complexity analysis and algorithms for some flow problems. E. Cohen and N. Megiddo.
Algorithmica, 11:320--340, 1994.

Improved algorithms for linear inequalities with two variables per inequality. E. Cohen and N. Megiddo.
SIAM J. Comput., 23:1313--1347, 1994.

New algorithms for generalized network flows. E. Cohen and N. Megiddo.
Math. Prog., 64:325--336, 1994.

Strongly polynomial time and NC algorithms for detecting cycles in periodic graphs. E. Cohen and N. Megiddo.
J. Assoc. Comput. Mach., 40:791--830, 1993.

Maximizing concave functions in fixed dimension. E. Cohen and N. Megiddo.
In P. M. Pardalos, editor, Complexity in Numerical Optimization, pages 74--87. World Scientific, 1993.

Recognizing properties of periodic graphs. E. Cohen and N. Megiddo.
In P. Gritzmann and Sturmfels B., editors, Applied Geometry and Discrete Math. The "Victor Klee Festschrift", volume 4, pages 135--146. ACM AMS, 1991.

NP-completeness of graph decomposition problems. E. Cohen and M. Tarsi.
J. Complexity, 7:200--212, 1991.

August, 2003
edith@research.att.com