Anders Martinsson
Research Interests
I am a PostDoc in the research group of Prof. Dr. Angelika Steger. My main research interest lies in discrete probability. In particular the probabilistic method, and extending and finding applications of the probabilistic toolbox. Throughout my time so far as a researcher, I have had the pleasure of learning how such tools can be applied to various different areas. During my time as a PhD student at the Department of Mathematical Sciences, Chalmers University of Technology, Gothenburg, my research covered, among other topics, highdimensional percolation, random graphs, stochastic processes, and rigorous investiation of opinion dynamics. Currently, as a PostDoc in the Department of Computer Sciece, ETH Zurich, I am continuing to build upon the same toolbox of ideas, although now, inspired by my research enviroment, with research topics shifted towards computer science, such as graph theory, randomized algorithms, and fundamentals of machine learning.
Publications:
Current preprints:
Accepted publications:
2020:
2019:

The
edgestatistics conjecture for ℓ ≪ k^{6/5}
(joint with F. Mousset, A. Noever, and M. Trujić)
Israel Journal of Mathematics 234 (2), 677690

Optimal strategies for patrolling fences
(joint with B. Haeupler, F. Kuhn, K. Petrova, and P. Pfister)
ICALP: International Colloquium on Automata, Languages and Programming, 2019

Optimal KroneckerSum Approximation of Real Time Recurrent Learning
(joint with F. Benzing, M. Gauy, A. Mujika, and A. Steger)
Proceedings of the 36th International Conference on Machine Learning (ICML), 2019

Most edgeorderings of K_n have maximal altitude
Random Structures & Algorithms 54 (3), 559585

A linear threshold for uniqueness of solutions to random jigsaw puzzles
Combinatorics, Probability and Computing 28 (2), 287302

When does hillclimbing fail on monotone functions: An entropy compression argument
(joint with J. Lengler, and A. Steger)
2019 Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics
2018:
2016:
2015:
2014:
2013:
Theses:

Topics in discrete random structures
PhD Thesis, 2017, Chalmers University of Technology, Gothenburg, Sweden, under supervision of P. Hegarty

Accessibility percolation and firstpassage percolation
on the hypercube
Licenciate thesis, 2015, Chalmers University of Technology, Gothenburg, Sweden,under supervision of P. Hegarty

Spectral and probabilistic methods in
planted random graph models
Master's thesis, 2012, Chalmers University of Technology, Gothenburg, Sweden, under supervision of C. Bhattacharyya, and D. Dubhashi