About

I am a third-year PhD student in the theory group at UCSD, where I am advised by Daniel Kane and Shachar Lovett and supported by NSF and Jacobs Fellowships. I did my undergraduate BA in Mathematics at Harvard University with a minor in Computer Science. In my time there, I was lucky enough to work under Michael Mitzenmacher and Madhu Sudan.

I host the weekly UCSD Theory Lunch on Friday's. Past and upcoming talks can be found here.

I like singing, boardgames, squash, and sushi (in no particular order).

Interests

I am broadly interested in areas such as learning theory, computational geometry, combinatorics, approximation algorithms, and hardness of approximation. Currently, I mostly think about:

1. High Dimensional Expanders and Approximation Algorithms

High Dimensional Expansion is an emerging area with applications to a variety of areas including sampling, error correction, approximation algorithms, and more. I study the spectral and combinatorial structure of random walks on High dimensional expanders and am especially interested in their application to approximation algorithms and unique games. I am currently teaching a course on expanders and high-dimensional expansion with Shachar Lovett. It is open to the public, so if you are interested feel free to drop by! Info here.

2. Active Learning through Enriched Queries

When does adaptivity help us learn? In standard models, it is well known that adaptivity often provides no asymptotic benefit. I study how asking better questions allows us to build adaptive algorithms that break these standard lower bounds. If you're interested and/or new to this area, check out this recent blog post for a basic primer, which covers how the ability to compare data can drastically speed up and robustify learning!

Papers

Conference Papers

1. Active Learning with Bounded Memory through Enriched Queries
   Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz
   COLT 2021

2. The Power of Comparisons for Actively Learning Linear Separators
   Max Hopkins, Daniel Kane, Shachar Lovett
   NeurIPS 2020

3. Point Location and Active Learning: Learning Halfspaces Almost Optimally
   Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
   FOCS 2020

4. Noise Tolerant, Reliable Active Classification with Comparison Queries
   Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
   COLT 2020

5. Doppelgangers: the Ur-Operation and Posets of Bounded Height
   Thomas Browning, Max Hopkins, Zander Kelley
   Extended Abstract appeared in Proceedings of FPSAC 2018

6. Simulated Annealing for JPEG Quantization
   Max Hopkins, Michael Mitzenmacher, Sebastian Wagner-Carena
   DCC 2018 (poster)
   Code

Journal Papers

1. A Novel CMB Component Separation Method: Hierarchical Generalized Morphological Component Analysis
   Sebastian Wagner-Carena, Max Hopkins, Ana Rivero, Cora Dvorkin
   MNRAS, May 2020

Pre-prints

1. High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games
   Max Hopkins, Tali Kaufman, Shachar Lovett
   New version with Mitali Bafna in preparation

Manuscripts

1. Expanding Posets: Random Walks, Pseudorandomness, and Unique Games
   Max Hopkins, Tali Kaufman, Shachar Lovett
   In preparation. Companion paper to ``HDX: Random Walks...''

Miscellaneous Writing

• Representation-Theoretic Techniques for Independence Bounds of Cayley Graphs
  My undergraduate thesis under Madhu Sudan
  

• Bordism Homology
  A survey of un-oriented bordism homology

Talks

• Point Location and Active Learning (Harvard CMSA)
  

• High Dimensional Expanders and Unique Games (UW Seminar, SoS+TCS Seminar, Cornell Theory Tea, Chicago/TTIC (Reading Group))
  

• Point Location and Active Learning Halfspaces (FOCS '20)
  

• Noise Tolerant Active Learning with Comparisons (COLT '20)
  

• Active Learning with Bounded Memory
  

• Point Location and Active Learning
  

• An Open Problem in Noisy Sorting
  

• Small Set Expansion in the Johnson Graph through High Dimensional Expansion
  

• High Dimensional Expanders: The Basics
  

• Reasoning in the Presence of Noise
  

• The Power of Comparisons for Active Learning
  

• On the Cohomology of Dihedral Groups
  

• Understanding Doppelgangers and the Ur-Operation
  

Teaching

1. Co-teaching CSE 291, Expander graphs and high-dimensional expanders, Spring 2021.
   

2. TA for CSE 200, Computability and Complexity, Winter 2020.
   

1. TA for APMTH 106, Applied Algebra, Fall 2017.