• EN
Background image HPI with color gradient

Anton Krohmer

Dr. Anton Krohmer

This is an archived page of a former group member.
Anton Krohmer is now a Senior Software Engineer at Google in Munich.

Publications

2020

  •  

    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonHyperbolic Embeddings for Near-Optimal Greedy RoutingJournal of Experimental Algorithmics (JEA) 2020: 1–18

    [ ][ ][ URL ][ DOI ][ Download ]

2018

  •  

    Bläsius, Thomas; Friedrich, Tobias; Krohmer, AntonCliques in Hyperbolic Random GraphsAlgorithmica 2018: 2324–2344

    [ ][ ][ DOI ][ Download ]

  •  

    Bringmann, Karl; Friedrich, Tobias; Krohmer, AntonDe-anonymization of Heterogeneous Random Graphs in Quasilinear TimeAlgorithmica 2018: 3397–3427

    [ ][ ][ DOI ][ Download ]

  •  

    Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, SörenEfficient Embedding of Scale-Free Graphs in the Hyperbolic PlaneIEEE/ACM Transactions on Networking 2018: 920–933

    [ ][ ][ URL ][ DOI ][ Download ]

  •  

    Friedrich, Tobias; Krohmer, AntonOn the diameter of hyperbolic random graphsSIAM Journal on Discrete Mathematics 2018: 1314–1334

    [ ][ ][ URL ][ DOI ][ Download ]

  •  

    Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonUnbounded Discrepancy of Deterministic Random Walks on GridsSIAM Journal on Discrete Mathematics 2018: 2441–2452

    [ ][ ][ URL ][ DOI ][ Download ]

  •  

    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonHyperbolic Embeddings for Near-Optimal Greedy RoutingAlgorithm Engineering and Experiments (ALENEX) 2018: 199–208

    [ ][ ][ URL ][ DOI ][ Download ]

  •  

    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton; Striebel, JonathanTowards a Systematic Evaluation of Generative Network ModelsWorkshop on Algorithms and Models for the Web Graph (WAW) 2018: 99–114

    [ ][ ][ URL ][ DOI ][ Download ]

2017

  •  

    Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sutton, Andrew M.Phase Transitions for Scale-Free SAT FormulasConference on Artificial Intelligence (AAAI) 2017: 3893–3899

    [ ][ ][ URL ][ Download ]

  •  

    Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sauerwald, Thomas; Sutton, Andrew M.Bounds on the Satisfiability Threshold for Power Law Distributed Random SATEuropean Symposium on Algorithms (ESA) 2017: 37:1–37:15

    [ ][ ][ URL ][ DOI ][ Download ]

2016

  •  

    Bläsius, Thomas; Friedrich, Tobias; Krohmer, AntonHyperbolic Random Graphs: Separators and TreewidthEuropean Symposium on Algorithms (ESA) 2016: 15:1–15:16

    [ ][ ][ DOI ][ Download ]

  •  

    Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, SörenEfficient Embedding of Scale-Free Graphs in the Hyperbolic PlaneEuropean Symposium on Algorithms (ESA) 2016: 16:1–16:18

    EATCS Best Paper Award

    [ ][ ][ URL ][ DOI ][ Download ]

2015

  •  

    Friedrich, Tobias; Krohmer, AntonParameterized clique on inhomogeneous random graphsDiscrete Applied Mathematics 2015: 130–138

    [ ][ ][ DOI ][ Download ]

  •  

    Friedrich, Tobias; Krohmer, AntonOn the Diameter of Hyperbolic Random GraphsInternational Colloquium on Automata, Languages and Programming (ICALP) 2015: 614–625

    [ ][ ][ DOI ][ Download ]

  •  

    Friedrich, Tobias; Krohmer, AntonCliques in Hyperbolic Random GraphsInternational Conference on Computer Communications (INFOCOM) 2015: 1544–1552

    [ ][ ][ DOI ][ Download ]

  •  

    Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonUnbounded Discrepancy of Deterministic Random Walks on GridsInternational Symposium on Algorithms and Computation (ISAAC) 2015: 212–222

    [ ][ ][ DOI ][ Download ]

