# Publications

Years: 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 | 2009 | 2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2002 | 2001

## 2016

*Conference papers*- Mohamad Ahmadi, Fabian Kuhn
**Multi-Message Broadcast in Dynamic Radio Networks**

2016 12th Int. Symp. on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS), Aarhus, Denmark - Dan Hefetz, Fabian Kuhn, Yannic Maus, Angelika Steger
**Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model**

2016 30th International Symposium on DIStributed Computing (DISC), Paris, September 26-30, 2016 - Fabian Kuhn, Sebastian Daum, Yannic Maus
**Rumor Spreading with Bounded In-Degree**

2016 23rd Int. Coll. on Structural Information and Communication Complexity (SIROCCO), Helsinki, Finland

## 2015

*Conference papers*- Fabian Kuhn, Anisur Rahaman Molla
**Distributed Sparse Cut Approximation**

2015 19th Int. Conf. on Principles of Distributed Systems (OPODIS), Rennes, France - Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, Anisur Rahaman Molla
**The Cost of Global Broadcast in Dynamic Radio Networks**

2015 19th Int. Conf. on Principles of Distributed Systems (OPODIS), Rennes, France - Abdolhamid Ghodselahi, Fabian Kuhn
**Serving Online Requests with Mobile Servers**

2015 26th Int. Symp. on Algorithms and Computation (ISAAC), Nagoya, Japan - Fabian Kuhn, Sebastian Daum, Yannic Maus
**Brief Announcement: Rumor Spreading with Bounded In-Degree**

2015 26th Int. Symp. on Distributed Computing (DISC), Tokyo, Japan - Sebastian Daum, Fabian Kuhn
**Tight Bounds for MIS in Multichannel Radio Networks**

2015 26th Int. Symp. on Distributed Computing (DISC), Tokyo, Japan - Seth Gilbert, Fabian Kuhn, Calvin Newport, Chaodong Zheng
**Efficient Communication in Cognitive Radio Networks**

2015 34th ACM Symp. on Principles of Distributed Computing (PODC), San Sebastián, Spain - Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, Boaz Patt-Shamir
**Near-Optimal Distributed Maximum Flow: Extended Abstract**

2015 34th ACM Symp. on Principles of Distributed Computing (PODC), San Sebastián, Spain - Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn
**Tight Bounds on Vertex Connectivity Under Vertex Sampling**

2015 26th ACM-SIAM Symp. on Discrete Algorithms (SODA), San Diego CA, USA - Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan
**Distributed Computation of Sparse Cuts via Random Walks**

2015 16th International Conference on Distributed Computing and Networking (ICDCN), Goa, India

*Journal Papers*- Majid Khabbazian, Stephane Durocher, Alireza Haghnegahdar, Fabian Kuhn
**Bounding Interference in Wireless Ad Hoc Networks With Nodes in Random Position**

2015*Ieee Acm T Network*, volume: 23, issue: 4, pages: 1078 - 1091

- Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan
**Distributed computation in dynamic networks via random walks.**

2015*Theor Comput Sci*, volume: 581, pages: 45 - 66

- Franziska Humair, Luc Humair, Fabian Kuhn, Christoph Kueffer
**E-commerce trade in invasive plants**

2015*Conserv Biol*, volume: 29, issue: 6, pages: 1658 - 1665

- Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan
**Efficient random walk sampling in distributed networks.**

2015*J Parallel Distr Com*, volume: 77, pages: 84 - 94

- Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan, Eli Upfal
**Fast distributed PageRank computation.**

2015*Theor Comput Sci*, volume: 561, pages: 113 - 121

## 2014

*Conference papers*- Andrew Drucker, Fabian Kuhn, Rotem Oshman
**On the Power of the Congested Clique Model**

2014 33rd ACM Symp. on Principles of Distributed Computing (PODC), Paris, France - Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn
**Distributed Connectivity Decomposition**

2014 33rd ACM Symp. on Principles of Distributed Computing (PODC), Paris, France - Karl Bringman, Fabian Kuhn, Konstantinos Panagiotou, Ueli Peter, Henning Thomas
**Internal DLA: Efficient Simulation of a Physical Growth Model**

