mitropolsky @ cs . columbia . edu
I also go by: Danny, Dan, Dani, Mito, Даня, Даниил Всеволодович Митропольский, 水戸智, 刘智龙
I am a PhD student at Columbia University in the Theory of Computation group and the NLP group.
I have the pleasure of being advised by Christos Papadimitriou and Tal Malkin. I am interested in everything, but my main research interests are:
- neurally-plausible, mathematical models of the brain
- complexity theory, including total complexity and foundational cryptography
- language; computational linguistics, NLP
About
Before starting my PhD, I lived in San Francisco and worked as a Software Engineer at Google on the Search team.
Before that, I did my undergrad at Yale University where I graduated summa cum laude with an intensive B.S. in Mathematics and a B.S. in Computer Science.
Languages
Languages are one of my greatest passions. I love to use them, so do not be shy if you know any of these.
I plan to update this section with my favorite resources, poems, and thoughts about languages.
- Fluent (C1-C2) in English, French, Spanish, Portuguese, Italian, Russian, Polish, Chinese (Mandarin), Japanese, German, American Sign Language (ASL)
- Advanced / Conversational (B2+) in Korean, Vietnamese
- Working on (B1+) Greek, Arabic
Publications
- D. Mitropolsky, C. Papadimitriou, "The Architecture of a Biologically Plausible Language Organ", 2023, in submission, Arxiv
- P. Harsha, D. Mitropolsky, A. Rosen, "Downward Self-Reducibility in TFNP", 14th Innovations in Theoretical Computer Science Conference (ITCS), 2023, Arxiv
- D. Mitropolsky, A. Ejaz, M. Shi, M. Yannakakis, C. Papadimitriou, "Center-Embedding and Constituency in the Brain and a New Characterization of Context-Free Languages", Natural Logic Meets Machine Learning (NALOMA), 2022
- F. d'Amore, D. Mitropolsky, P. Creszenzi, E. Natale, C. Papadimitriou, "Planning with Biological Neurons and Synapses", (AAAI), 2022, Arxiv
- D. Mitropolsky, M. Collins, C. Papadimitriou, "A Biologically Plausible Parser", Transactions of the Association for Computational Linguistics (TACL), 2021, Arxiv
- R. Kleinberg, D. Mitropolsky, C. Papadimitriou, “Total Functions in the Polynomial Hierarchy”, 12th Innovations in Theoretical Computer Science Conference (ITCS), 2021, ECCC
- C. Papadimitriou, S. Vempala, D. Mitropolsky, M. Collins, W. Maass, “Brain Computation by Assemblies of Neurons”, in PNAS, vol. 117, no. 25, June 2020
- C. Papadimitriou, S. Vempala, D. Mitropolsky, M. Collins, W. Maass, L. Abbott, “A Calculus for Brain Computation”, in CCNeuro, Berlin, Germany, 2019.
- D. Jensen, A. Deveau, J. Kainic, D. Mitropolsky, “Gonality of Random Graphs”, in Involve, vol. 9, no 4, 715-720, 2016
Selected Talks
- Invited talk on my brain research at the MIT CBMM (Center for Brains, Minds and Machines), Dec. 2023, Link (recording of in-person talk)
- Talk on my brain research at the Brown Theoretical Computer Science Seminar (this one is more CS-oriented) , Dec. 2023 Link (recording of in-person talk)
- Talk on my brain research at Tufts, Dec. 2023 Announcement link
- Talk on downward self-reducibility in TFNP (and the unlikelihood of recursive algorithms for factoring!), Jan 2023 Link (Zoom talk)
- Talk on total functions and the polynomial hierarchy (a new area of complexity theory!), Jan 2021, Link (Zoom talk)
Errata for Computational Complexity (Arora Barak)
Teaching
Industry research