This is a webpage for Adam Marcus.
Specifically, Adam W. Marcus the mathematician, not to be confused with (for example)



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 learningdriven 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.
I currently hold the Chair of Combinatorial Analysis in the School of Mathematics at EPFL in Lausanne, Switzerland.
You can find my contact information here.
For potential students:
Students wishing to come to EPFL for a Ph.D. need to apply to a doctoral program.
The mathematics program is EDMA and the computer science one is EDIC.
Part of the application process will ask you to list faculty that you would have interest in working with.
You should put my name if you want me to see the application.
My ability to take students changes all of the time, so if you do not hear from me, it is very likely that I am not able to take any students at that time.
For those looking to come to EPFL for a summer project, the only program that I am aware of is this one in the computer science department.
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 things 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 highdimensional vector spaces.
In particular, I have a growing interest in a number of topics in machine learning, computational geometry, and optimization.
When I am pretending to be a Frankensteinlike combination of the two, my interests lie in what I like to call "combinatorial linear algebra," a mixing of ideas from the theory of stable polynomials, convex geometry, geometric functional analysis, convex programming, and (of course) 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.
Students:
I currently advise two graduate students from my time at Princeton (both in the PACM program): Aurelien Gribinski and Benno Mirabelli.
Support:
My research at Princeton was supported by National Science Foundation CAREER grant, Grant No. DMS1552520.
My time at the Institute for Advanced Study was supported by a Von Neumman Fellowship, National Science Foundation Grant No. DMS1128155.
My research at Yale was funded in part by the National Science Foundation under a
Mathematical Sciences Postdoctoral Research Fellowship, Grant No. DMS0902962.
Some slides from previous talks:

Interlacing families and bipartite Ramanujan graphs PDF

Interlacing families and KadisonSinger PDF

A more general ``method of interlacing polynomials'' talk PDF

Polynomials and (finite) free probability PDF
Some actual talks:

Noncommutative 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 noncommutative probability can be used for their problems before investing any serious effort in learning any details." There is no actual computer science background needed.

Bounding roots of polynomials (and applications): A followup of the previous talk, it shows how to combine the ideas of noncommutative probability with polynomial convolutions to say nontrivial things in (for example) spectral graph theory.
Papers:
(in reverse chronological order of writing, not publication) [ With short descriptions when titles are ambiguous. ]
 A. Gribinski, A. W. Marcus,
A rectangular convolution for polynomials.
arXiv
[ Introduces convolutions for general singular value problems, with bounds on the largest root. ]
 A. W. Marcus,
N. Srivastava,
The solution of the KadisonSinger problem,
Current Developments in Mathematics, 2016.
arXiv
 V. Gorin, A. W. Marcus,
Crystallization of random matrix orbits,
International Mathematics Research Notices, 2020 (3), 883913.
arXiv
 A. W. Marcus,
A determinantal identity for the permanent of a rank 2 matrix,
preprint. PDF
 A. W. Marcus, W. Yomjinda,
Analysis of rank 1 perturbations in general β ensembles,
preprint. PDF
 A. W. Marcus,
Discrete unitary invariance.
arXiv
 A. W. Marcus,
Polynomial convolutions and (finite) free probability,
preprint. PDF
[ Shows that the finite free convolutions associated to the eigenvalues of Hermitian matrices, in the appropriate limit, become free convolutions. ]
 M. Bownik,
P. Casazza,
A. W. Marcus,
D. Speegle,
Improved bounds in Weaver and Feichtinger conjectures,
Crelles Journal, 2016.
arXiv
 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. Turned into a construction by Cohen. ]
 A. W. Marcus,
D. A. Spielman,
N. Srivastava,
Finite free convolutions of polynomials,
submitted.
arXiv
[ Original paper defining finite free convolutions (for eigenvalues of Hermite matrices and singular values of square matrices), with bounds on the largest root. ]
 A. W. Marcus,
D. A. Spielman,
N. Srivastava,
Ramanujan graphs and the solution of the KadisonSinger problem,
Proc. ICM, Vol III (2014), 375386.
arXiv
 A. W. Marcus,
D. A. Spielman,
N. Srivastava,
Interlacing families III: improved bounds for restricted invertibility,
accepted (Isr. J. Math.). arXiv
[ Arguably the first appearance of finite free convolutions. ]
 A. W. Marcus,
D. A. Spielman,
N. Srivastava,
Interlacing families II: mixed characteristic polynomials and the KadisonSinger problem,
Ann. of Math. 1821 (2015), 327350.
arXiv
 A. W. Marcus,
D. A. Spielman,
N. Srivastava,
Interlacing families I: bipartite Ramanujan graphs of all degrees,
Ann. of Math. 1821 (2015), 307325. (preliminary version appeared in FOCS 2013)
arXiv
[ Uses 2lifts to show existence of Ramanujan graphs. No construction known. ]
 M. Madiman, A. W. Marcus, P. Tetali,
Entropy and set cardinality inequalities for partitiondetermined functions,
Random Struct. Algorithms 40 (2012), no. 4, 399424.
PDF
 M. Klazar, A. Marcus,
Extensions of the linear bound in the FürediHajnal conjecture,
Adv. in Appl. Math. 38 (2006), no. 2, 258266.
PDF
PS
BibTeX entry

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

A. Marcus, G. Tardos,
Excluded permutation matrices and the StanleyWilf conjecture,
J. Combin. Theory Ser. A 107 (2004), no. 1, 153160.
PDF
PS
BibTeX entry

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

J. Goodwin, D. Johnston, A. Marcus,
Radio Channel Assignments,
UMAP Journal 21.3 (Fall 2000), 369378.
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:
Other (still mostly math) links:
 Many of my early results are due to the work I did in Budapest, where I was supported by The HungarianAmerican Fulbright Commission.
 Should you need to spend a substantial amount of time there as well, here is a good
HungarianEnglish and EnglishHungarian Translator.
 Should you need a reason to spend a substantial amount of time there, I highly recommend the
Budapest Semesters in Mathematics
program  it is easily the best overseas program for anyone interested in Discrete Math (that I am aware of). If (for some unfortunate reason) you are interested in other areas of mathematics, I have been told that the Budapest Semesters program and the
Math in Moscow program are the two best.

While I am shamelessly endorsing math programs, I must recommend both
Hampshire College Summer Studies in Mathematics (HCSSiM)
and Mathily
for any advanced highschoolers who like 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.
THIS PAGE IS NOT A PUBLICATION OF EPFL AND EPFL HAS NOT EDITED OR EXAMINED THE CONTENT.
THE AUTHOR OF THIS PAGE IS SOLELY RESPONSIBLE FOR ITS CONTENT.