2014 41st Int.l Colloquium on Automata, Languages, and Programming (ICALP), Copenhagen, Denmark - Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn
**A New Perspective on Vertex Connectivity**

2014 25th ACM-SIAM Symp. on Discrete Algorithms (SODA), Portland OR, USA

*Journal Papers*- Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, Nancy Lynch
**Decomposing Broadcast Algorithms Using Abstract MAC Layers**

2014*Ad Hoc Netw*, volume: 12, pages: 219 - 242

- Leonid Barenboim, Michael Elkin, Fabian Kuhn
**Distributed (Delta+1)-Coloring in Linear (in Delta) Time**

2014*Siam J Comput*, volume: 43, issue: 1, pages: 72 - 95

- Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch, Calvin Newport
**Structuring Unreliable Radio Networks**

2014*Distrib Comput*, volume: 27, issue: 1, pages: 1 - 19

## 2013

*Conference papers*- Sebastian Daum, Seth Gilbert, Fabian Kuhn, Calvin Newport
**Broadcast in the Ad Hoc SINR Model**

2013 27th Int. Symp. on Distributed Computing (DISC), Jerusalem, Israel , pages: 358 - 372 - Mohsen Ghaffari, Fabian Kuhn
**Distributed Minimum Cut Approximation (best paper award)**

2013 27th Int. Symp. on Distributed Computing (DISC), Jerusalem, Israel , pages: 1 - 15 - Sebastian Daum, Mohsen Ghaffari, Seth Gilbert, Fabian Kuhn, Calvin Newport
**Maximal Independent Sets in Multichannel Radio Networks**

2013 32nd ACM Symp. on Principles of Distributed Computing (PODC), Montreal, Canada , pages: 335 - 344

*Journal Papers*- Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn
**Beeping a Maximal Independent Set**

2013*Distrib Comput*, volume: 26, issue: 4, pages: 195 - 208

- Fabian Kuhn, Monaldo Mastrolilli
**Vertex Cover in Graphs with Locally Few Colors**

2013*Inform Comput*, volume: 222, pages: 265 - 277

## 2012

*Conference papers*- Sebastian Daum, Fabian Kuhn, Calvin Newport
**Efficient Symmetry Breaking in Multi-Channel Radio Networks**

2012 26th Int. Symp. on Distributed Computing (DISC), Salvador, Bahia, Brazil , pages: 238 - 252 - Bernhard Haeupler, Fabian Kuhn
**Lower Bounds on Information Dissemination in Dynamic Networks**

2012 26th International Symposium on Distributed Computing (DISC), Salvador, Bahia, Brazil , pages: 166 - 180 - Sebastian Daum, Seth Gilbert, Fabian Kuhn, Calvin Newport
**Leader Election in Shared Spectrum Radio Networks**

2012 31st ACM Symp. on Principles of Distributed Computing (PODC), Madeira, Portugal , pages: 215 - 224 - Andrew Drucker, Fabian Kuhn, Rotem Oshman
**The Communication Complexity of Distributed Task Allocation**

2012 31st ACM Symp. on Principles of Distributed Computing (PODC), Madeira, Portugal , pages: 67 - 76 - Antonio Carzaniga, Koorosh Khazaei, Fabian Kuhn
**Oblivious Low-Congestion Multicast Routing in Wireless Networks**

2012 13th ACM Int. Symp. on Mobile Ad Hoc Networking and Computing (MOBIHOC) , Hilton Head Island, SC, USA , pages: 155 - 164

## 2011

*Conference papers*- Fabian Kuhn, Rotem Oshman
**The Complexity of Data Aggregation in Directed Networks**

2011 25th Int. Symp. on Distributed Computing (DISC), Rome, Italy , pages: 416 - 431 - Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn
**Beeping a Maximal Independent Set**

2011 25th Int. Symp. on Distributed Computing (DISC), Rome, Italy , pages: 32 - 50 - Fabian Kuhn, Monaldo Mastrolilli
**Vertex Cover in Graphs with Locally Few Colors**