2014

  •  

    Bringmann, Karl; Friedrich, Tobias; Krohmer, AntonDe-anonymization of Heterogeneous Random Graphs in Quasilinear TimeEuropean Symposium on Algorithms (ESA) 2014: 197–208

    [ ][ ][ DOI ][ Download ]

2012

  •  

    Alcaraz, Nicolas; Friedrich, Tobias; Kötzing, Timo; Krohmer, Anton; Müller, Joachim; Pauling, Josch; Baumbach, JanEfficient Key Pathway Mining: Combining Networks and OMICS DataIntegrative Biology 2012: 756–764

    [ ][ ][ DOI ][ Download ]

  •  

    Baumbach, Jan; Friedrich, Tobias; Kötzing, Timo; Krohmer, Anton; Müller, Joachim; Pauling, JoschEfficient Algorithms for Extracting Biological Key Pathways with Global ConstraintsGenetic and Evolutionary Computation Conference (GECCO) 2012: 169–176

    [ ][ ][ URL ][ DOI ][ Download ]

  •  

    Friedrich, Tobias; Krohmer, AntonParameterized Clique on Scale-Free NetworksInternational Symposium on Algorithms and Computation (ISAAC) 2012: 659–668

    [ ][ ][ DOI ][ Download ]

2010

  •  

    Backes, Michael; Ciobotaru, Oana; Krohmer, AntonRatFish: A File Sharing Protocol Provably Secure against Rational UsersEuropean Symposium on Research in Computer Security (ESORICS) 2010: 607–625

    [ ][ ][ DOI ][ Download ]

Other Works

  • Finding Cliques in Scale-Free Networks. [pdf]
    Master Thesis, 2012.
  • Rational File Sharing. [pdf]
    Bachelor Thesis, 2009.

Nice Riddles

Here's a collection of my favorite riddles.

Battling Coins

You and your friend are playing the following game on a rectangular table. Each of you has an unlimited supply of equally-sized coins. Whenever it's a player's turn, the player has to put down a coin on an unoccupied space on the table. In particular, the coin cannot overlap with previously placed coins.

The first player who cannot put down a coin loses.

Do you want to go first or second in this game? What is a winning strategy?

Squaring Squares

Assume you are given four points in the plane that form a square with side length 1. You are allowed to modify the position of the points as follows: You can mirror a point at another one of the four points.

Is it possible to create a square with side length 2 using only these operations?

Robot Meeting

Two robots land safely with their parachutes on the integer line. They leave their parachute at the landing position and then proceed to execute their coded programs. They both contain exactly the same program. Your task is to write this program in such a way that they will eventually meet. You have access to the following operations:

  • Move left
  • Move right
  • GOTO x (where x is a line number in your code)
  • If there is a parachute at your position, skip the next line of code

Your program should not be longer than 10 lines.

Spiders, Spiders Everywhere!

This riddle is a little different, and it is hard to get all constraints straight, but let's try:

You inherited a room in which you intend to sleep. Unfortunately, the room is haunted, and spiders can spawn on the walls and on the ceiling. A spider can crawl essentially everywhere, and it can also let itself drop from wherever it is hanging right now.

Your task is to place your bed inside the room such that you can sleep without being pestered by spiders. To this end, you can build immovable structures (in particular, you cannot build a house inside your room since you cannot enter the room without a door); and you can use water.

Spiders hate water. While you can step over it (if it is narrow enough), they cannot cross water. However, you cannot just "place water" in your room; the laws of gravity still apply. To this end, if you want to place water somewhere, you will have to build a structure such that it contains the water. The structures are of non-negligible thickness, i.e., you cannot contain water within walls of "thickness almost 0." If in doubt, there is always a spider small enough that can land on the wall.

For instance, it is possible to build a small moat around your bed. Then, spiders cannot enter your bed via the floor. They still can, however, enter your bed by crawling on the ceiling and then dropping in your mouth while you sleep.

How can you prevent spiders from reaching your bed?