For descriptions of my research projects, see my research page. For full list of publications, see below or my Google Scholar.

You may drop me an e-mail to get a copy of the following publications.

Authors are listed in alphabetical order. AM stands for my initials.

• Hossein Esfandiari, Amin Karbasi, AM, Vahab Mirrokni, Regret bounds for batched bandits, arXiv


• Gabor Lugosi and AM, Multiplayer bandits without observing collision information, arXiv

[AISTATS'20] Audrey Durand, Branislav Kveton, AM, Sharan Vaswani, Old dog learns new tricks: randomized UCB for bandit problems, arXiv

[AISTATS'20] Etienne Boursier, Emilie Kaufmann, AM, and Vianney Perchet, A practical algorithm for multiplayer bandits when arm means vary among players, arXiv

[NeurIPS'18] Hassan Ashtiani, Shai Ben-David, Nick Harvey, Christopher Liaw, AM, and Yaniv Plan, Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes, winner of a best paper award at Neural Information Processing Systems (formerly known as NIPS), conference version, full version

[AAAI'18] Hassan Ashtiani, Shai Ben-David and AM, Sample-Efficient Learning of Mixtures, conference paper, corrected version

[RANDOM'17] Omer Angel, AM, and Yuval Peres, String of diamonds is tight for rumor spreading, conference version, journal version

[COLT'17] Nick Harvey, Christopher Liaw, and AM, Nearly-tight VC-dimension bounds for piecewise linear neural networks, conference version, journal version

[IPDPS'17] Petra Berenbrink, Peter Kling, Christopher Liaw, AM, Tight Load Balancing via Randomized Local Search, conference paper

[WAW'15] Jeannette Janssen and AM, Rumours spread slowly in a small world spatial network, conference version, journal version

[PODC'15] Huseyin Acan, Andrea Collevecchio, AM, and Nick Wormald, On the push&pull protocol for rumour spreading, conference version, journal version

[DISC'14] AM and Ali Pourmiri, Randomized rumor spreading on poorly connected small-world networks, conference version, talk video, journal version

[RANDOM'14] AM and Nick Wormald, It's a small world for random surfers, conference version, journal version

[WAW'12] Soroush Alamdari and AM, On a DAG Partitioning problem, conference paper

[CCCG'11] AM, A randomly embedded random graphs is not a spanner, conference version, journal version

[SPAA'11] Shayan Ehsani, Mohammadamin Fazli, AM, Sina Sadeghian, Mohammadali Safari, Morteza Saghafian, and Saber Shokatfadaee, On a bounded budget network creation game, conference version, journal version

[Journal of the ACM] Hassan Ashtiani, Shai Ben-David, Nick Harvey, Christopher Liaw, AM, and Yaniv Plan, Near-optimal sample complexity bounds for robust learning of Gaussian mixtures via compression schemes, accepted (available on arXiv)

[Electronic Journal of Statistics] Luc Devroye, AM, and Tommy Reddad, The minimax learning rate of normal and Ising undirected graphical models, accepted (available on arXiv)

[Journal Machine Learning Research 2019] Peter L. Bartlett, Nick Harvey, Christopher Liaw, and AM, Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks

[Combinatorics Probability Computing 2019] Omer Angel, AM, and Yuval Peres, String of diamonds is tight for rumour spreading

[Random Structures Algorithms 2019] Luc Devroye, Vida Dujmovic, Alan Frieze, AM, Pat Morin, and Bruce Reed, Notes on Growing a Tree in a Graph

[SIAM Journal Discrete Mathematics 2017] Jeannette Janssen and AM, Rumours spread slowly in a small world spatial network

[GAFA Seminar Notices 2017] Cristopher Liaw, AM, Yaniv Plan, and Roman Vershynin, A simple tool for bounding the deviation of random matrices on geometric sets

[SIAM Journal Discrete Mathematics 2017] Huseyin Acan, Andrea Collevecchio, AM, and Nick Wormald, On the push&pull protocol for rumour spreading

[Random Structures Algorithms 2017] AM, Justifying the small-world phenomenon via random recursive trees

[Journal Applied Probability 2016] Andrea Collevecchio, AM, and Nick Wormald, Longest paths in random Apollonian networks and largest r-ary subtrees of random d-ary recursive trees

[Random Structures Algorithms 2015] AM and Ali Pourmiri, Randomized rumor spreading on poorly connected small-world networks

[Algorithmica 2015] AM and Nick Wormald, It's a small world for random surfers

[ACM Transactions Algorithms 2015] Shayan Ehsani, Mohammadamin Fazli, AM, Sina Sadeghian, Mohammadali Safari, Morteza Saghafian, and Saber Shokatfadaee, A bounded budget network creation game

[Journal Graph Theory 2015] Noga Alon and AM, Chasing a Fast Robber on Planar Graphs and Random Graphs (correction)

[Discrete Applied Mathematics 2015] AM, The fast robber on interval and chordal graphs

[Ars Combinatoria 2015] Saieed Akbari, Aliakbar Daemi, Omid Hatami, Adel Javanmard, and AM, Nowhere-zero unoriented flows in hamiltonian graphs

[Random Structures Algorithms 2014] Ehsan Ebrahimzadeh, Linda Farczadi, Jane Gao, AM, Cristiane Sato, Nick Wormald, Jonathan Zung, On Longest Paths and Diameter in Random Apollonian Networks

[SIAM Journal Discrete Mathematics 2013] AM, Dieter Mitsche, and Pawel Pralat, On the Maximum Density of Graphs with Unique-Path Labelings

[Discrete Computational Geometry 2013] AM and Nick Wormald, On the Stretch Factor of Randomly Embedded Random Graphs

[Annals Combinatorics 2012] AM, Cops and robber game with a fast robber on expander graphs and random graphs

[SIAM Journal Discrete Mathematics 2012] AM, On the density of nearly regular graphs with a good edge-labeling

[Combinatorics Probability Computing 2011] AM, Lower bounds for the cop number when the robber is fast

[Electronic Journal Combinatorics 2011] Noga Alon and AM, On a generalization of Meyniel’s conjecture on the cops and robbers game

[Discrete Mathematics 2011] AM, The capture time of grids

[Graphs Combinatorics 2010] Saieed Akbari, Aliakbar Daemi, Omid Hatami, Adel Javanmard, and AM, Zero-sum flows in regular graphs

[PhD thesis] Diameter and Rumour Spreading in Real-World Network Models, University of Waterloo, April 2015

[Master's thesis] Cops and Robber Game with a Fast Robber, University of Waterloo, March 2011

[Bachelor's thesis] Survey on the Cops and Robber Game (in Persian), Sharif University of Technology, July 2009, unicode-TeX-e-Parsi source files

• The total variation distance between high-dimensional Gaussians, with Luc Devroye and Tommy Reddad, unpublished research note, October 2018, arXiv


• Learning mixtures of high-dimensional Gaussians, with Hassan Ashtiani, Canadian Mathematical Society Research Note, June 2018


• Some techniques in density estimation, with Hassan Ashtiani, unpublished tutorial, February 2018, arXiv


• The quantum query complexity of determining whether a graph is connected, expository article, November 2013


• Kelner-Madry's $O(m \sqrt n )$ algorithm for generating random spanning trees, expository article, April 2011


• The search version of 2-dimensional Sperner's lemma is PPAD-complete, expository article, April 2011


• The giant component, expository article, July 2010


• Approximation algorithms for counting the number of perfect matchings in bipartite graphs, expository article, April 2010


• An agent that plays Pacman, with Arian Khosravi, technical report, January 2008.

• Review of "Understanding machine learning: from theory to algorithms," book review, July 2016, link to the book


• An introduction to asymptotic calculations, unpublished tutorial, June 2016


• Review of "Foundations of Data Science," book review, May 2016, link to the book


• The weather forecast problem and a fruitful algorithmic idea, expository article based on these notes on the multiplicative weight update method, February 2016


• Four examples of applying linear algebra in other areas, expository article based on this beautiful book by Jiri Matousek, October 2015


• Highlights of the SODA 2015 conference, conference report, July 2015


• Models for rumour spreading in social networks, survey article, February 2015


• The Grover's search algorithm, expository article, March 2014


• Highlights of the RSA 2013 conference, conference report, September 2013


• A collection of algorithmic problems, based on Mohammad Ghodsi’s Algorithms course, course material, July 2007