Micah Adler's Publications

Algorithms for Internet Security

Efficient Probabilistic Packet Marking Qunfeng Dong, Micah Adler, Suman Banerjee, Kazu Hirata. In Proceedings of International Conference on Network Protocols (ICNP), November 2005.
Towards Asymptotic Optimality in Probabilistic Packet Marking Micah Adler, Jeff Edmonds, and Jiri Matousek, in Proceedings of ACM Symposium on Theory of Computing (STOC) 2005.
Defending Anonymous Communication Against Passive Logging Attacks Matthew Wright, Micah Adler, Brian N. Levine, and Clay Schields, in Proceedings of IEEE Symposium on Security and Privacy 2003.
Randomized Pursuit-Evasion in Graphs Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, and Berthold Vöcking, in Proceedings of 29th International Colloquium on Automata, Languages, and Programming (ICALP) 2002.
Tradeoffs in Probabilistic Packet Marking for IP Traceback Micah Adler. In Journal of the ACM, Volume 52 , Issue 2 (March 2005). Pages: 217 - 244. Preliminary version in Proceedings of 34th ACM Symposium on Theory of Computing (STOC) 2002.
An Analysis of the Degradation of Anonymous Protocols Matthew Wright, Micah Adler, Brian N. Levine, and Clay Schields, in Proceedings of Symposium on Network and Distributed System Security (NDSS) 2002. (Winner of Outstanding Paper Award.)

Collecting Information in Sensor Networks

On Optimal Communication Cost for Gathering Correlated Data Through Wireless Sensor Networks Junning Liu, Micah Adler, Don Towsley, Chun Zhang. In Proceedings of MOBICOM, 2006: 310-321.
On the Capacity of Information Networks. Micah Adler, Nicholas Harvey, Kamal Jain and Robert Kleinberg, April Rasala Lehman. In Special Issue of the IEEE Transactions on Information Theory and the IEEE/ACM Transactions on Networking, 52(6):2345-2364, June 2006. Preliminary version in Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2006.
Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding. Micah Adler, Erik Demaine, Nicholas Harvey, Mihai Patrascu. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2006.
On the Distance Entropy of a Data Collection Network. Junning Liu, Micah Adler, Don Towsley, in Second Workshop on Spatial Stochastic Modeling of Wireless Networks, 2006.
Collecting Correlated Information from a Sensor Network. Micah Adler. In Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2005.

Bandwidth Efficient Network Protocols

Estimation of Congestion Price Using Probabilistic Packet Marking. Micah Adler, Jin-Yi Cai, Jonathan K. Shapiro, and Don Towsley, in Proceedings of Infocom 2003.
Optimal Proxy Cache Allocation for Efficient Streaming Media Distribution. Bing Wang, Subhabrata Sen, Micah Adler, and Don Towsley, in Proceedings of Infocom 2002.
New Protocols for Asymmetric Communication Channels. John Watkinson, Micah Adler, and Faith Fich, in Proceedings of 8th International Colloquium on Structural Information and Communication Complexity (Sirocco) 2001.
Tight Size Bounds for Packet Headers in Narrow Meshes. Micah Adler, Faith Fich, Leslie Ann Goldberg, and Mike Paterson, in Proceedings of 27th International Colloquium on Automata, Languages and Programming (ICALP) 2000.
The Complexity of End-to-End Communication in Memoryless Networks. Micah Adler and Faith Fich, in Proceedings of 18th ACM Symposium on Principles of Distributed Computing (PODC) 1999.
Protocols for Asymmetric Communication Channels. Micah Adler and Bruce Maggs, in Proceedings of 39th IEEE Symposium on Foundations of Computer Science (FOCS) 1998. Also in FOCS '98 special issue of Journal of Computer and System Sciences.
A Modular Analysis of Network Transmission Protocols, Micah Adler, Yair Bartal, John W. Byers, Michael Luby, and Danny Raz, in Proceedings of 5th Israeli Symposium on Theory of Computing and Systems (ISTCS) 1997.

Load Balancing and Scheduling

Optimal Selection of Peers for P2P Downloading and Streaming Micah Adler, Rakesh Kumar, Keith Ross, Dan Rubenstein, Torsten Suel, and David Yao. In Proceedings of Infocom 2005.
Load Balancing in Hypercubic Distributed Hash Tables with Heterogeneous Processors Junning Liu and Micah Adler. In Proceedings of European Symposium on Algorithms (ESA) 2004.
A Proportionate Fair Scheduling Rule with Good Worst-case Performance Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Goldberg, Paul Goldberg and Mike Paterson, in Proceedings of Fifteenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2003.
Asumptotically Optimal Worksharing in HNOWs: How Long is "Sufficiently Long"? Micah Adler, Ying Gong and Arnold L. Rosenberg, in Proceedings of 36th Annual Simulation Symposium, 2003.
Optimal Sharing of Bags of Tasks in Heterogeneous Clusters Micah Adler, Ying Gong and Arnold L. Rosenberg, in Proceedings of Fifteenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2003.
A Stochastic Process on the Hypercube with Applications to Peer-to-peer Networks Micah Adler, Eran Halperin, Richard Karp and Vijay Vazirani, in Proceedings of 35th ACM Symposium on Theory of Computing (STOC) 2003.
Deadline Fair Scheduling: Bridging the Theory and Practice of Proportionate-Fair Scheduling in Multiprocessor Servers Abhishek Chandra, Micah Adler, and Prashant Shenoy, in Proceedings of IEEE Real-time Technology and Applications Symposium (RTAS), 2001.
Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors Abhishek Chandra, Micah Adler, Pawan Goyal and Prashant Shenoy, in Proceedings of the Fourth Symposium on Operating System Design and Implementation (OSDI) 2000.
Analyzing an Infinite Parallel Job Allocation Process Micah Adler, Petra Berenbrink and Klaus Schröder, in Proceedings of the 6th European Symposium on Algorithms (ESA), 1998.
Parallel Randomized Load Balancing. Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, and Lars Rasmussen, in Proceedings of ACM Symposium on Theory of Computing (STOC) 1995. Also in Randomized Structures and Algorithms.
Scheduling Parallel Communication: The h-relation Problem , Micah Adler, John W. Byers and Richard M. Karp, in Proceedings of Mathematical Foundations of Computer Science (MFCS) 1995.

