Calendar

A Fermi surface coupled to a scalar field can be described in a 1/N expansion by choosing the fermion-scalar Yukawa coupling to be random in the N-dimensional flavor space, but invariant under translations. We compute the conductivity of such a theory in two spatial dimensions for a critical scalar. We find a Drude contribution, and show that a previously proposed  mega^{-2/3} contribution to the optical conductivity at frequency mega has vanishing co-efficient. We also describe the influence of impurity scattering of the fermions, and find that while the self energy resembles a marginal Fermi liquid, the resistivity behaves like a Fermi liquid.  Arxiv references: 2203.04990, 2207.08841

For more information on how to join, please see: https://cmsa.fas.harvard.edu/quantum-matter-seminar/

The field of dynamic graph algorithms seeks to understand and compute statistics on real-world networks that undergo changes with time. Some of these networks could have up to millions of edge insertions and deletions per second. In light of these highly dynamic networks, we propose various scalable and accurate graph algorithms for a variety of problems. In this talk, I will discuss new algorithms for various graph problems in the batch-dynamic model in shared-memory architectures where updates to the graph arrive in multiple batches of one or more updates. I’ll also briefly discuss my work in other dynamic models such as distributed dynamic models where the communication topology of the network also changes with time (ITCS 2022). In these models, I will present efficient algorithms for graph problems including k-core decomposition, low out-degree orientation, matching, triangle counting, and coloring.

Specifically, in the batch-dynamic model where we are given a batch of B updates, I’ll discuss an efficient O(B log^2 n) amortized work and O(log^2 n log log n) depth algorithm that gives a (2+\epsilon)-approximation on the k-core decomposition after each batch of updates (SPAA 2022). We also obtain new batch-dynamic algorithms for matching, triangle counting, and coloring using techniques and data structures developed in our k-core decomposition algorithm. In addition to our theoretical results, we implemented and experimentally evaluated our k-core decomposition algorithm on a 30-core machine with two-way hyper-threading on 11 graphs of varying densities and sizes. Our experiments show improvements over state-of-the-art algorithms even on machines with only 4 cores (your standard laptop). I’ll conclude with a discussion of some open questions and potential future work that these lines of research inspire.

For more information, please see: https://cmsa.fas.harvard.edu/interdisciplinary-science-seminar/