2011 38th Int. Colloquium on Automata, Languages and Programming (ICALP), Zurich, Switzerland , pages: 498 - 509 - Majid Khabbazian, Fabian Kuhn, Nancy Lynch, Muriel Médard, Ali ParandehGheibi
**MAC Design for Analog Network Coding**

2011 7th ACM Workshop on Foundations of Mobile Computing (FOMC), San Jose CA, USA , pages: 42 - 51 - Fabian Kuhn, Yoram Moses, Rotem Oshman
**Coordinated Consensus in Dynamic Networks**

2011 30th ACM Symp. on Principles of Distributed Computing (PODC), San Jose CA, USA , pages: 1 - 10 - Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch, Calvin Newport
**Structuring Unreliable Radio Networks**

2011 30th ACM Symp. on Principles of Distributed Computing (PODC), San Jose CA, USA , pages: 79 - 88

*Journal Papers*- Sebastian Daum, Ralf Werner
**A Novel Feasible Discretization Method for Linear Semi-infinite Programming Applied to Basket Option Pricing**

2011*Optimization*, volume: 60, issue: 10, pages: 1379 - 1398

- Fabian Kuhn, Rotem Oshman
**Dynamic Networks: Models and Algorithms**

2011*ACM SIGACT News*, volume: Volume 42, issue: 1

- Fabian Kuhn, Thomas Locher, Rotem Oshman
**Gradient Clock Synchronization in Dynamic Networks**

2011*Theor Comput Syst*, volume: 49, issue: 4, pages: 781 - 816

- Fabian Kuhn, Nancy Lynch, Calvin Newport
**The Abstract MAC Layer**

2011*Distrib Comput (Distributed Computing)*, volume: 24, issue: 3-4, pages: 187 - 206

## 2010

*Conference papers*- Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, Nancy Lynch
**Decomposing Broadcast Algorithms Using Abstract MAC Layers**

2010 6th ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cambridge MA, USA , pages: 13 - 22 - Alejandro Cornejo, Fabian Kuhn
**Deploying Wireless Networks with Beeps**

2010 24th Int. Symp. on Distributed Computing (DISC), Cambridge MA, USA , pages: 148 - 162 - Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, Andrea Richa
**Broadcasting in Unreliable Radio Networks**

2010 29th ACM Symp. on Principles of Distributed Computing (PODC), Zurich, Switzerland , pages: 336 - 345 - Fabian Kuhn, Christoph Lenzen, Thomas Locher, Rotem Oshman
**Optimal Gradient Clock Synchronization in Dynamic Networks**

2010 29th ACM Symp. on Principles of Distributed Computing (PODC), Zurich, Switzerland , pages: 430 - 439 - Fabian Kuhn, Nancy Lynch, Rotem Oshman
**Distributed Computation in Dynamic Networks**

2010 42nd ACM Symp. on Theory of Computing (STOC), Cambridge MA, USA , pages: 513 - 522 - Fabian Kuhn, Konstantinos Panagiotou, Joel Spencer, Angelika Steger.
**Synchrony and Asynchrony in Neural Networks**

2010 21st ACM-SIAM Symp. on Discrete Algorithms (SODA), Atlanta GA, USA , pages: 949 - 964

*Journal Papers*- Fabian Kuhn, Thomas Moscibroda
**Distributed Approximation of Capacitated Dominating Sets**

2010*Theor Comput Syst*, volume: 47, issue: 4, pages: 811 - 836

- Fabian Kuhn, Stefan Schmid, Roger Wattenhofer
**Towards Worst-Case Churn Resistant Peer-to-Peer Systems**

2010*Distrib Comput*, volume: Volume 22, issue: 4, pages: 249 - 267

## 2009

*Conference papers*- Fabian Kuhn, Rotem Oshman
**Gradient Clock Synchronization Using Reference Broadcasts**

2009 13th Int. Conf. on Principles of Distributed Systems (OPODIS), Nîmes, France , pages: 204 - 218 - Alejandro Cornejo, Fabian Kuhn, Ruy Ley-Wild, Nancy Lynch
**Keeping Mobile Robot Swarms Connected**