Multicasting

Using Multicast for Streaming Videos across Wide Area Networks . Bing Wang, Subhabrata Sen, Micah Adler, and Don Towsley, in Proceedings of GLOBECOM 2003
Pricing Multicasting in More Practical Network Models. Micah Adler and Dan Rubenstein, in Proceedings of 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2002.
Tree Layout for Internal Network Characterizations in Multicast Networks Micah Adler, Tian Bu, Ramesh Sitaraman, and Don Towsley, in Proceedings of 3rd International Workshop on Networked Group Communication (NGC) 2001.
Channelization Problem in Large Scale Data Dissemination Micah Adler, Zihui Ge, James Kurose, Don Towsley, and Stephen Zabele, in Proceedings of the 9th IEEE International Conference on Network Protocols (ICNP) 2001.
Compression Using Efficient Multicasting Micah Adler and Tom Leighton, in Proceedings of 32nd ACM Symposium on Theory of Computing (STOC) 2000.

Packet Routing in Emerging Technologies

Minimum Energy Reliable Paths Using Unreliable Wireless Links Qunfeng Dong, Micah Adler, Suman Banerjee, and Archan Misra. In Proceedings of ACM Mobihoc, Urbana-Champaign, IL, May 2005.
Tight Bounds for the Performance of Longest in System on DAGs Micah Adler and Adi Rosen. In Proceedings of STACS 2002. (Invitation to STACS 2002 special issue regretfully had to be declined.)
Time-Constrained Scheduling of Weighted Packets on Trees and Meshes Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman and Adi Rosen, in Proceedings of 11th ACM Symposium on Parallel Algorithms and Architectures (SPAA) 1999.
Efficient Communication Strategies for Ad-Hoc Wireless Networks Micah Adler and Christian Scheideler, in Proceedings of 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA) 1998. Also in SPAA '98 special issue of Theory of Computing Systems.
Scheduling Time-Constrained Communication in Linear Networks Micah Adler, Arnold L. Rosenberg, Ramesh K. Sitaraman, and Walter Unger, in Proceedings of 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA) 1998.
Asynchronous Shared Memory Search Structures Micah Adler, in Proceedings of 8th ACM Symposium on Parallel Algorithms and Architectures (SPAA) 1996. Full version in Theory of Computing Systems 31, 377-401, 1998 (SPAA '96 special issue).

The World Wide Web

Optimal Website Design with the Constrained Subtree Selection Problem Brent Heeringa and Micah Adler. In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP) 2004.
Towards Compressing Web Graphs Micah Adler, Michael Mitzenmacher, in Proceedings of the IEEE Data Compression Conference (DCC), 2001.
Scheduling Space-Sharing for Internet Advertising Micah Adler, Phil B. Gibbons and Yossi Matias, Journal of Scheduling. Patent application approved, September 1999. See also the Collager Home Page.

Parallel Computing with Limited Bandwidth

Communication-Optimal Parallel Minimum Spanning Tree Algorithms Micah Adler, Wolfgang Dittrich, Ben Juurlink, Miroslaw Kutylowski, and Ingo Rieping, in Proceedings of 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA) 1998.
Modeling Parallel Bandwidth: Local vs. Global Restrictions . Micah Adler, Phillip B. Gibbons, Yossi Matias, and Vijaya Ramachandran, in Proceedings of 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA) 1997. Also in Algorithmica.
Limited Bandwidth Parallel Computation . Micah Adler, Ph.D. dissertation, University of California at Berkeley, December 1996.
New Coding Techniques for Improved Bandwidth Utilization. Micah Adler, in Proceedings of 37th IEEE Symposium on Foundations of Computer Science (FOCS) 1996.
Parallel Sorting With Limited Bandwidth . Micah Adler, John W. Byers and Richard M. Karp, in Proceedings of 7th ACM Symposium on Parallel Algorithms and Architectures (SPAA) 1995. Also in SIAM Journal on Computing.
AT^2 Bounds for a Class of VLSI Problems and String Matching Micah Adler and John W. Byers, in Proceedings of 6th ACM Symposium on Parallel Algorithms and Architectures (SPAA) 1994.

Other areas of interest

Clustering Relational Data Using Attribute and Link Information Jen Neville, Micah Adler, and David Jensen, in Proceedings of the Text Mining and Link Analysis Workship, 18th International Joint Converence on Artificial Intelligence, 2003.
An n! Lower Bound On Formula Size Micah Adler and Neil Immerman, in Proceedings of IEEE Symposium on Logic in Computer Science (LICS) 2001. Also in LICS 2001 special issue of ACM-TOCL.
Selection In The Presence of Noise: The Design of Playoff Systems . Micah Adler, Peter Gemmel, Mor Harchol, Richard M. Karp, and Claire Kenyon, in Proceedings of ACM Symposium on Discrete Algorithms (SODA) 1994.

Back to Micah's homepage.