Adam Kirsch's Publications

This page lists my publications. For more information about me, please visit my main page.

    Thesis

  1. Hash-Based Data Structures for Extreme Conditions, Ph.D. Thesis, Harvard University, 2008. pdf (single-spaced, hyperlinked)

    Submitted, Accepted, or Otherwise Unpublished Works

  2. "More Robust Hashing: Cuckoo Hashing with a Stash," with M. Mitzenmacher and U. Wieder. To appear in ESA 2008. pdf

  3. "The Power of One Move: Hashing Schemes for Hardware," with M. Mitzenmacher. This preprint is an extended version of the INFOCOM paper below. pdf

  4. "The Hiring Problem and Lake Wobegon Strategies," with A. Z. Broder, R. Kumar, M. Mitzenmacher, E. Upfal, and S. Vassilvitskii. This preprint is an extended version of the SODA paper below. pdf

  5. "Directly Lower Bounding the Information Capacity for Channels with I.I.D. Deletions and Duplications," with E. Drinea. This preprint is an extended version of the ISIT paper below. pdf

    Conference and Journal Publications

  6. "Less Hashing, Same Performance: Building a Better Bloom Filter," with M. Mitzenmacher. Random Structures and Algorithms, 33(2):187-218. pdf

  7. "The Power of One Move: Hashing Schemes for Hardware," with M. Mitzenmacher. In Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM), 2008. pdf

  8. "Simple Summaries for Hashing with Choices," with M. Mitzenmacher. IEEE/ACM Transactions on Networking, 16(1):218-231, 2008. pdf

  9. "The Hiring Problem and Lake Wobegon Strategies," with A. Z. Broder, R. Kumar, M. Mitzenmacher, E. Upfal, and S. Vassilvitskii. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1184-1193, 2008. pdf. Extended draft version: pdf

  10. "Using a Queue to De-amortize Cuckoo Hashing in Hardware," with M. Mitzenmacher. In Proceedings of the Forty-Fifth Annual Allerton Conference on Communication, Control, and Computing, 2007. pdf

  11. "Directly Lower Bounding the Information Capacity for Channels with I.I.D. Deletions and Duplications," with E. Drinea. In Proceedings of the IEEE Symposium on Information Theory (ISIT), pp. 1731-1735, 2007. pdf

  12. "On Threshold Behavior in Query Incentive Networks," with E. Arcaute, R. Kumar, D. Liben-Nowell, and S. Vassilvitskii. In Proceedings of the 8th ACM Conference on Electronic Commerce (EC), pp. 66-74, 2007. pdf

  13. "Less Hashing, Same Performance: Building a Better Bloom Filter," with M. Mitzenmacher. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA), pp. 456-467, 2006. pdf. Technical report version: pdf

  14. "Distance-Sensitive Bloom Filters," with M. Mitzenmacher. In Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX), 2006. pdf

  15. "Simple Summaries for Hashing with Multiple Choices," with M. Mitzenmacher. In Proceedings of the Forty-Third Annual Allerton Conference on Communication, Control, and Computing, 2005. pdf

  16. "TBBL: A Tree-Based Bidding Language for Iterative Combinatorial Exchanges," with R. Cavallo, D. C. Parkes, A. I. Juda, A. Kulesza, S. Lahaie, B. Lubin, L. Michael, and J. Shneidman. In the Multidisciplinary Workshop on Advances in Preference Handling (IJCAI), 2005. pdf

  17. "Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input," with A. Anagnostopoulos and E. Upfal. SIAM Journal on Computing, 34(3):616-639, 2005. pdf

  18. "Stability and Efficiency of a Random Local Load Balancing Protocol," with A. Anagnostopoulos and E. Upfal. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 472-481, 2003. pdf
© Copyright Notice: The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.