2009 23rd Int. Symp. on Distributed Computing (DISC), Elche, Spain , pages: 496 - 511 - Fabian Kuhn, Nancy Lynch, Calvin Newport
**The Abstract MAC Layer**

2009 23rd Int. Symp. on Distributed Computing (DISC), Elche, Spain , pages: 48 - 62 - Fabian Kuhn, Thomas Locher, Rotem Oshman
**Gradient Clock Synchronization in Dynamic Networks**

2009 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), Calgary, Canada , pages: 270 - 279 - Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Fabian Kuhn, Calvin Newport
**The Wireless Synchronization Problem**

2009 28th ACM Symp. on Principles of Distributed Computing (PODC), Calgary, Canada , pages: 190 - 199 - Fabian Kuhn
**Weak Graph Coloring: Distributed Algorithms and Applications**

2009 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), Calgary, Canada , pages: 138 - 144 - Venugopalan Ramasubramanian, Dahlia Malkhi, Fabian Kuhn, Mahesh Balakrishnan, Archit Gupta, Aditya Akella
**On the Treeness of Internet Latency and Bandwidth**

2009 11th ACM Joint Conf. on Measurement and Modeling of Computer Systems (SIGMETRICS/Performance), Seattle WA, USA , pages: 61 - 72 - Fabian Kuhn
**Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time**

2009 26th Symp. on Theoretical Aspects of Computer Science (STACS), Freiburg, Germany , pages: 613 - 624

## 2008

*Conference papers*- Fabian Kuhn, Thomas Locher, Stefan Schmid
**Distributed Computation of the Mode**

2008 27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada - Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, Kunal Talwar
**Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings**

2008 27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada - Torsten Muetze, Patrick Stuedi, Fabian Kuhn, Gustavo Alonso
**Understanding Radio Irregularity in Wireless Networks**

2008 5th IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), San Francisco, California, USA

*Journal Papers*- Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
**Ad hoc networks beyond unit disk graphs**

2008*Wirel Netw*, volume: 14, issue: 5, pages: 715 - 729

- Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
**An Algorithmic Approach to Geographic Routing in Ad Hoc and Sensor Networks**

2008*Ieee Acm T Network*, volume: 16, issue: 1, pages: 51 - 62

- Fabian Kuhn, Thomas Locher, Roger Wattenhofer
**Distributed selection: a missing piece of data aggregation**

2008*Commun Acm*, volume: 51, issue: 9, pages: 93 - 99

## 2007

*Conference papers*- Ittai Abraham, Mahesh Balakrishnan, Fabian Kuhn, Dahlia Malkhi, Venugopalan Ramasubramanian, Kunal Talwar
**Reconstructing Approximate Tree Metrics**

2007 26th ACM Symposium on Principles of Distributed Computing (PODC), Portland, Oregon, USA - Fabian Kuhn, Thomas Moscibroda
**Distributed Approximation of Capacitated Dominating Sets**

2007 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego, California, USA - Fabian Kuhn, Thomas Locher, Roger Wattenhofer
**Tight Bounds for Distributed Selection (SPAA Best Paper Award)**

2007 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego, California, USA

*Journal Papers*- Stefan Funke, Alex Kesselman, Fabian Kuhn, Zvi Lotker, Michael Segal
**Improved approximation algorithms for connected sensor cover**

2007*Wirel Netw*, volume: 13, issue: 2, pages: 153 - 164

## 2006

*Conference papers*- Fabian Kuhn, Roger Wattenhofer
**On the Complexity of Distributed Graph Coloring**

2006 25th ACM Symposium on Principles of Distributed Computing (PODC), Denver, Colorado, USA - Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
**Fault-Tolerant Clustering in Ad Hoc and Sensor Networks**

2006 26th International Conference on Distributed Computing Systems (ICDCS), Lisbon, Portugal - Fabian Kuhn, Stefan Schmid, Joest Smit, Roger Wattenhofer
**A Blueprint for Constructing Peer-to-Peer Systems Robust to Dynamic Worst-Case Joins and Leaves**

