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, high-dimensional percolation, random graphs, stochastic processes, and rigorous investigation of opinion dynamics. Currently, as a PostDoc in the Department of Computer Science, ETH Zurich, I am continuing to build upon the same toolbox of ideas, although now, inspired by my research environment, with research topics shifted towards computer science, such as graph theory, randomized algorithms, and fundamentals of machine learning.

Publications:

Current preprints:

• Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs
  (Joint with R. Steiner)
• Cycle lengths modulo k in expanders
  (Joint with R. Steiner)
• Optimal schemes for combinatorial query problems with integer feedback
• Hat guessing numbers of strongly degenerate graphs
  (joint with C. Knierim and R. Steiner)
• Reconstructibility of the Kr-count from n-1 cards
  (joint with C. Knierim)
• A simplified proof of the Johansson-Molloy Theorem using the Rosenfeld counting method
• Mastermind with a linear number of queries
  (joint with P. Su)
• The chromatic number of dense random block graphs
  (joint with K. Panagiotou, P. Su, M. Trujić)
• Why honesty of effort may not be rewarded in tournaments
  (joint with P. Hegarty, and E. Wedin)
• Accessibility percolation and first-passage percolation on the unoriented binary hypercube
  

Accepted publications:

2022:

• Solving Static Permutation Mastermind using O(n log n) Queries
  (joint with M. Larcher and A. Steger)
  Electronic Journal of Combinatorics 29, no. 1

2021:

• Note on Long Paths in Eulerian Digraphs
  (joint with C. Knierim and M. Larcher)
  Electronic Journal of Combinatorics 28, no. 2, Paper no. 2.37
• Arithmetic Progressions in Sumsets of Sparse Sets
  (joint with N. Alon, R. Alweiss, Y. Liu, and S. Narayanan)
  Integers 21A, Ron Graham Memorial Volume, Paper no. A3
• Long cycles, heavy cycles and cycle decompositions in digraphs
  (joint with C. Knierim, M. Larcher, and A. Noever)
  Journal of Combinatorial Theory, Series B 148, 125-148

2020:

• An Optimal Decentralized (Delta+1)-Coloring Algorithm
  (joint with D. Bertschinger, J. Lengler, R. Meier, A. Steger, M. Trujić, E. Welzl)
  28th Annual European Symposium on Algorithms, Art. No. 17
• Navigating an Infinite Space with Unreliable Movements
  (joint with J. Uitto)
  Symposium on Discrete Algorithms 20, 1170-1179

2019:

• The edge-statistics conjecture for ℓ ≪ k^6/5
  (joint with F. Mousset, A. Noever, and M. Trujić)
  Israel Journal of Mathematics 234 (2), 677-690
• 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 Kronecker-Sum 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 edge-orderings of K_n have maximal altitude
  Random Structures & Algorithms 54 (3), 559-585
• A linear threshold for uniqueness of solutions to random jigsaw puzzles
  Combinatorics, Probability and Computing 28 (2), 287-302
• 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:

• Segregating Markov chains
  (joint with T. Hirscher)
  Journal of Theoretical Probability 31 (3), 1512-1538
• Even flying cops should think ahead
  (joint with F. Meier, P. Schnider, and A. Steger)
  International Symposium on Combinatorial Optimization, 326-337
• First-passage percolation on Cartesian power graphs
  The Annals of Probability 46 (2), 1004-1041

2016:

• The Hegselmann–Krause dynamics on the circle converge
  (joint with P. Hegarty, and E. Wedin)
  Journal of Difference Equations and Applications 22(11), 2016, 1720–1731
• Unoriented first-passage percolation on the n-cube
  Annals of Applied Probability 26(5), 2016, 2597–2625
• An improved energy argument for the Hegselmann–Krause model
  Journal of Difference Equations and Applications 22(4), 2016, 513–518.
• When can multi-agent rendezvous be executed in time linear in the diameter of a plane configuration?
  (joint with P. Hegarty, and D. Zhelezov)
  ICDCN '16 Proceedings of the 17th International Conference on Distributed Computing and Networking

2015:

• Permutations destroying arithmetic progressions in finite cyclic groups
  (joint with P. Hegarty)
  The Electronic Journal of Combinatorics 22(4), 2015, Paper #P4.39

2014:

• On the existence of accessible paths in various models of fitness landscapes
  (joint with with P. Hegarty)
  Annals of Applied Probability 24(4), 2014, 1375–1395

2013:

• The Lovasz ϑ function, SVMs and finding large dense subgraphs
  (joint with V. Jethava, C. Bhattacharyya, and D. Dubhashi)
  Journal of Machine Learning Research 14 (2013), 3495-3526.

Theses:

• Topics in discrete random structures
  PhD Thesis, 2017, Chalmers University of Technology, Gothenburg, Sweden, under supervision of P. Hegarty
• Accessibility percolation and first-passage 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