Squaring the circle

Andrew Marks


I'm an associate professor at UCLA. My research interests lie in descriptive set theory and its connections to related areas such as computability theory, combinatorics, ergodic theory, probability, operator algebras, and quantum information.

Office: MS 6228.

Email: marks@math.ucla.edu

Address: UCLA Mathematics
BOX 951555
Los Angeles, CA 90095-1555


Publications and preprints:

  1. Borel asymptotic dimension and hyperfinite equivalence relations (with Clinton Conley, Steve Jackson, Brandon Seward, and Robin Tucker-Drob). Preprint [ pdf | arXiv ]
  2. On a question of Slaman and Steel (with Adam Day). Submitted. [ arXiv | pdf ]
  3. Scott ranks of classifications of the admissibility equivalence relation (with William Chan and Matthew Harrison-Trainor). Submitted [ arXiv | pdf ]
  4. Descriptive graph combinatorics (with Alekos Kechris). Preprint [ pdf ].
  5. Distance from marker sequences in locally finite Borel graphs (with Clinton Conley) in Samuel Coskey and Grigor Sargysan eds. Trends in Set Theory, Contemp. Math. 752, (2020), 89-92 [ arXiv | pdf | doi ].
  6. Measurable realizations of abstract systems of congruences (with Clinton Conley and Spencer Unger). Forum of Math, Sigma 8, (2020) e10 [ arXiv | pdf | doi ].
  7. Hyperfiniteness and Borel combinatorics (with Clinton Conley, Steve Jackson, Brandon Seward, and Robin Tucker-Drob). J. European Math. Soc. 22, No. 3 (2020), 877-892 [ arXiv | pdf | doi ]
  8. Topological generators for full groups of hyperfinite pmp equivalence relations. Submitted. [ arXiv | pdf ]
  9. Folner tilings for actions of amenable groups (with Clinton Conley, Steve Jackson, David Kerr, Brandon Seward, and Robin Tucker-Drob). Mathematische Annalen 371 (2018), 663-683. [ arXiv | pdf | doi ]
  10. Jump operations for Borel graphs (with Adam Day). J. Symb. Log 82 (2018), 13-28. [ arXiv | pdf | doi].
  11. Borel circle squaring (with Spencer Unger). Ann. of Math. 186 (2017), 581-605. [ arXiv | pdf | doi | pictures ].
  12. Uniformity, universality, and computability theory. J. Math. Logic 17 (2017) no 1. [ arXiv | pdf | doi ]. Errata to the published version: errata
  13. The universality of poly-time Turing equivalence. Mathematical Structures in Computer Science (2016) [ arXiv | pdf | doi ].
  14. Brooks's theorem for measurable colorings (with Clinton Conley and Robin Tucker-Drob). Forum of Math. Sigma 4 (2016) [ arXiv | pdf | doi ].
  15. Baire measurable paradoxical decompositions via matchings (with Spencer Unger). Adv. Math. 289 (2016), 397-410. [ arXiv | pdf | doi ].
  16. A determinacy approach to Borel combinatorics. J. Amer. Math. Soc. 29 (2016), 579-600. [ arXiv | pdf | doi ]
  17. Martin's conjecture, arithmetic equivalence, and countable Borel equivalence relations (with Theodore Slaman and John Steel). Ordinal definability and recursion theory: The cabal seminar volume III, Lecture Notes in Logic 43, Cambridge University Press, 2016, 200-219. [ arXiv | pdf | doi ]
  18. Minimal Betti Numbers (with Christopher Dodd, Victor Meyerson, and Ben Richert). Communications in Algebra Vol 35 (3), 2007, pp 759-772. [ arXiv | doi ]


Teaching:

Fall 2020: MATH 285D, MIP*=RE The course will be an introduction to quantum information theory, with the goal of covering the recent result of Ji, Natarajan, Vidick, Wright, and Yuen that MIP*=RE: the class of languages which can be decided by a multiprover interactive protocol with a classical polynomial-time verifier and provers sharing arbitrarily many entangled qbits is equal to the class of all recursively enumerable languages. This implies a negative solution to the longstanding Connes embedding problem in operator algebras.

Prerequisites are basic computational complexity theory and some elementary algebra and functional analysis. We will not assume any familiarity with quantum computation or quantum information; we will cover the basics of these areas in the first few weeks.


Past Teaching:


Research notes (not intended for publication):

  1. A short proof of the Connes-Feldman-Weiss theorem. November 2017. [ pdf ]
  2. A Baire category proof of the Ackerman-Freer-Patel Theorem. May 2016. [ pdf ]
  3. Structure in complete sections of the shift action of a residually finite group. November 2013. [ pdf ]
  4. A short proof that an acyclic n-regular Borel graph may have Borel chromatic number n+1. May 2013. [ pdf ]
  5. Is the Turing jump unique? : Martin's conjecture and countable Borel equivalence relations. December 2011. [ pdf ]