2006 14th IEEE International Workshop on Quality of Service (IWQoS), Yale University, New Haven, Connectitut, USA - Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
**The Price of Being Near-Sighted**

2006 17th ACM-SIAM Symposium on Discrete Algorithms (SODA) Miami, Florida, USA

*Journal Papers*- Maurice Herlihy, Fabian Kuhn, Srikanta Tirthapura, Roger Wattenhofer
**Dynamic Analysis of the Arrow Distributed Protocol**

2006*Theor Comput Syst*, volume: 39, issue: 6, pages: 875 - 901

- Hagit Attiya, Fabian Kuhn, C. Greg Plaxton, Mirjam Wattenhofer, Roger Wattenhofer
**Efficient adaptive collect using randomization**

2006*Distrib Comput*, volume: 18, issue: 3, pages: 179 - 188

## 2005

*Conference papers*- Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, Roger Wattenhofer
**Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs**

2005 19th International Symposium on Distributed Computing (DISC), Cracow, Poland - Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, Roger Wattenhofer
**Local Approximation Schemes for Ad Hoc and Sensor Networks**

2005 3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, Germany - Fabian Kuhn, Pascal von Rickenbach, Roger Wattenhofer, Emo Welzl, Aaron Zollinger
**Interference in Cellular Networks: The Minimum Membership Set Cover Problem**

2005 11th International Computing and Combinatorics Conference (COCOON), Kunming, Yunnan, China - Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
**On the Locality of Bounded Growth**

2005 24th ACM Symposium on the Principles of Distributed Computing (PODC), Las Vegas, Nevada, USA - Fabian Kuhn, Stefan Schmid, Roger Wattenhofer
**A Self-Repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn**

2005 4th International Workshop on Peer-To-Peer Systems (IPTPS), Cornell University, Ithaca, New York, USA

*Journal Papers*- Fabian Kuhn, Roger Wattenhofer
**Constant-time distributed dominating set approximation**

2005*Distrib Comput*, volume: 17, issue: 4, pages: 303 - 310

## 2004

*Conference papers*- Hagit Attiya, Fabian Kuhn, Mirjam Wattenhofer, Roger Wattenhofer
**Efficient Adaptive Collect using Randomization (DISC Best Student Paper Award)**

2004 18th Annual Conference on Distributed Computing (DISC), Amsterdam, Netherlands - Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
**Unit Disk Graph Approximation**

2004 ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Philadelphia, Pennsylvania, USA - Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
**Initializing Newly Deployed Ad Hoc and Sensor Networks**

2004 10th Annual International Conference on Mobile Computing and Networking (MOBICOM), Philadelphia, Pennsylvania, USA - Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
**Radio Network Clustering from Scratch**

2004 12nd Annual European Symposium on Algorithms (ESA), Bergen, Norway - Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
**What Cannot Be Computed Locally! (PODC Best Student Paper Award)**

2004 23rd ACM Symposium on the Principles of Distributed Computing (PODC), St. John's, Newfoundland, Canada - Fabian Kuhn, Roger Wattenhofer
**Dynamic Analysis of the Arrow Distributed Protocol**

2004 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Barcelona, Spain

## 2003

*Conference papers*- Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
**Ad-Hoc Networks Beyond Unit Disk Graphs**

2003 1st ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), San Diego, California, USA - Fabian Kuhn, Roger Wattenhofer
**Constant-Time Distributed Dominating Set Approximation (PODC Best Student Paper Award)**

2003 22nd ACM Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA - Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Aaron Zollinger
**Geometric Ad-Hoc Routing: Of Theory and Practice**

2003 22nd ACM Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA - Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
**Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing**

2003 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), Annapolis, Maryland, USA

## 2002

*Conference papers*- Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger
**Asymptotically Optimal Geometric Mobile Ad-Hoc Routing**

2002 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), Atlanta, Georgia, USA

## 2001

*Conference papers*- Fabian Kuhn, René Struik
**Random Walks Revisited: Extensions of Pollard’s Rho Algorithm for Computing Multiple Discrete Logarithms**

2001 8th Annual Workshop on Selected Areas in Cryptography (SAC), Toronto, Ontario, Canada

Former Publications