# 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

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
A Survey on the Cops and Robber Game [in Persian], Bachelor’s thesis at Sharif University of Technology (source files in Unicode-TeX-e-Parsi format)

## Unpublished and Expository Articles

2018
The total variation distance between high-dimensional Gaussians, 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: 6 June 2021. Go back to my homepage.