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.
H. Ashtiani, S. Ben-David, N. Harvey, C. Liaw, AM, and Y. Plan,
Near-optimal Sample Complexity Bounds for Robust Learning of Gaussian Mixtures via Compression Scheme,
submitted, July 2019
(conference version in Neurips 2018; full version on arXiv).
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).
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,
Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks, Journal of Machine Learning Research (2019), 20(63), 1–-17 (extended abstract in COLT'17).
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 small-world phenomenon via random recursive trees,
Random Structures & Algorithms (2017), 50 (2), 201--224 (arXiv).
- A. Collevecchio, AM, and N. Wormald,
Longest paths in random Apollonian networks and largest r-ary subtrees of random d-ary recursive trees,
Journal of Applied Probability (2016), , 53 (3), 846--856 (arXiv).
- AM and A. Pourmiri, Randomized rumor spreading on poorly connected small-world networks,
Random Structures & Algorithms (2015),
(this is a full version of this paper and is available on arXiv)
- 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), 81--96
(draft version on Noga's homepage) (correction).
- AM, The fast robber on interval and chordal graphs, Discrete Applied Mathematics (2015), 180, 188--193 (arXiv).
- S. Akbari, A. Daemi, O. Hatami, A. Javanmard, and AM, Nowhere-zero unoriented flows in hamiltonian graphs, Ars Combinatoria (2015), volume CXX, 51--63.
- 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), 703--725
(extended abstract version, draft of full version on arXiv).
- AM, D. Mitsche, and P. Pralat, On the Maximum Density of Graphs with Unique-Path Labelings, SIAM Journal on Discrete Mathematics (2013), 27(3), 1228--1233 (arXiv).
- AM and N. Wormald, On the Stretch Factor of Randomly Embedded Random Graphs, Discrete & Computational Geometry (2013) 49, 647--658 (arXiv).
- AM, Cops and robber game with a fast robber on expander graphs and random graphs, Annals of Combinatorics (2012), 16(4), 829--846 (arXiv).
- AM, On the density of nearly regular graphs with a good edge-labeling, SIAM Journal on Discrete Mathematics (2012), 26(3), 1265--1268 (arXiv link).
- AM, Lower bounds for the cop number when the robber is fast, Combinatorics, Probability and Computing (2011) 20, 617--621.
- 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), 102--105.
- S. Akbari, A. Daemi, O. Hatami, A. Javanmard and AM, Zero-sum flows in regular graphs, Graphs and Combinatorics 26 (2010), 603--615.
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
- H. Ashtiani, S. Ben-David and AM,
Sample-Efficient 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,
Nearly-tight VC-dimension 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 small-world 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).
Other (Expository articles, Course projects, etc.)
- 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 Thirty-three 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.
back to my homepage
Luc Devroye, AM, and Tommy Reddad,
The total variation distance between high-dimensional Gaussians,
unpublished research note, November 2018.
- Learning mixtures of high-dimensional
Gaussians, with Hassan Ashtiani, Canadian Mathematical Society Research Notes, June 2018, pages 16--17.
- 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.
- Kelner-Madry'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 2-dimensional Sperner's lemma is PPAD-complete, 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.
Last updated: 22 July 2019