AM's publications
Selected publications
 [Learning theory] Peter L. Bartlett, Nick Harvey, Chris Liaw, and AM,
Nearlytight VCdimension and pseudodimension bounds for piecewise linear neural networks,
extended abstract in COLT'17; full version on arXiv.
 [Discrete probability] Omer Angel, AM, and Yuval Peres,
String of diamonds is tight for rumor spreading,
conference version in RANDOM'17;
full version on arXiv.
 [Graph theory] Noga Alon and AM,
Chasing a Fast Robber on Planar Graphs and Random Graphs, Journal of Graph Theory 2015
(final draft).
 [Random matrices] Chris Liaw, AM, Yaniv Plan, and Roman Vershynin, A simple tool for bounding the deviation of random matrices on geometric sets,
GAFA Seminar Notices 2017 (arXiv).
 [Algorithmic game theory] 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 (conference version in SPAA 2011; arXiv).
 [Random graphs] AM, Justifying the smallworld phenomenon via random recursive trees,
Random Structures & Algorithms 2017 (arXiv).
 [Stochastic geometry] AM and Nick Wormald, On the Stretch Factor of Randomly Embedded Random Graphs, Discrete & Computational Geometry 2013 (arXiv).
 [Graph theory] AM, Lower bounds for the cop number when the robber is fast, Combinatorics, Probability and Computing 2011.
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.
Submitted

Hassan Ashtiani,
Shai BenDavid,
Nick Harvey, Christopher Liaw,
AM, and Yaniv Plan,
Settling the Sample Complexity for Learning Mixtures of Gaussians, submitted, February 2018 (arXiv).

Peter L. Bartlett,
Nick Harvey, Chris Liaw, and AM,
Nearlytight VCdimension and pseudodimension bounds for piecewise linear neural networks, submitted, October 2017 (extended abstract in COLT'17, full version on arXiv).

Luc Devroye,
Vida Dujmovic,
Alan Frieze, AM,
Pat Morin, and
Bruce Reed, Notes on Growing a Tree in a Graph, submitted, October 2017 (arXiv).

O. Angel, AM, and Y. Peres,
String of diamonds is tight for rumor spreading,
submitted, July 2017
(conference version in RANDOM 2017;
full version on arXiv).
Refereed journals
 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
 H. Ashtiani, S. BenDavid and AM,
SampleEfficient Learning of Mixtures, accepted in AAAI 2018
(arXiv).
 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.)
 Some techniques in density estimation, with Hassan Ashtiani, unpublished tutorial, January 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: 19 February 2018