Rajko Nenadov

I am a Lecturer in the School of Computer Science at the University of Auckland, New Zealand.

I obtained PhD from ETH Zurich in 2016, under the supervision of Angelika Steger. I spent two years as a postdoc at the School of Mathematical Sciences at Monash University (Melbourne, Australia) hosted by Jane Gao and Nick Wormald, and another year and half back at ETH, where I was hosted by Benny Sudakov. The following four years I was a software engineer at Google Zurich, working mostly on Search Ranking algorithms. As of July 2023, I'm back in academia!

My principal research interests are in discrete mathematics and theoretical computer science, particularly algorithmic and combinatorial properties of random and pseudorandom discrete structures, applications of (pseudo)randomness in theoretical computer science, probabilistic methods in combinatorics, extremal graph theory, Ramsey theory, and combinatorial games.

Upcoming talks

19 March 2024: Research seminar in Discrete Mathematics, BIMSA (online)
2 April 2024: ETH Mittagsseminar
22 July 2024: Novi Sad Workshop on Foundations of Computer Science

Publications

M. Christoph, R. Nenadov, K. Petrova, The Hamilton space of pseudorandom graphs [arXiv]
Submitted, 2024.
R. Montgomery, R. Nenadov, T Szabó, Global rigidity of random graphs in R [arXiv]
Submitted, 2024.
N. Alon, N. Dodson, C. Jackson, R. McCarty, R. Nenadov, and L. Southern, Universality for graphs with bounded density [arXiv]
Submitted, 2024.
N. Draganić and R. Nenadov, Edge-disjoint paths in expanders: online with removals [arXiv]
Proc. of the ACM-SIAM SODA 2024, 4554-4563
R. Nenadov, Probabilistic hypergraph containers [journal, arXiv]
Israel Journal of Mathematics, to appear.
K. D. Barbosa, D. Mašulović, and R. Nenadov
A short note on the characterization of countable chains with finite big Ramsey spectra [arXiv, journal]
Order, to appear.
D. Conlon, R. Nenadov, and M. Trujić, On the size-Ramsey number of grids [arXiv, journal]
Combinatorics, Probability and Computing, 32(6), 874-880, 2023.
R. Nenadov, Routing permutations on spectral expanders via matchings [arXiv, journal]
Combinatorica, 43:737-742, 2023.
R. Nenadov, Probabilistic intuition holds for a class of small subgraph games [arXiv, journal]
Proceedings of the American Mathematical Society, 151:1495-1501, 2023.
R. Nenadov, A new proof of the KŁR conjecture [arXiv, journal]
Advances in Mathematics, 406:108518, 2022.
Companion note: Small subsets without k-term arithmetic progressions [arXiv]
D. Conlon, R. Nenadov, and M. Trujić, The size-Ramsey number of cubic graphs [arXiv, journal]
Bulletin of the London Mathematical Society, 54(6):2135-2150, 2022.
N. Draganić, M. Krivelevich, and R. Nenadov
Rolling backwards can move you forward: on embedding problems in sparse expanders [arXiv, journal]
Transactions of the American Mathematical Society, 375:5195-5216, 2022.
Proc. of the ACM-SIAM SODA 2021, 123–134.
A. Liebenau and R. Nenadov, The threshold bias of the clique-factor game [arXiv, journal]
Journal of Combinatorial Theory, Series B, 152:221;247, 2022.
N. Draganić, M. Krivelevich, and R. Nenadov, The size-Ramsey number of short subdivisions [arXiv, journal]
Random Structures & Algorithms, 59(1):68-78, 2021.
M. Krivelevich and R. Nenadov, Complete minors in graphs without sparse cuts [arXiv, journal]
International Mathematics Research Notices (IMRN), 2021(12): 8996–9015, 2021.
R. Nenadov and M. Trujić, Sprinkling a few random edges doubles the power [arXiv, journal]
SIAM Journal on Discrete Mathematics, 35(2):988–1004, 2021.
R. Nenadov, A. Steger, and P. Su, An O(N) time algorithm for finding Hamilton cycles with high probability [arxiv, proc]
12th Innovations in Theoretical Computer Science Conference ITCS 2021, vol 185, 60:1-60:17, 2021.
R. Nenadov, B. Sudakov, and A. Z. Wagner, Completion and deficiency problems [arXiv, journal]
Journal of Combinatorial Theory, Series B, 145:214–240, 2020.
R. Nenadov, B. Sudakov, and M. Tyomkyn, Proof of the Brown–Erdős–Sós conjecture in groups [arXiv, journal]
Mathematical Proceedings of the Cambridge Philosophical Society, 169(2):323–333, 2020.
R. Nenadov, M. Sawhney, B. Sudakov, and A. Z. Wagner, Bounded degree spanners of the hypercube [arXiv, journal]
The Electronic Journal of Combinatorics, 27(3), 2020.
F. Mousset, R. Nenadov, and W. Samotij, Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties [arXiv, journal]
Combinatorics, Probability and Computing, 29(6):943–955, 2020.
R. Nenadov and Y. Pehova, On a Ramsey–Turán variant of the Hajnal–Szemerédi theorem [arXiv, journal]
SIAM Journal on Discrete Mathematics, 34(2):1001–1010, 2020.
R. Nenadov and N. Škorić, On Komlós’ tiling theorem in random graphs [arXiv, journal]
Combinatorics, Probability and Computing, 29(1):113–127, 2020.
R. Nenadov, Triangle-factors in pseudorandom graphs [arXiv, journal]
Bulletin of the London Mathematical Society, 51(3):421–430, 2019.
R. Nenadov, A. Steger, and M. Trujić, Resilience of perfect matchings and hamiltonicity in random graph processes [arXiv, journal]
Random Structures & Algorithms, 54(4):797–819, 2019.
N. Alon and R. Nenadov, Optimal induced universal graphs for bounded-degree graphs [arXiv, journal]
Mathematical Proceedings of the Cambridge Philosophical Society, 166(1):61–74, 2019.
Proc. of the ACM-SIAM SODA 2017, 1149–1157.
R. Nenadov and N. Škorić, Powers of hamilton cycles in random graphs and tight hamilton cycles in random hypergraphs [arXiv, journal]
Random Structures & Algorithms, 54(1):187–208, 2018.
A. Ferber and R. Nenadov, Spanning universality in random graphs [arXiv, journal]
Random Structures & Algorithms, 53(4):604–637, 2018.
D. Korándi, F. Mousset, R. Nenadov, N. Škorić, and B. Sudakov, Monochromatic cycle covers in random graphs [arXiv, journal]
Random Structures & Algorithms, 53(4):667–691, 2018.
R. Nenadov, Star-factors in graphs with large minimum degree [arXiv, journal]
Journal of Combinatorial Theory, Series B, 133:78–87, 2018.
L. Gugelmann, R. Nenadov, Y. Person, N. Škorić, A. Steger, and H. Thomas
Symmetric and asymmetric Ramsey properties in random hypergraphs [arXiv, journal]
Forum of Mathematics, Sigma, 5:e28, 2017.
A. Ferber, R. Nenadov, A. Noever, U. Peter, and N. Škorić, Robust hamiltonicity of random directed graphs [arXiv, journal]
Journal of Combinatorial Theory, Series B, 126:1–23, 2017.
Proc. of the ACM-SIAM SODA 2015, 1752–1758.
R. Nenadov, P. Pfister, and A. Steger, Unique reconstruction threshold for random jigsaw puzzles [arXiv, journal]
Chicago Journal of Theoretical Computer Science, 2017:2, June 2017.
D. Conlon, A. Ferber, R. Nenadov, and N. Škorić, Almost-spanning universality in random graphs [arXiv, journal]
Random Structures & Algorithms, 50(3):380–393, 2017.
R. Nenadov, Y. Person, N. Škorić, and A. Steger
An algorithmic framework for obtaining lower bounds for random Ramsey problems [arXiv, journal]
Journal of Combinatorial Theory, Series B, 124:1–38, 2017.
Proc. of the ACM-SIAM SODA 2015, 1743–1751.
R. Nenadov, A. Steger, and M. Stojaković, On the threshold for the Maker-Breaker H-game [arXiv, journal]
Random Structures & Algorithms, 49(3):558–578, 2016.
A. Ferber, R. Nenadov, and U. Peter, Universality of random graphs and rainbow embedding [arXiv, journal]
Random Structures & Algorithms, 48(3):546–564, 2016.
R. Nenadov and A. Steger, A short proof of the random Ramsey theorem [pdf, journal]
Combinatorics, Probability and Computing, 25(01):130–144, 2016.
F. Mousset, R. Nenadov, and A. Steger, On the number of graphs without large cliques [arXiv, journal]
SIAM Journal on Discrete Mathematics, 28(4):1980–1986, 2014.
D. Mašulović, R. Nenadov, and N. Škorić, On finite reflexive homomorphism-homogeneous binary relational systems [arXiv, journal]
Discrete Mathematics, 311:2543–2555, 2011.