Fabian Kuhn - Publications

Ph.D. Thesis

• The Price of Locality: Exploring the Complexity of Distributed Coordination Primitives
  Fabian Kuhn.
  PhD Thesis, ETH Zurich, Diss. ETH No. 16213, December 2005.
  

Journal Papers

• Ad Hoc Networks Beyond Unit Disk Graphs
  Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger.
  Wireless Networks, Volume 14, Number 5, October 2008.
  
• Distributed Selection: A Missing Piece of Data Aggregation
  Fabian Kuhn, Thomas Locher, and Roger Wattenhofer.
  Communications of the ACM, Volume 51, Number 9, September 2008.
  
• An Algorithmic Approach to Geographic Routing in Ad Hoc and Sensor Networks
  Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger.
  IEEE/ACM Transactions on Networking, Volume 16, Number 1, February 2008.
  
• Improved Approximation Algorithms for Connected Sensor Cover
  Stefan Funke, Alex Kesselman, Fabian Kuhn, Zvi Lotker, and Michael Segal.
  Wireless Networks, Volume 13, Number 2, April 2007.
  
• Dynamic Analysis of the Arrow Distributed Protocol
  Maurice Herlihy, Fabian Kuhn, Srikanta Tirthapura, and Roger Wattenhofer.
  Theory of Computing Systems, Volume 39, Number 6, November 2006
  
• Efficient Adaptive Collect using Randomization
  Hagit Attiya, Fabian Kuhn, C. Greg Plaxton, Mirjam Wattenhofer, and Roger Wattenhofer.
  Distributed Computing, Volume 18, Number 3, February 2006.
  
• Constant-Time Distributed Dominating Set Approximation
  Fabian Kuhn and Roger Wattenhofer.
  Distributed Computing, Volume 17, Number 4, May 2005.
  

Conference Papers

• The Wireless Synchronization Problem
  Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Fabian Kuhn, and Calvin Newport.
  28th ACM Symposium on Principles of Distributed Computing (PODC), Calgary, Canada, August 2009.
  
• Gradient Clock Synchronization in Dynamic Networks
  Fabian Kuhn, Thomas Locher, and Rotem Oshman.
  21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, Canada, August 2009.
  
• Weak Graph Coloring: Distributed Algorithms and Applications
  Fabian Kuhn.
  21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, Canada, August 2009.
  
• On the Treeness of Internet Latency and Bandwidth
  Venugopalan Ramasubramanian, Dahlia Malkhi, Fabian Kuhn, Mahesh Balakrishnan, Archit Gupta, and Aditya Akella.
  11th ACM Joint Conference on Measurement and Modeling of Computer Systems (SIGMETRICS/Performance), Seattle, Washington, USA, June 2009.
  
• Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time (full version)
  Fabian Kuhn.
  26th Symposium on Theoretical Aspects of Computer Science (STACS), Freiburg, Germany, February 2009.
  
• Distributed Computation of the Mode
  Fabian Kuhn, Thomas Locher, and Stefan Schmid.
  27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada, August 2008.
  
• Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings
  Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, and Kunal Talwar.
  27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada, August 2008.
  
• Understanding Radio Irregularity in Wireless Networks
  Torsten Muetze, Patrick Stuedi, Fabian Kuhn, and Gustavo Alonso.
  5th IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), San Francisco, California, June 2008.
  
• Reconstructing Approximate Tree Metrics
  Ittai Abraham, Mahesh Balakrishnan, Fabian Kuhn, Dahlia Malkhi, Venugopalan Ramasubramanian, and Kunal Talwar.
  26th ACM Symposium on Principles of Distributed Computing (PODC), Portland, Oregon, USA, August 2007.
  
• Tight Bounds for Distributed Selection (SPAA Best Paper Award)
  Fabian Kuhn, Thomas Locher, and Roger Wattenhofer.
  19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego, California, USA, June 2007.
  
• Distributed Approximation of Capacitated Dominating Sets
  Fabian Kuhn and Thomas Moscibroda.
  19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego, California, USA, June 2007.
  
