Uni-Logo
Algorithms and Complexity
 


Prof. Dr. Fabian Kuhn



Publications:

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

    2020


    Conference papers

    2019


    Conference papers
    • Abdolhamid Ghodselahi, Fabian Kuhn, Volker Turau
      Competitive Concurrent Distributed Scheduling
      2019 30th Int. Symp. on Algorithms and Computation (ISAAC)
    • Mohsen Ghaffari, Fabian Kuhn, Jara Uitto
      Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds
      2019 60th IEEE Symp. on Foundations of Computer Science (FOCS)
    • Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, Rotem Oshman
      Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles
      2019 33rd International Symposium on Distributed Computing (DISC)
    • Janosch Deurer, Fabian Kuhn, Yannic Maus
      Deterministic Distributed Dominating Set Approximation in the CONGEST Model
      2019 38th ACM Symp. on Principles of Distributed Computing (PODC)
    • Philipp Bamberger, Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Jara Uitto
      On the Complexity of Distributed Splitting Problems
      2019 38th ACM Symp. on Principles of Distributed Computing (PODC)
    • Mohsen Ghaffari, Fabian Kuhn
      On the Use of Randomness in Local Distributed Graph Algorithms
      2019 38th ACM Symp. on Principles of Distributed Computing (PODC)
    • Bernhard Haeupler, Fabian Kuhn, Anders Martinsson, Kalina Petrova, Pascal Pfister
      Optimal Strategies for Patrolling Fences
      2019 46th Int. Coll. on Automata, Languages, and Programming (ICALP)
    • Mohamad Ahmadi, Fabian Kuhn, Shay Kutten, Anisur Rahaman Molla, Gopal Pandurangan
      The Communication Cost of Information Spreading in Dynamic Networks
      2019 39th IEEE Int. Conf. on Distributed Computing Systems (ICDCS), Dallas, USA
    • John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian Kuhn, Jason Li, Christian Scheideler
      Distributed Computation in Node-Capacitated Networks
      2019 31st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA)
    • Philipp Bamberger, Fabian Kuhn, Yannic Maus
      Local Distributed Algorithms in Highly Dynamic Networks
      2019 33rd IEEE Int. Parallel and Distributed Processing Symposium (IPDPS)
    Journal Papers
    • Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, Calvin Newport
      Contention Resolution on a Fading Channel
      2019 Distrib Comput, volume: 32, issue: 6, pages: 517 - 533
    • Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, Anisur Rahaman Molla
      The Cost of Global Broadcast in Dynamic Radio Networks
      2019 Theor Comput Sci

    2018


    Conference papers
    • Mohsen Ghaffari, Fabian Kuhn
      Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
      2018 32nd International Symposium on Distributed Computing (DISC)
    • Mohamad Ahmadi, Fabian Kuhn, Rotem Oshman
      Distributed Approximate Maximum Matching in the CONGEST Model
      2018 32th Int. Symp. on Distributed Computing (DISC), New Orleans, USA
    • Mohsen Ghaffari, Fabian Kuhn
      Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping
      2018 32nd International Symposium on Distributed Computing (DISC)
    • Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler, Thim Strothmann
      Forming Tile Shapes with Simple Robots
      2018 24th International Conference on DNA Computing and Molecular Programming (DNA 24) Springer
    • Mohsen Ghaffari, David G. Harris, Fabian Kuhn
      On Derandomizing Local Distributed Algorithms
      2018 59th IEEE Symposium on Foundations of Computer Science (FOCS)
    • Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler
      Shape Recognition by a Finite Automaton Robot
      2018 43rd Symposium on Mathematical Foundations of Computer Science (MFCS)
    • Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Juho Hirvonen
      Improved Distributed Delta-Coloring
      2018 ACM Symposium on Principles of Distributed Computing (PODC)
    • Orr Fischer, Tzlil Gonen, Fabian Kuhn, Rotem Oshman
      Possibilities and Impossibilities for Distributed Subgraph Detection
      2018 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA)
    • Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Jara Uitto
      Deterministic Distributed Edge-Coloring with Fewer Colors
      2018 50th ACM Symposium on Theory of Computing (STOC)
    • Fabian Kuhn, Yannic Maus, Simon Weidner
      Deterministic Distributed Ruling Sets of Line Graphs
      2018 Int. Coll. on Structural Information and Communication Complexity (SIROCCO)
    • Paweł Gawrychowski, Fabian Kuhn, Jakub Łopuszański, Konstantinos Panagiotou, Pascal Su
      Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees
      2018 29th ACM-SIAM Symposium on Discrete Algorithms (SODA)

    2017


    Conference papers
    • Fabian Kuhn, Philipp Schneider
      Broadcasting in an Unreliable SINR Model
      2017 21st Conference on Principles of Distributed Systems (OPODIS) , pages: 3:1 - 3:21
    • Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, Jara Uitto
      Improved Distributed Degree Splitting and Edge Coloring
      2017 International Symposium on DIStributed Computing (DISC)
    • Magnús M. Halldórsson, Fabian Kuhn, Nancy Lynch, Calvin Newport
      An Efficient Communication Abstraction for Dense Wireless Networks
      2017 31st Symposium on Distributed Computing (DISC) , pages: 25:1 - 25:16
    • Abdolhamid Ghodselahi, Fabian Kuhn
      Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks
      2017 31st Symposium on Distributed Computing (DISC)
    • Manuela Fischer, Mohsen Ghaffari, Fabian Kuhn
      Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
      2017 58th IEEE Symposium on Foundations of Computer Science (FOCS) , pages: 180 - 191
    • Seth Gilbert, Fabian Kuhn, Chaodong Zheng
      Communication Primitives in Cognitive Radio Networks
      2017 36th ACM Symposium on Principles of Distributed Computing (PODC) , pages: 23 - 32
    • Mohsen Ghaffari, Fabian Kuhn, Hsin-Hao Su
      Distributed MST and Routing in Almost Mixing Time
      2017 36th ACM Symposium on Principles of Distributed Computing (PODC) , pages: 131 - 140
    • Mohsen Ghaffari, Fabian Kuhn, Yannic Maus
      On the Complexity of Local Distributed Graph Problems
      2017 ACM Symposium on Theory of Computing (STOC)
    Journal Papers
    • Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn
      Tight Bounds on Vertex Connectivity Under Sampling
      2017 Acm T Algorithms, volume: 13, issue: 2, pages: 19:1 - 19:26

    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
    • Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, Calvin Newport
      Contention Resolution on a Fading Channel
      2016 2016 ACM Symposium on Principles of Distributed Computing (PODC)
    • 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
    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

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