Abbas Mehrabian’s publications

These are my scientific publications; for journalistic ones, check my MuckRack profile, and for descriptions of my research projects, see my research page.

Conferences and Workshops

2024: Mehrabian, Anand, Kim, Sonnerat, Balog, Comanici, Berariu, Lee, Ruoss, Bulanova, Toyama, Blackwell, Paredes, Veličković, Orseau, Lee, Naredla, Precup, Wagner, Finding increasingly large extremal graphs with AlphaZero and tabu search, IJCAI'24 and MATH-AI Workshop at NeurIPS'23
2021: Esfandiari, Karbasi, Mehrabian, Mirrokni, Regret bounds for batched bandits, AAAI'21
2020: Durand, Kveton, Mehrabian, Vaswani, Old dog learns new tricks: randomized UCB for bandit problems, AISTATS'20; Boursier, Kaufmann, Mehrabian, Perchet, A practical algorithm for multiplayer bandits when arm means vary among players, AISTATS'20
2018: Ashtiani, Ben-David, Harvey, Liaw, Mehrabian, Plan, Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes, winner of a best-paper award at NeurIPS'18 (full version in JACM); Ashtiani, Ben-David, Mehrabian, Sample-efficient learning of mixtures, AAAI'18, corrected version on arXiv
2017: Angel, Mehrabian, Peres, String of diamonds is tight for rumor spreading, RANDOM'17 (full version in CPC); Harvey, Liaw, Mehrabian, Nearly-tight VC-dimension bounds for piecewise linear neural networks, COLT'17, (full version in JMLR); Berenbrink, Kling, Liaw, Mehrabian, Tight load balancing via randomized local search, IPDPS'17
2015: Janssen and Mehrabian, Rumours spread slowly in a small world spatial network, WAW'15 (journal version in SiDMa); Acan, Collevecchio, Mehrabian, Wormald, On the push&pull protocol for rumour spreading, PODC'15 (full version in SiDMa)
2014: Mehrabian and Pourmiri, Randomized rumor spreading on poorly connected small-world networks, DISC'14 (full version in RSA); Mehrabian and Wormald, It’s a small world for random surfers, RANDOM'14 (full version in Algorithmica)
2012: Alamdari and Mehrabian, On a DAG partitioning problem, WAW'12
2011: Mehrabian, A randomly embedded random graphs is not a spanner, CCCG'11 (full version in DCG); Ehsani, Fazli, Mehrabian, Sadeghian, Safari, Saghafian, Shokatfadaee, On a bounded budget network creation game, SPAA'11 (full version in ACM TAlg)

Journals

2021: Lugosi and Mehrabian, Multiplayer bandits without observing collision information, Mathematics of Operations Research
2020: Ashtiani, Ben-David, Harvey, Liaw, Mehrabian, Plan, Near-optimal sample complexity bounds for robust learning of Gaussian mixtures via compression schemes, Journal of the ACM; Devroye, Mehrabian, Reddad, The minimax learning rate of normal and Ising undirected graphical models, Electronic Journal of Statistics
2019: Bartlett, Harvey, Liaw, Mehrabian, Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks, Journal of Machine Learning Research; Angel, Mehrabian, Peres, String of diamonds is tight for rumour spreading, Combinatorics, Probability and Computing; Devroye, Dujmovic, Frieze, Mehrabian, Morin, Reed, Notes on Growing a Tree in a Graph, Random Structures and Algorithms
2017: Janssen and Mehrabian, Rumours spread slowly in a small world spatial network, SIAM Journal on Discrete Mathematics; Liaw, Mehrabian, Plan, Vershynin, A simple tool for bounding the deviation of random matrices on geometric sets, GAFA Seminar Notices; Acan, Collevecchio, Mehrabian, Wormald, On the push&pull protocol for rumour spreading, SIAM Journal on Discrete Mathematics; Mehrabian, Justifying the small-world phenomenon via random recursive trees, Random Structures and Algorithms
2016: Collevecchio, AM, and Nick Wormald, Longest paths in random Apollonian networks and largest $r$-ary subtrees of random $d$-ary recursive trees, Journal of Applied Probability
2015: Mehrabian and Pourmiri, Randomized rumor spreading on poorly connected small-world networks, Random Structures and Algorithms; Mehrabian and Wormald, It’s a small world for random surfers, Algorithmica; Ehsani, Fazli, Mehrabian, Sadeghian, Safari, Saghafian, Shokatfadaee, A bounded budget network creation game, ACM Transactions on Algorithms; Alon and Mehrabian, Chasing a fast robber on planar graphs and random graphs, Journal of Graph Theory (a minor correction); Mehrabian, The fast robber on interval and chordal graphs, Discrete and Applied Mathematics; Akbari, Daemi, Hatami, Javanmard, Mehrabian, Nowhere-zero unoriented flows in Hamiltonian graphs, Ars Combinatoria
2014: Ebrahimzadeh, Farczadi, Gao, Mehrabian, Sato, Wormald, Zung, On longest paths and diameter in random Apollonian networks, Random Structures and Algorithms
2013: Mehrabian, Mitsche, Pralat, On the maximum density of graphs with unique-path labelings, SIAM Journal on Discrete Mathematics; Mehrabian and Wormald, On the stretch factor of randomly embedded random graphs, Discrete and Computational Geometry
2012: Mehrabian, Cops and robber game with a fast robber on expander graphs and random graphs, Annals of Combinatorics; Mehrabian, On the density of nearly regular graphs with a good edge-labeling, SIAM Journal on Discrete Mathematics; Mehrabian, Lower bounds for the cop number when the robber is fast, Combinatorics, Probability and Computing
2011
2011: Alon and Mehrabian, On a generalization of Meyniel’s conjecture on the cops and robbers game, Electronic Journal of Combinatorics; Mehrabian, The capture time of grids, Discrete Mathematics
2010: Akbari, Daemi, Hatami, Javanmard, Mehrabian, Zero-sum flows in regular graphs, Graphs and Combinatorics

Theses

2015: Diameter and Rumour Spreading in Real-World Network Models, PhD thesis at University of Waterloo
2011: Cops and Robber Game with a Fast Robber, Master’s thesis at University of Waterloo
2009

Expository Articles

2025: AlphaEvolve: A coding agent for scientific and algorithmic discovery, with Alexander Novikov, Ngân Vũ, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, Matej Balog, white paper
2018: The total variation distance between high-dimensional Gaussians with the same mean, with Luc Devroye and Tommy Reddad, unpublished research note; Learning mixtures of high-dimensional Gaussians, with Hassan Ashtiani, Canadian Mathematical Society Research Notes, June 2018, pages 16 and 17; Some techniques in density estimation, with Hassan Ashtiani, unpublished tutorial

Notes in Persian

2016: Book review: Understanding Machine Learning: From Theory to Algorithms; Unpublished tutorial: An introduction to asymptotic calculations; Book review: Foundations of Data Science; Expository article: The weather forecast problem and a fruitful algorithmic idea (based on these notes on the multiplicative weight update method)
2015: Expository article: Four examples of applying linear algebra in other areas (based on this beautiful book by Jiri Matousek); SODA 2015 conference report; Survey article: Models for rumour spreading in social networks
2014: expository article: Grover’s search algorithm
2013: RSA 2013 conference report
2007: A collection of algorithmic problems (based on Ghodsi’s algorithm design course)

Last update: 24 October 2025. Go back to my homepage.