• On the Complexity of Distributed Graph Coloring
  Fabian Kuhn and Roger Wattenhofer.
  25th ACM Symposium on Principles of Distributed Computing (PODC), Denver, Colorado, USA, July 2006.
  
• Fault-Tolerant Clustering in Ad Hoc and Sensor Networks
  Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer.
  26th International Conference on Distributed Computing Systems (ICDCS), Lisbon, Portugal, July 2006.
  
• A Blueprint for Constructing Peer-to-Peer Systems Robust to Dynamic Worst-Case Joins and Leaves
  Fabian Kuhn, Stefan Schmid, Joest Smit, and Roger Wattenhofer.
  14th IEEE International Workshop on Quality of Service (IWQoS), Yale University, New Haven, Connectitut, USA, June 2006.
  
• The Price of Being Near-Sighted
  Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer.
  17th ACM-SIAM Symposium on Discrete Algorithms (SODA) Miami, Florida, USA, January 2006.
  
• Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs
  Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, and Roger Wattenhofer.
  19th International Symposium on Distributed Computing (DISC), Cracow, Poland, September 2005.
  
• Local Approximation Schemes for Ad Hoc and Sensor Networks
  Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, and Roger Wattenhofer.
  3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, Germany, September 2005.
  
• Interference in Cellular Networks: The Minimum Membership Set Cover Problem
  Fabian Kuhn, Pascal von Rickenbach, Roger Wattenhofer, Emo Welzl, and Aaron Zollinger.
  11th International Computing and Combinatorics Conference (COCOON), Kunming, Yunnan, China, August 2005.
  
• On the Locality of Bounded Growth
  Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer.
  24th ACM Symposium on the Principles of Distributed Computing (PODC), Las Vegas, Nevada, USA, July 2005.
  
• A Self-Repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn
  Fabian Kuhn, Stefan Schmid, and Roger Wattenhofer.
  4th International Workshop on Peer-To-Peer Systems (IPTPS), Cornell University, Ithaca, New York, USA, February 2005.
  
• Efficient Adaptive Collect using Randomization
  Hagit Attiya, Fabian Kuhn, Mirjam Wattenhofer, and Roger Wattenhofer. (DISC Best Student Paper Award)
  18th Annual Conference on Distributed Computing (DISC), Amsterdam, Netherlands, October 2004.
  
• Unit Disk Graph Approximation
  Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer.
  ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Philadelphia, Pennsylvania, USA, October 2004.
  
• Initializing Newly Deployed Ad Hoc and Sensor Networks
  Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer.
  10th Annual International Conference on Mobile Computing and Networking (MOBICOM), Philadelphia, USA, September 2004.
  
• Radio Network Clustering from Scratch
  Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer.
  12nd Annual European Symposium on Algorithms (ESA), Bergen, Norway, September 2004.
  
• What Cannot Be Computed Locally!
  Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. (PODC Best Student Paper Award)
  23rd ACM Symposium on the Principles of Distributed Computing (PODC), St. John's, Newfoundland, Canada, July 2004.
  
• Dynamic Analysis of the Arrow Distributed Protocol
  Fabian Kuhn and Roger Wattenhofer.
  16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Barcelona, Spain, June 2004.
  
• Ad-Hoc Networks Beyond Unit Disk Graphs
  Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger.
  1st ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), San Diego, California, USA, September 2003.
  
• Constant-Time Distributed Dominating Set Approximation
  Fabian Kuhn and Roger Wattenhofer. (PODC Best Student Paper Award)
  22nd ACM Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA, July 2003.
  
• Geometric Ad-Hoc Routing: Of Theory and Practice
  Fabian Kuhn, Roger Wattenhofer, Yan Zhang, and Aaron Zollinger.
  22nd ACM Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA, July 2003.
  
• Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing
  Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger.
  4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), Annapolis, Maryland, USA, June 2003.
  
• Asymptotically Optimal Geometric Mobile Ad-Hoc Routing
  Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger.
  6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), Atlanta, Georgia, September 2002.
  
• Random Walks Revisited: Extensions of Pollard's Rho Algorithm for Computing Multiple Discrete Logarithms
  Fabian Kuhn and René Struik.
  8th Annual Workshop on Selected Areas in Cryptography (SAC), Toronto, Ontario, Canada, August 2001.