42 citations · 132 across the 20 of their papers we have counts for
4 papers · 1 filter
When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument
Johannes Lengler, Anders Martinsson, Angelika Steger
Hillclimbing is an essential part of any optimization algorithm. An important benchmark for hillclimbing algorithms on pseudo-Boolean functions are (s…
Connectivity Thresholds for Bounded Size Rules
Hafsteinn Einarsson, Johannes Lengler, Konstantinos Panagiotou +2
In an Achlioptas process, starting with a graph that has n vertices and no edge, in each round edges are drawn uniformly at random, and using some rule exactly one of th…
Bootstrap percolation with inhibition
Hafsteinn Einarsson, Johannes Lengler, Konstantinos Panagiotou +2
Bootstrap percolation is a prominent framework for studying the spreading of activity on a graph. We begin with an initial set of active vertices. The process then proceeds in roun…
Extremal Subgraphs of Random Graphs: an Extended Version
Graham Brightwell, Konstantinos Panagiotou, Angelika Steger
We prove that there is a constant , such that whenever , with probability tending to 1 when goes to infinity, every maximum triangle-free subgraph of the ra…