4 citations · 10 across the 6 of their papers we have counts for
6 papers
Learning Randomized Algorithms with Transformers
Johannes von Oswald, Seijin Kobayashi, Yassir Akram +1
Randomization is a powerful tool that endows algorithms with remarkable properties. For instance, randomized algorithms excel in adversarial settings, often surpassing the worst-ca…
Random initialisations performing above chance and how to find them
Frederik Benzing, Simon Schug, Robert Meier +5
Neural networks trained with stochastic gradient descent (SGD) starting from different random initialisations typically find functionally very similar solutions, raising the questi…
Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model
Dan Hefetz, Fabian Kuhn, Yannic Maus +1
We show an lower bound on the runtime of any deterministic distributed -graph coloring algorithm in a weak vari…
An algorithmic framework for obtaining lower bounds for random Ramsey problems
Rajko Nenadov, Yury Person, Nemanja Škorić +1
In this paper we introduce a general framework for proving lower bounds for various Ramsey type problems within random settings. The main idea is to view the problem from an algori…
The game chromatic number of dense random graphs
Ralph Keusch, Angelika Steger
Suppose that two players take turns coloring the vertices of a given graph G with k colors. In each move the current player colors a vertex such that neighboring vertices get diffe…
Random directed graphs are robustly Hamiltonian
Dan Hefetz, Angelika Steger, Benny Sudakov
A classical theorem of Ghouila-Houri from 1960 asserts that every directed graph on vertices with minimum out-degree and in-degree at least contains a directed Hamilton c…