This is a webpage for Adam Marcus. Specifically, Adam W. Marcus the mathematician, not to be confused with (for example) the film director, or the database expert, or the Retraction Watch blogger, or the cancer researcher.

About me:

I received my B.A./M.A. in Mathematics from Washington University in St. Louis in 2003 and my Ph.D. in Algorithms, Combinatorics, and Optimization under the supervision of Prasad Tetali from Georgia Tech in 2008. I then spent 4 years as a Gibbs Assistant Professor in Applied Mathematics at Yale University under the supervision of Daniel Spielman, followed by 3 years as Chief Scientist at a machine learning-driven startup called Crisply. I then spent 5 years as an Assistant Professor in the Mathematics Department and Program in Applied and Computational Mathematics at Princeton University. Most recently, I held the Chair of Combinatorial Analysis in the School of Mathematics at EPFL in Lausanne, Switzerland for 3 years (ending in February 2023).

For potential students:

Research interests:

When I am pretending to be a mathematician, my main research interests lie in various areas of combinatorics. In particular, I tend to like problems that are constrained in ways that current tools are not equipped to deal with (like restricted orderings and, more recently, dimensionality restrictions).

When I am pretending to be a computer scientist, my interests lie in areas that involve algorithms and computation in high-dimensional vector spaces. In particular, I have a growing interest in a number of topics in spectral graph theory, machine learning, computational geometry, and optimization.

When I am pretending to be a Frankenstein-like combination of the two, I tend to work on problems in what has come to be known as "finite free probability," an area that seems to lie in the intersection of a number of other (more standard) topics, including the theory of stable polynomials, convex geometry, geometric functional analysis, random matrix theory, convex programming, linear algebra and combinatorics.

Teaching interests:

My primary interest here lies in creating innovative curricula for general education mathematics courses. There are many practical skills that mathematics can teach someone (problem solving, understanding of probability and statistics, etc) and the current paradigm does not address these as adequately as it could.

Previous Ph.D. students (now graduated):

• Benno Mirabelli (PACM program at Princeton)
• Aurelien Gribinski (PACM program at Princeton)

Previous Ph.D. students (transferred upon my retirement):

• Reihaneh Malekian (EDMA at EPFL)
• Amire Bendjeddou (EDMA at EPFL)

Support:

My research at Princeton was supported by a National Science Foundation CAREER grant, Grant No. DMS-1552520.

My time at the Institute for Advanced Study was supported by a Von Neumman Fellowship, National Science Foundation Grant No. DMS-1128155.

My time at Yale was funded in part by the National Science Foundation under a Mathematical Sciences Postdoctoral Research Fellowship, Grant No. DMS-0902962.

My work with Gábor Tardos was made possible due to the support of the The Hungarian-American Fulbright Commission.

Some slides from previous talks:

1. Interlacing families and bipartite Ramanujan graphs PDF
2. Interlacing families and Kadison-Singer PDF
3. A more general "method of interlacing polynomials" talk PDF
4. Polynomials and (finite) free probability PDF

Some actual talks:

1. Non-commutative probability for computer scientists: Note that the use of the term "computer scientist" here is short for "any person that would like to see how results from non-commutative probability can be used for their problems before investing any serious effort in learning any details." There is no actual computer science background needed.


2. Bounding roots of polynomials (and applications): A follow-up of the previous talk, it shows how to combine the ideas of non-commutative probability with polynomial convolutions to say non-trivial things in (for example) spectral graph theory.

Papers:

1. A. W. Marcus, Finite free point processes, preprint (2022). arXiv
   [ Examples of how finite free probability seems to capture the limiting behavior of β ensembles (as β goes to infinity). Also gives an example where the finite free probability statistics are tractable but formulas for general β are not (at least at the time of writing). ]


2. A. Gribinski, A. W. Marcus, Polynomial time construction of biregular, bipartite Ramanujan graphs of all degrees, preprint (2020). arXiv
   [ Extends results of IF4 to certain biregular graphs. ]


3. A. W. Marcus, A class of multivariate convolutions (and applications), preprint (2020). arXiv


4. A. Gribinski, A. W. Marcus, A rectangular additive convolution for polynomials, Combinatorial Theory, 2(1), 2022. arXiv
   [ Introduces convolutions for general singular value problems, with bounds on the largest root. ]


5. V. Gorin, A. W. Marcus, Crystallization of random matrix orbits, International Mathematics Research Notices, 2020 (3), 883-913. arXiv


6. A. W. Marcus, A determinantal identity for the permanent of a rank 2 matrix, Amer. Math. Monthly, 129:10, 962-971 (2022). arXiv


7. A. W. Marcus, W. Yomjinda, Analysis of rank 1 perturbations in general β ensembles, preprint (2016). PDF


8. A. W. Marcus, Discrete unitary invariance. preprint (2016). arXiv
   


9. A. W. Marcus, Polynomial convolutions and (finite) free probability, preprint (2021). arXiv
   [ Shows that the finite free convolutions associated to the eigenvalues of Hermitian matrices, in the appropriate limit, should become free convolutions. The reason for using the word ``should'' is that some of the proofs are not completely rigorous (they require uniform convergence, which is not proved). However, I believe all of the results have since been proved independently using moment-cumulant relations, (see this paper for additive convolutions and this one for multiplicative convolutions). ]


10. A. W. Marcus, N. Srivastava, The solution of the Kadison-Singer problem, Current Developments in Mathematics, 2016. arXiv


