Uni-Logo
Algorithms and Complexity
 

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
    • 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
    • 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

    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

    2011


    Conference papersJournal 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, Nancy Lynch, Calvin Newport
      The Abstract MAC Layer
      2011 Distrib Comput (Distributed Computing), volume: 24, issue: 3-4, pages: 187 - 206

    2010


    Conference papersJournal Papers

    2009


    Conference papers

    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 papersJournal 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

    2002


    Conference papers

    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