AM's publications
For a detailed description of problems I have worked on, see my research page.
For full list of publications, see below or my Google Scholar.
In all of these papers, authors are listed in alphabetical order.
Submitted

H. Ashtiani, S. BenDavid, N. Harvey, C. Liaw, AM, and Y. Plan,
Nearoptimal Sample Complexity Bounds for Robust Learning of Gaussian Mixtures via Compression Scheme,
submitted, July 2019
(conference version in Neurips 2018; full version on arXiv).

Etienne Boursier,
Emilie Kaufmann, AM, and Vianney Perchet,
A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players,
submitted, May 2019 (arXiv).

Gabor Lugosi and AM,
Multiplayer bandits without observing collision information,
submitted, August 2018 (arXiv).

Luc Devroye, AM, and Tommy Reddad,
The minimax learning rate of normal and Ising undirected graphical models,
submitted, June 2018 (arXiv).
Refereed journals

O. Angel, AM, and Y. Peres,
String of diamonds is tight for rumour spreading,
accepted in Combinatorics, Probability and Computing, July 2019
(conference version in RANDOM 2017;
full version on arXiv).

Peter L. Bartlett,
Nick Harvey, Chris Liaw, and AM,
Nearlytight VCdimension and pseudodimension bounds for piecewise linear neural networks, Journal of Machine Learning Research (2019), 20(63), 1–17 (extended abstract in COLT'17).

Luc Devroye,
Vida Dujmovic,
Alan Frieze, AM,
Pat Morin, and
Bruce Reed, Notes on Growing a Tree in a Graph, Random Structures & Algorithms 2019 (arXiv).
 J. Janssen and AM, Rumours spread slowly in a small world spatial network,
SIAM Journal on Discrete Mathematics (2017), 31(4), 2414–2428.
(Full version of this; arXiv link).
 C. Liaw, AM, Y. Plan, and R. Vershynin, A simple tool for bounding the deviation of random matrices on geometric sets,
GAFA Seminar Notices, 2017 (arXiv link).
 H. Acan, A. Collevecchio, AM, and N. Wormald, On the push&pull protocol for rumour spreading,
SIAM Journal on Discrete Mathematics (2017), 31 (2), 647–668 (this is a full version of this paper and is available on arXiv).
 AM, Justifying the smallworld phenomenon via random recursive trees,
Random Structures & Algorithms (2017), 50 (2), 201224 (arXiv).
 A. Collevecchio, AM, and N. Wormald,
Longest paths in random Apollonian networks and largest rary subtrees of random dary recursive trees,
Journal of Applied Probability (2016), , 53 (3), 846856 (arXiv).
 AM and A. Pourmiri, Randomized rumor spreading on poorly connected smallworld networks,
Random Structures & Algorithms (2015),
49(1), 185208
(this is a full version of this paper and is available on arXiv)
(talk video).
 AM and N. Wormald, It's a small world for random surfers, Algorithmica (2015) (full version of this) (arXiv).
 S. Ehsani, S. Fadaee, M. Fazli, AM, S. Sadeghian, M. Safari, and M. Saghafian, A bounded budget network creation game, ACM Transactions on Algorithms (2015), 11(4), article 34 (full version of this) (arXiv).
 N. Alon and AM,
Chasing a Fast Robber on Planar Graphs and Random Graphs, Journal of Graph Theory (2015), 78(2), 8196
(draft version on Noga's homepage) (correction).
 AM, The fast robber on interval and chordal graphs, Discrete Applied Mathematics (2015), 180, 188193 (arXiv).
 S. Akbari, A. Daemi, O. Hatami, A. Javanmard, and AM, Nowherezero unoriented flows in hamiltonian graphs, Ars Combinatoria (2015), volume CXX, 5163.
 E. Ebrahimzadeh, L. Farczadi, P. Gao, AM, C. Sato, N. Wormald, J. Zung, On Longest Paths
and Diameter in Random Apollonian Networks, Random Structures & Algorithms (2014), 45(4), 703725
(extended abstract version, draft of full version on arXiv).
 AM, D. Mitsche, and P. Pralat, On the Maximum Density of Graphs with UniquePath Labelings, SIAM Journal on Discrete Mathematics (2013), 27(3), 12281233 (arXiv).
 AM and N. Wormald, On the Stretch Factor of Randomly Embedded Random Graphs, Discrete & Computational Geometry (2013) 49, 647658 (arXiv).
 AM, Cops and robber game with a fast robber on expander graphs and random graphs, Annals of Combinatorics (2012), 16(4), 829846 (arXiv).
 AM, On the density of nearly regular graphs with a good edgelabeling, SIAM Journal on Discrete Mathematics (2012), 26(3), 12651268 (arXiv link).
 AM, Lower bounds for the cop number when the robber is fast, Combinatorics, Probability and Computing (2011) 20, 617621.
 N. Alon and AM, On a generalization of Meyniel’s conjecture on the cops and robbers game, The Electronic Journal of Combinatorics 18 (2011), #P19.
 AM, The capture time of grids, Discrete Mathematics 311 (2011), 102105.
 S. Akbari, A. Daemi, O. Hatami, A. Javanmard and AM, Zerosum flows in regular graphs, Graphs and Combinatorics 26 (2010), 603615.
Refereed conferences

Hassan Ashtiani,
Shai BenDavid,
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 2018
(arXiv).
 H. Ashtiani, S. BenDavid and AM,
SampleEfficient Learning of Mixtures, in Proceedings of AAAI 2018
(the version published in conference proceedings had a bug, which was fixed in the updated arXiv version).
 O. Angel, AM, and Y. Peres,
String of diamonds is tight for rumor spreading,
in Proceedings of RANDOM 2017 (arXiv).
 N. Harvey, C. Liaw, and AM,
Nearlytight VCdimension bounds for piecewise linear neural networks,
in Proceedings of COLT 2017 (full version on arXiv).
 P. Berenbrink, P. Kling, C. Liaw, AM, Tight Load Balancing via Randomized Local Search, In Proceedings of IPDPS 2017 (arXiv).
 J. Janssen and AM, Rumours spread slowly in a small world spatial network, in Proceedings of WAW 2015.
 H. Acan, A. Collevecchio, AM, and N. Wormald, On the push&pull protocol for rumour spreading, in Proceedings of PODC 2015 (full version is on arXiv).
 AM and A. Pourmiri, Randomized rumor spreading on poorly connected smallworld networks, in Proceedings of DISC 2014 (talk video) (journal version on arXiv).
 AM and N. Wormald, It's a small world for random surfers, in Proceedings of APPROX/RANDOM 2014 (full version in Algorithmica and on arXiv).
 S. Alamdari and AM, On a DAG Partitioning problem, in Proceedings of WAW 2012.
 AM, A randomly embedded random graphs is not a spanner, in Proceedings of CCCG 2011 (full version in Discrete & Computational Geometry).
 S. Ehsani, M. Fazli, AM, S. Sadeghian, M. Safari, M. Saghafian, and S. Shokatfadaee, On a bounded budget network creation game, SPAA 2011
(full version in ACM Transactions on Algorithms and on arXiv).
Theses
In Persian
 Introduction of the book Understanding machine learning: from theory to algorithms, July 2016 (link to the book).
 Asymptotic calculations, June 2016.
 Introduction of the book Foundations of Data Science, May 2016 (link to the January 2016 edition of the book).
 The weather forecast problem and a fruitful algorithmic idea, based on these notes on the multiplicative weight update method, February 2016.
 Four examples of applying linear algebra in other areas, based on the beautiful book Thirtythree miniatures by Jiri Matousek, expository article, October 2015.
 Highlights of SODA 2015, 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.
 Some hints about using Scheme, January 2008.
 A collection of algorithmic problems, based on M. Ghodsi’s Algorithms course, July 2007.
Other (Expository articles, Course projects, etc.)

Luc Devroye, AM, and Tommy Reddad,
The total variation distance between highdimensional Gaussians,
unpublished research note, November 2018.
 Learning mixtures of highdimensional
Gaussians, with Hassan Ashtiani, Canadian Mathematical Society Research Notes, June 2018, pages 1617.
 Some techniques in density estimation, with Hassan Ashtiani, unpublished tutorial, February 2018.
 Some mathematical formulae, useful in random structures and algorithms, dynamic handbook, latest update: January 2018.

Quantum query complexity of determining whether a graph is connected
(based on this paper), a report for the
Quantum Information Processing course, November 2013.
 KelnerMadry's O(m √ n log (1/δ)) algorithm for generating random spanning trees, describes this paper, a report for Randomized Algorithms course, April 2011.
 The search version of 2dimensional Sperner's lemma is PPADcomplete, describes this paper, a report for Topological Methods in Graph Theory course, April 2011.
 The Giant Component, a report for Advanced Random Graph Theory reading course, University of Waterloo, July 2010.
 Approximation algorithms for counting the number of perfect matchings in bipartite graphs, describes this paper and an outline of this one, a report for Approximation Algorithms course, April 2010.
 An agent that plays Pacman (joint work with A. Khosravi), a manuscript describing our agent for playing Pacman, January 2008.
back to my homepage
Last updated: 22 July 2019