11. M. Bownik, P. Casazza, A. W. Marcus, D. Speegle, Improved bounds in Weaver and Feichtinger conjectures, Crelles Journal, 2016. arXiv


12. A. W. Marcus, D. A. Spielman, N. Srivastava, Interlacing families IV: bipartite Ramanujan graphs of all sizes, FOCS (2015). arXiv
    [ Uses finite free convolutions to show the existence of Ramanujan graphs. This is the basis for the polynomial time construction of Michael B. Cohen. ]


13. A. W. Marcus, D. A. Spielman, N. Srivastava, Finite free convolutions of polynomials, Probab. Theory Relat. Fields 182, 807-848 (2022). arXiv
    [ Original paper defining finite free convolutions (for eigenvalues of Hermite matrices and singular values of square matrices), with bounds on the largest root. ]


14. A. W. Marcus, D. A. Spielman, N. Srivastava, Ramanujan graphs and the solution of the Kadison-Singer problem, Proc. ICM, Vol III (2014), 375-386. arXiv


15. A. W. Marcus, D. A. Spielman, N. Srivastava, Interlacing families III: improved bounds for restricted invertibility, Isr. J. Math. 247, 519-546 (2022). arXiv
    [ Arguably the first appearance of finite free convolutions. ]


16. A. W. Marcus, D. A. Spielman, N. Srivastava, Interlacing families II: mixed characteristic polynomials and the Kadison-Singer problem, Ann. of Math. 182-1 (2015), 327-350. arXiv


17. A. W. Marcus, D. A. Spielman, N. Srivastava, Interlacing families I: bipartite Ramanujan graphs of all degrees, Ann. of Math. 182-1 (2015), 307-325. (preliminary version appeared in FOCS 2013) arXiv
    [ Uses 2-lifts to show existence of Ramanujan graphs. No construction known. ]


18. M. Madiman, A. W. Marcus, P. Tetali, Entropy and set cardinality inequalities for partition-determined functions, Random Struct. Algorithms 40 (2012), no. 4, 399-424. PDF


19. M. Klazar, A. Marcus, Extensions of the linear bound in the Füredi-Hajnal conjecture, Adv. in Appl. Math. 38 (2006), no. 2, 258-266. PDF PS BibTeX entry


20. A. Marcus, G. Tardos, Intersection reverse sequences and geometric applications, J. Combin. Theory Ser. A 113 (2006), no. 4, 675-691. PDF PS BibTeX entry
    (Preliminary version appeared in GD 2004 (J. Pach, ed.), LNCS, no. 3383, 2004, 349-359)


21. A. Marcus, G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107 (2004), no. 1, 153-160. PDF PS BibTeX entry
    


22. R. Kawai, A. Marcus, Negative Conductance in Two Finite-size Coupled Brownian Motor Models, manuscript (2000). PDF PS BibTeX entry


23. J. Goodwin, D. Johnston, A. Marcus, Radio Channel Assignments, UMAP Journal 21.3 (Fall 2000), 369-378. Preprint version: PDF PS BibTeX entry
    **DISCLAIMER**: This paper was written as a contest entry to the MCM 2000 competition, which took place over a span of 4 days (not much time). It is here because it has some mathematical value, but there are some mistakes so please read at your own risk!!

Links related to my research:

• Here are links to Mathworld's listing and Wikipedia's listing of the Stanley-Wilf Conjecture.


• Both the Stanley-Wilf and Kadison-Singer conjectures appear in Wikipedia's list of "Recently Solved Problems".


• Our solution of the Kadison-Singer problem was the focus of workshops at AIM, MSRI and Oberwolfach and was the subject of an invited talk at ICM 2014.


• Quanta magazine wrote a very nice article about our work leading to the resolution of the Kadison-Singer problem.


• Our solution of the Stanley-Wilf conjecture is one of the highlights of the book, Combinatorics of Permutations, by Miklós Bóna.


• Here are some kind words from Doron Zeilberger regarding one of my papers, as well as his "Loving Rendition" of the proof and a transcript of the talk he gave at Georgia Tech.


• My work with Gábor Tardos and Martin Klazar was honored by SIAM with the 2008 Dénes Kőnig Prize.


• My work with Dan Spielman and Nikhil Srivastava was honored by SIAM with the 2014 George Pólya Prize in Mathematics and by the NAS with the 2021 Michael and Sheila Held Prize and by the AMS with the 2022 Ciprian Foias Prize.


• My share of (the monetary award that accompanied) the Held Prize was used to start the Steve Sigur Fund for Young Scholars Programs at the American Mathematical Society in memory of Steve Sigur. The fund's proceeds are used to support opportunities for high-school students to engage in mathematics, via the AMS Epsilon Fund program.


• My work with Joshua Vekhter was honored by the AMS with the 2009 Karl Menger Award.

Other (still mostly math) links:

• One of the greatest influences in my choice to become a mathematician was my year abroad at the Budapest Semesters in Mathematics For those looking for an overseas program, I am told that Math in Moscow is also a good option.


• Another large influence came when I was still in high school, when I attended the Hampshire College Summer Studies in Mathematics (HCSSiM). I also highly recommend the Mathily program for any advanced high-schoolers who might have an interest in math.


• My Erdős number is 2 - many thanks to Russ Lyons, who told me how to make an ő in HTML.


• The best way I have found to keep up to date on the most current scientific (not just math) results is through arXiv.


• I was forced to learn how to use source control and now I am in the habit of forcing others to learn it. I prefer git simply because that is what I learned first. You can get started easily with Bitbucket or github. Here is a nice tutorial written specifically for mathematicians.