Tonton Cris fait dessins, comme moi! --- Alena Krzakala-Zdeborova
Which links matter most? Sparsifying epidemic models with effective resistance. Network Science Society Colloquium, March 27 2024. Joint work with Alexander Mercier and Sam Scarpino.
Pretrial Risk Assessment on the Ground: Lessons from New Mexico. Given at a workshop on Algorithms, Fairness, and Equity at the Simons Laufer Mathematical Sciences Institute (formerly MSRI) in August 2023.
The Dynamics of Computation. This is a repeat of a colloquium given at the Hypatia Summer School at the Centre de Recerca Matematica in Barcelona.
The physics of inference, phase transitions, and networks, a Rutgers Mathematical Physics Webinar.
Algorithms from Tensor Networks (page down for video) given at the 2023 Simons Collaboration on Cracking the Glass Problem. Based on joint work with Tim Kunisky and Alex Wein.
Percolation is Odd, a short fun talk given at the Los Angeles Combinatorics and Complexity Seminar. Joint work with Stephan Mertens.
The Planted Matching Problem. Joint work with Mehrdad Moharrami and Jiaming Xu, given at Allerton '19, the MIT Stochastics and Statistics Seminar, and at the Simons Institute (video).
Easy, Hard, and Impossible Problems: The Limits of Computation. Ulam Memorial Lecture #1, September 2018.
Data, Algorithms, Justice, and Fairness. Ulam Memorial Lecture #2, September 2018.
Interdependence Between Network Layers, or Predicting One Kind of Link from Another. video and slides. We use a kind of Poisson tensor factorization to analyze multilayer networks from anthropology and (less successfully) malaria. Joint work with Caterina De Bacco, Dan Larremore, and Elly Power.
Lectures on Computational Complexity and Belief Propagation. Boulder School for Condensed Matter and Materials Physics.
What Can Physics Tell Us About Inference? Video (if that doesn't work, try youtube) from the Data Science Colloquium at Ecole Normale Superieure.
The Hunt for a Quantum Algorithm for Graph Isomorphism. Video of a Physics Department Colloquium at Ecole Normale Superieure. Based on older work, including slides from QIP (Quantum Information Processing) 2006, describing joint work with Alex Russell and Leonard Schulman.
Turing Lectures on Complexity, Phase Transitions, and Inference. ICTS, Tata Institute of Fundamental Research, Bangalore. Slides (of the first lecture) and videos (of all three), or youtube of the first one.
Information-theoretic bounds and phase transitions in community detection and high-dimensional clustering. Videos from the the Isaac Newton Institute and the Simons Institute for the Theory of Computing; also a chalk talk given at Institute Henri Poincare and Caltech. Joint work with Jess Banks, Joe Neeman, Praneeth Netrapalli, Roman Vershynin, and Jiaming Xu.
Sending Secrets: Security and Privacy in a Quantum World. Distinguished Lecture, University of South Floria (slides), John von Neumann Public Lecture Series, Wisconsin Institutes for Discovery (video) and a Santa Fe Institute Community Lecture (video).
Lectures on Representation Theory and Quantum Computing: Modern Applications of Representation Theory, University of Chicago, August 2014. Lecture 1 (Intro and Simon's algorithm), Lecture 2 (Shor's algorithm and the Hidden Subgroup Problem), Lecture 3 (The symmetric group and Graph Isomorphism).
Physics-Inspired Algorithms and Phase Transitions in Community Detection. Versions given at the Stanford RAIN seminar, UC Santa Cruz, NIPS, MSR New England, Harvard CS, Distinguished Lecture, University of South Floria (slides), John von Neumann Public Lecture Series, Wisconsin Institutes for Discovery (video) and a Santa Fe Institute Community Lecture (video).
Lectures on Representation Theory and Quantum Computing: Modern Applications of Representation Theory, University of Chicago, August 2014. Lecture 1 (Intro and Simon's algorithm), Lecture 2 (Shor's algorithm and the Hidden Subgroup Problem), Lecture 3 (The symmetric group and Graph Isomorphism).
Physics-Inspired Algorithms and Phase Transitions in Community Detection. Versions given at the Stanford RAIN seminar, UC Santa Cruz, NIPS, MSR New England, Harvard CS, Princeton PACM, Rutgers CS, NetSci, SIAM, MIT LIDS seminar, Northeastern, Boston University, Dartmouth. Joint work with Aurelien Decelle, Florent Krzakala, Elchanan Mossel, Joe Neeman, Mark Newman, Allan Sly, Lenka Zdeborova, and Pan Zhang. Significant overlap with the following, but with new material on the non-backtracking operator, semisupervised learning, hierarchical clustering, and message-passing for modularity and statistically significant communities. Also a video of a broadly accessible version, from SFI's 2014 Science Board Symposium.
Finding Hidden Structure in Networks. Physics and Astronomy Complex Systems Seminar, Northwestern University, October 2012; Berkeley Probability Seminar, November 2012; UNM Computer Science Colloquium, April 2013, Michigan Statistics Seminar, October 2013; Indiana University Computer Science Colloquium, October 2013; University of Chicago Statistics Colloquium, November 2013. Joint work with lots of people, including Aaron Clauset, Mark Newman, Xiaoran Yan, Yaojia Zhu, Lenka Zdeborova, Florent Krzakala, and Cosma Shalizi. For some reason, slide 32 doesn't display on Adobe Reader; other pdf viewers seem to work fine.
The Power of Choice in Random Satisfiability. RANDOM 2013, Berkeley, August 2013. Joint work with Varsha Dani, Josep Diaz, and Tom Hayes.
Universality, hardness, engineering, and messiness. Workshop on Natural Algorithms and the Sciences, Princeton, May 2013; and Complex Systems Seminar, University of Michigan, November 2013.
P vs. NP, Phase Transitions, and Incomputability in the Wild, given at the Turing Centenary Workshop on the Incomputable at the Kavli Royal Society International Center at Chicheley Hall.
Message-Passing Algorithms for Network Analysis, given at an IPAM workshop on Mathematical Challenges in Graphical Models and Message-Passing Algorithms. Joint work with Lenka Zdeborova, Florent Krzakala, Xiaoran Yan, Yaojia Zhu, Aurelien Decelle, and Mark Newman.
Let the Physics Do the Work: Scattering Algorithms for High-Dimensional Geometry, given at the NASA Quantum Future Technologies conference. Joint work with Aaron Denney.
Continuous Methods in Computer Science, invited talk at LATIN 2010. I discuss two areas where continuous techniques arise in computer science: in the analysis of algorithms on random graphs, and in interior-point methods for convex optimization problems.
Bounds on the Quantum Satisfiability Threshold, joint work with Sergey Bravyi and Alex Russell. Proceedings of Innovations in Computer Science (ICS) 2010, and given at a Los Alamos workshop on Physics of Algorithms.
Approximating the Permanent with Nonabelian Determinants, joint work with Alex Russell. Given at a UC Berkeley Theory Seminar.
The Power of Choice in Social Networks, joint work with Raissa D'Souza and Paul Krapivsky, a talk given at a Santa Fe Institute workshop on Scaling in Biological and Social Networks.
Phase Transitions in Physics and Computer Science: A Tale of Two Cultures, a talk for a general scientific audience given at the European Conference on Complex Systems.
Proving Lower Bounds on Random Satisfiability Using the Second Moment Method at the SIAM Conference on Discrete Mathematics in Victoria, 2006, minisymposium on Random Constraint Satisfaction Problems: from Physics to Algorithms.
Fearful Symmetries: Factoring, Graph Isomorphism, and Quantum Computing, a more informal talk focusing on the role symmetry plays in physics, and comments on cultural differences between physics and computer science, given at ESA (European Symposium on Algorithms) 2005.