@inproceedings{14179, abstract = {Self-supervised representation learning has shown remarkable success in a number of domains. A common practice is to perform data augmentation via hand-crafted transformations intended to leave the semantics of the data invariant. We seek to understand the empirical success of this approach from a theoretical perspective. We formulate the augmentation process as a latent variable model by postulating a partition of the latent representation into a content component, which is assumed invariant to augmentation, and a style component, which is allowed to change. Unlike prior work on disentanglement and independent component analysis, we allow for both nontrivial statistical and causal dependencies in the latent space. We study the identifiability of the latent representation based on pairs of views of the observations and prove sufficient conditions that allow us to identify the invariant content partition up to an invertible mapping in both generative and discriminative settings. We find numerical simulations with dependent latent variables are consistent with our theory. Lastly, we introduce Causal3DIdent, a dataset of high-dimensional, visually complex images with rich causal dependencies, which we use to study the effect of data augmentations performed in practice.}, author = {Kügelgen, Julius von and Sharma, Yash and Gresele, Luigi and Brendel, Wieland and Schölkopf, Bernhard and Besserve, Michel and Locatello, Francesco}, booktitle = {Advances in Neural Information Processing Systems}, isbn = {9781713845393}, location = {Virtual}, pages = {16451--16467}, title = {{Self-supervised learning with data augmentations provably isolates content from style}}, volume = {34}, year = {2021}, } @inproceedings{14180, abstract = {Modern neural network architectures can leverage large amounts of data to generalize well within the training distribution. However, they are less capable of systematic generalization to data drawn from unseen but related distributions, a feat that is hypothesized to require compositional reasoning and reuse of knowledge. In this work, we present Neural Interpreters, an architecture that factorizes inference in a self-attention network as a system of modules, which we call \emph{functions}. Inputs to the model are routed through a sequence of functions in a way that is end-to-end learned. The proposed architecture can flexibly compose computation along width and depth, and lends itself well to capacity extension after training. To demonstrate the versatility of Neural Interpreters, we evaluate it in two distinct settings: image classification and visual abstract reasoning on Raven Progressive Matrices. In the former, we show that Neural Interpreters perform on par with the vision transformer using fewer parameters, while being transferrable to a new task in a sample efficient manner. In the latter, we find that Neural Interpreters are competitive with respect to the state-of-the-art in terms of systematic generalization. }, author = {Rahaman, Nasim and Gondal, Muhammad Waleed and Joshi, Shruti and Gehler, Peter and Bengio, Yoshua and Locatello, Francesco and Schölkopf, Bernhard}, booktitle = {Advances in Neural Information Processing Systems}, isbn = {9781713845393}, location = {Virtual}, pages = {10985--10998}, title = {{Dynamic inference with neural interpreters}}, volume = {34}, year = {2021}, } @inproceedings{14181, abstract = {Variational Inference makes a trade-off between the capacity of the variational family and the tractability of finding an approximate posterior distribution. Instead, Boosting Variational Inference allows practitioners to obtain increasingly good posterior approximations by spending more compute. The main obstacle to widespread adoption of Boosting Variational Inference is the amount of resources necessary to improve over a strong Variational Inference baseline. In our work, we trace this limitation back to the global curvature of the KL-divergence. We characterize how the global curvature impacts time and memory consumption, address the problem with the notion of local curvature, and provide a novel approximate backtracking algorithm for estimating local curvature. We give new theoretical convergence rates for our algorithms and provide experimental validation on synthetic and real-world datasets.}, author = {Dresdner, Gideon and Shekhar, Saurav and Pedregosa, Fabian and Locatello, Francesco and Rätsch, Gunnar}, booktitle = {Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence}, location = {Montreal, Canada}, pages = {2337--2343}, publisher = {International Joint Conferences on Artificial Intelligence}, title = {{Boosting variational inference with locally adaptive step-sizes}}, doi = {10.24963/ijcai.2021/322}, year = {2021}, } @inproceedings{14182, abstract = {When machine learning systems meet real world applications, accuracy is only one of several requirements. In this paper, we assay a complementary perspective originating from the increasing availability of pre-trained and regularly improving state-of-the-art models. While new improved models develop at a fast pace, downstream tasks vary more slowly or stay constant. Assume that we have a large unlabelled data set for which we want to maintain accurate predictions. Whenever a new and presumably better ML models becomes available, we encounter two problems: (i) given a limited budget, which data points should be re-evaluated using the new model?; and (ii) if the new predictions differ from the current ones, should we update? Problem (i) is about compute cost, which matters for very large data sets and models. Problem (ii) is about maintaining consistency of the predictions, which can be highly relevant for downstream applications; our demand is to avoid negative flips, i.e., changing correct to incorrect predictions. In this paper, we formalize the Prediction Update Problem and present an efficient probabilistic approach as answer to the above questions. In extensive experiments on standard classification benchmark data sets, we show that our method outperforms alternative strategies along key metrics for backward-compatible prediction updates.}, author = {Träuble, Frederik and Kügelgen, Julius von and Kleindessner, Matthäus and Locatello, Francesco and Schölkopf, Bernhard and Gehler, Peter}, booktitle = {35th Conference on Neural Information Processing Systems}, isbn = {9781713845393}, location = {Virtual}, pages = {116--128}, title = {{Backward-compatible prediction updates: A probabilistic approach}}, volume = {34}, year = {2021}, } @unpublished{14221, abstract = {The world is structured in countless ways. It may be prudent to enforce corresponding structural properties to a learning algorithm's solution, such as incorporating prior beliefs, natural constraints, or causal structures. Doing so may translate to faster, more accurate, and more flexible models, which may directly relate to real-world impact. In this dissertation, we consider two different research areas that concern structuring a learning algorithm's solution: when the structure is known and when it has to be discovered.}, author = {Locatello, Francesco}, booktitle = {arXiv}, title = {{Enforcing and discovering structure in machine learning}}, doi = {10.48550/arXiv.2111.13693}, year = {2021}, } @article{9002, abstract = { We prove that, for the binary erasure channel (BEC), the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Our proof is based on the construction and analysis of binary polar codes with large kernels. When communicating reliably at rates within ε>0 of capacity, the code length n often scales as O(1/εμ), where the constant μ is called the scaling exponent. It is known that the optimal scaling exponent is μ=2, and it is achieved by random linear codes. The scaling exponent of conventional polar codes (based on the 2×2 kernel) on the BEC is μ=3.63. This falls far short of the optimal scaling guaranteed by random codes. Our main contribution is a rigorous proof of the following result: for the BEC, there exist ℓ×ℓ binary kernels, such that polar codes constructed from these kernels achieve scaling exponent μ(ℓ) that tends to the optimal value of 2 as ℓ grows. We furthermore characterize precisely how large ℓ needs to be as a function of the gap between μ(ℓ) and 2. The resulting binary codes maintain the recursive structure of conventional polar codes, and thereby achieve construction complexity O(n) and encoding/decoding complexity O(nlogn).}, author = {Fazeli, Arman and Hassani, Hamed and Mondelli, Marco and Vardy, Alexander}, issn = {1557-9654}, journal = {IEEE Transactions on Information Theory}, number = {9}, pages = {5693--5710}, publisher = {IEEE}, title = {{Binary linear codes with optimal scaling: Polar codes with large kernels}}, doi = {10.1109/TIT.2020.3038806}, volume = {67}, year = {2021}, } @article{9005, abstract = {Studies on the experimental realization of two-dimensional anyons in terms of quasiparticles have been restricted, so far, to only anyons on the plane. It is known, however, that the geometry and topology of space can have significant effects on quantum statistics for particles moving on it. Here, we have undertaken the first step toward realizing the emerging fractional statistics for particles restricted to move on the sphere instead of on the plane. We show that such a model arises naturally in the context of quantum impurity problems. In particular, we demonstrate a setup in which the lowest-energy spectrum of two linear bosonic or fermionic molecules immersed in a quantum many-particle environment can coincide with the anyonic spectrum on the sphere. This paves the way toward the experimental realization of anyons on the sphere using molecular impurities. Furthermore, since a change in the alignment of the molecules corresponds to the exchange of the particles on the sphere, such a realization reveals a novel type of exclusion principle for molecular impurities, which could also be of use as a powerful technique to measure the statistics parameter. Finally, our approach opens up a simple numerical route to investigate the spectra of many anyons on the sphere. Accordingly, we present the spectrum of two anyons on the sphere in the presence of a Dirac monopole field.}, author = {Brooks, Morris and Lemeshko, Mikhail and Lundholm, D. and Yakaboylu, Enderalp}, issn = {10797114}, journal = {Physical Review Letters}, number = {1}, publisher = {American Physical Society}, title = {{Molecular impurities as a realization of anyons on the two-sphere}}, doi = {10.1103/PhysRevLett.126.015301}, volume = {126}, year = {2021}, } @article{9006, abstract = {Cytoplasm is a gel-like crowded environment composed of various macromolecules, organelles, cytoskeletal networks, and cytosol. The structure of the cytoplasm is highly organized and heterogeneous due to the crowding of its constituents and their effective compartmentalization. In such an environment, the diffusive dynamics of the molecules are restricted, an effect that is further amplified by clustering and anchoring of molecules. Despite the crowded nature of the cytoplasm at the microscopic scale, large-scale reorganization of the cytoplasm is essential for important cellular functions, such as cell division and polarization. How such mesoscale reorganization of the cytoplasm is achieved, especially for large cells such as oocytes or syncytial tissues that can span hundreds of micrometers in size, is only beginning to be understood. In this review, we will discuss recent advances in elucidating the molecular, cellular, and biophysical mechanisms by which the cytoskeleton drives cytoplasmic reorganization across different scales, structures, and species.}, author = {Shamipour, Shayan and Caballero Mancebo, Silvia and Heisenberg, Carl-Philipp J}, issn = {18781551}, journal = {Developmental Cell}, number = {2}, pages = {P213--226}, publisher = {Elsevier}, title = {{Cytoplasm's got moves}}, doi = {10.1016/j.devcel.2020.12.002}, volume = {56}, year = {2021}, } @article{9009, abstract = {Recent advancements in live cell imaging technologies have identified the phenomenon of intracellular propagation of late apoptotic events, such as cytochrome c release and caspase activation. The mechanism, prevalence, and speed of apoptosis propagation remain unclear. Additionally, no studies have demonstrated propagation of the pro-apoptotic protein, BAX. To evaluate the role of BAX in intracellular apoptotic propagation, we used high speed live-cell imaging to visualize fluorescently tagged-BAX recruitment to mitochondria in four immortalized cell lines. We show that propagation of mitochondrial BAX recruitment occurs in parallel to cytochrome c and SMAC/Diablo release and is affected by cellular morphology, such that cells with processes are more likely to exhibit propagation. The initiation of propagation events is most prevalent in the distal tips of processes, while the rate of propagation is influenced by the 2-dimensional width of the process. Propagation was rarely observed in the cell soma, which exhibited near synchronous recruitment of BAX. Propagation velocity is not affected by mitochondrial volume in segments of processes, but is negatively affected by mitochondrial density. There was no evidence of a propagating wave of increased levels of intracellular calcium ions. Alternatively, we did observe a uniform increase in superoxide build-up in cellular mitochondria, which was released as a propagating wave simultaneously with the propagating recruitment of BAX to the mitochondrial outer membrane.}, author = {Grosser, Joshua A. and Maes, Margaret E and Nickells, Robert W.}, issn = {1573-675X}, journal = {Apoptosis}, number = {2}, pages = {132--145}, publisher = {Springer Nature}, title = {{Characteristics of intracellular propagation of mitochondrial BAX recruitment during apoptosis}}, doi = {10.1007/s10495-020-01654-w}, volume = {26}, year = {2021}, } @article{9010, abstract = {Availability of the essential macronutrient nitrogen in soil plays a critical role in plant growth, development, and impacts agricultural productivity. Plants have evolved different strategies for sensing and responding to heterogeneous nitrogen distribution. Modulation of root system architecture, including primary root growth and branching, is among the most essential plant adaptions to ensure adequate nitrogen acquisition. However, the immediate molecular pathways coordinating the adjustment of root growth in response to distinct nitrogen sources, such as nitrate or ammonium, are poorly understood. Here, we show that growth as manifested by cell division and elongation is synchronized by coordinated auxin flux between two adjacent outer tissue layers of the root. This coordination is achieved by nitrate‐dependent dephosphorylation of the PIN2 auxin efflux carrier at a previously uncharacterized phosphorylation site, leading to subsequent PIN2 lateralization and thereby regulating auxin flow between adjacent tissues. A dynamic computer model based on our experimental data successfully recapitulates experimental observations. Our study provides mechanistic insights broadening our understanding of root growth mechanisms in dynamic environments.}, author = {Ötvös, Krisztina and Marconi, Marco and Vega, Andrea and O’Brien, Jose and Johnson, Alexander J and Abualia, Rashed and Antonielli, Livio and Montesinos López, Juan C and Zhang, Yuzhou and Tan, Shutang and Cuesta, Candela and Artner, Christina and Bouguyon, Eleonore and Gojon, Alain and Friml, Jiří and Gutiérrez, Rodrigo A. and Wabnik, Krzysztof T and Benková, Eva}, issn = {14602075}, journal = {EMBO Journal}, number = {3}, publisher = {Embo Press}, title = {{Modulation of plant root growth by nitrogen source-defined regulation of polar auxin transport}}, doi = {10.15252/embj.2020106862}, volume = {40}, year = {2021}, } @article{9020, abstract = {We study dynamics and thermodynamics of ion transport in narrow, water-filled channels, considered as effective 1D Coulomb systems. The long range nature of the inter-ion interactions comes about due to the dielectric constants mismatch between the water and the surrounding medium, confining the electric filed to stay mostly within the water-filled channel. Statistical mechanics of such Coulomb systems is dominated by entropic effects which may be accurately accounted for by mapping onto an effective quantum mechanics. In presence of multivalent ions the corresponding quantum mechanics appears to be non-Hermitian. In this review we discuss a framework for semiclassical calculations for the effective non-Hermitian Hamiltonians. Non-Hermiticity elevates WKB action integrals from the real line to closed cycles on a complex Riemann surfaces where direct calculations are not attainable. We circumvent this issue by applying tools from algebraic topology, such as the Picard-Fuchs equation. We discuss how its solutions relate to the thermodynamics and correlation functions of multivalent solutions within narrow, water-filled channels. }, author = {Gulden, Tobias and Kamenev, Alex}, issn = {1099-4300}, journal = {Entropy}, number = {1}, publisher = {MDPI}, title = {{Dynamics of ion channels via non-hermitian quantum mechanics}}, doi = {10.3390/e23010125}, volume = {23}, year = {2021}, } @phdthesis{9022, abstract = {In the first part of the thesis we consider Hermitian random matrices. Firstly, we consider sample covariance matrices XX∗ with X having independent identically distributed (i.i.d.) centred entries. We prove a Central Limit Theorem for differences of linear statistics of XX∗ and its minor after removing the first column of X. Secondly, we consider Wigner-type matrices and prove that the eigenvalue statistics near cusp singularities of the limiting density of states are universal and that they form a Pearcey process. Since the limiting eigenvalue distribution admits only square root (edge) and cubic root (cusp) singularities, this concludes the third and last remaining case of the Wigner-Dyson-Mehta universality conjecture. The main technical ingredients are an optimal local law at the cusp, and the proof of the fast relaxation to equilibrium of the Dyson Brownian motion in the cusp regime. In the second part we consider non-Hermitian matrices X with centred i.i.d. entries. We normalise the entries of X to have variance N −1. It is well known that the empirical eigenvalue density converges to the uniform distribution on the unit disk (circular law). In the first project, we prove universality of the local eigenvalue statistics close to the edge of the spectrum. This is the non-Hermitian analogue of the TracyWidom universality at the Hermitian edge. Technically we analyse the evolution of the spectral distribution of X along the Ornstein-Uhlenbeck flow for very long time (up to t = +∞). In the second project, we consider linear statistics of eigenvalues for macroscopic test functions f in the Sobolev space H2+ϵ and prove their convergence to the projection of the Gaussian Free Field on the unit disk. We prove this result for non-Hermitian matrices with real or complex entries. The main technical ingredients are: (i) local law for products of two resolvents at different spectral parameters, (ii) analysis of correlated Dyson Brownian motions. In the third and final part we discuss the mathematically rigorous application of supersymmetric techniques (SUSY ) to give a lower tail estimate of the lowest singular value of X − z, with z ∈ C. More precisely, we use superbosonisation formula to give an integral representation of the resolvent of (X − z)(X − z)∗ which reduces to two and three contour integrals in the complex and real case, respectively. The rigorous analysis of these integrals is quite challenging since simple saddle point analysis cannot be applied (the main contribution comes from a non-trivial manifold). Our result improves classical smoothing inequalities in the regime |z| ≈ 1; this result is essential to prove edge universality for i.i.d. non-Hermitian matrices.}, author = {Cipolloni, Giorgio}, issn = {2663-337X}, pages = {380}, publisher = {Institute of Science and Technology Austria}, title = {{Fluctuations in the spectrum of random matrices}}, doi = {10.15479/AT:ISTA:9022}, year = {2021}, } @article{9036, abstract = {In this short note, we prove that the square root of the quantum Jensen-Shannon divergence is a true metric on the cone of positive matrices, and hence in particular on the quantum state space.}, author = {Virosztek, Daniel}, issn = {0001-8708}, journal = {Advances in Mathematics}, keywords = {General Mathematics}, number = {3}, publisher = {Elsevier}, title = {{The metric property of the quantum Jensen-Shannon divergence}}, doi = {10.1016/j.aim.2021.107595}, volume = {380}, year = {2021}, } @article{9037, abstract = {We continue our study of ‘no‐dimension’ analogues of basic theorems in combinatorial and convex geometry in Banach spaces. We generalize some results of the paper (Adiprasito, Bárány and Mustafa, ‘Theorems of Carathéodory, Helly, and Tverberg without dimension’, Proceedings of the Thirtieth Annual ACM‐SIAM Symposium on Discrete Algorithms (Society for Industrial and Applied Mathematics, San Diego, California, 2019) 2350–2360) and prove no‐dimension versions of the colored Tverberg theorem, the selection lemma and the weak 𝜀 ‐net theorem in Banach spaces of type 𝑝>1 . To prove these results, we use the original ideas of Adiprasito, Bárány and Mustafa for the Euclidean case, our no‐dimension version of the Radon theorem and slightly modified version of the celebrated Maurey lemma.}, author = {Ivanov, Grigory}, issn = {14692120}, journal = {Bulletin of the London Mathematical Society}, number = {2}, pages = {631--641}, publisher = {London Mathematical Society}, title = {{No-dimension Tverberg's theorem and its corollaries in Banach spaces of type p}}, doi = {10.1112/blms.12449}, volume = {53}, year = {2021}, } @article{9046, author = {Römhild, Roderich and Andersson, Dan I.}, issn = {15537374}, journal = {PLoS Pathogens}, number = {1}, publisher = {Public Library of Science}, title = {{Mechanisms and therapeutic potential of collateral sensitivity to antibiotics}}, doi = {10.1371/journal.ppat.1009172}, volume = {17}, year = {2021}, } @article{9047, abstract = {This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N1−1/μ) , where N is the block length and μ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 or 1.}, author = {Mondelli, Marco and Hashemi, Seyyed Ali and Cioffi, John M. and Goldsmith, Andrea}, issn = {15582248}, journal = {IEEE Transactions on Wireless Communications}, number = {1}, pages = {18--27}, publisher = {IEEE}, title = {{Sublinear latency for simplified successive cancellation decoding of polar codes}}, doi = {10.1109/TWC.2020.3022922}, volume = {20}, year = {2021}, } @article{9048, abstract = {The analogy between an equilibrium partition function and the return probability in many-body unitary dynamics has led to the concept of dynamical quantum phase transition (DQPT). DQPTs are defined by nonanalyticities in the return amplitude and are present in many models. In some cases, DQPTs can be related to equilibrium concepts, such as order parameters, yet their universal description is an open question. In this Letter, we provide first steps toward a classification of DQPTs by using a matrix product state description of unitary dynamics in the thermodynamic limit. This allows us to distinguish the two limiting cases of “precession” and “entanglement” DQPTs, which are illustrated using an analytical description in the quantum Ising model. While precession DQPTs are characterized by a large entanglement gap and are semiclassical in their nature, entanglement DQPTs occur near avoided crossings in the entanglement spectrum and can be distinguished by a complex pattern of nonlocal correlations. We demonstrate the existence of precession and entanglement DQPTs beyond Ising models, discuss observables that can distinguish them, and relate their interplay to complex DQPT phenomenology.}, author = {De Nicola, Stefano and Michailidis, Alexios and Serbyn, Maksym}, issn = {1079-7114}, journal = {Physical Review Letters}, keywords = {General Physics and Astronomy}, number = {4}, publisher = {American Physical Society}, title = {{Entanglement view of dynamical quantum phase transitions}}, doi = {10.1103/physrevlett.126.040602}, volume = {126}, year = {2021}, } @phdthesis{9056, abstract = {In this thesis we study persistence of multi-covers of Euclidean balls and the geometric structures underlying their computation, in particular Delaunay mosaics and Voronoi tessellations. The k-fold cover for some discrete input point set consists of the space where at least k balls of radius r around the input points overlap. Persistence is a notion that captures, in some sense, the topology of the shape underlying the input. While persistence is usually computed for the union of balls, the k-fold cover is of interest as it captures local density, and thus might approximate the shape of the input better if the input data is noisy. To compute persistence of these k-fold covers, we need a discretization that is provided by higher-order Delaunay mosaics. We present and implement a simple and efficient algorithm for the computation of higher-order Delaunay mosaics, and use it to give experimental results for their combinatorial properties. The algorithm makes use of a new geometric structure, the rhomboid tiling. It contains the higher-order Delaunay mosaics as slices, and by introducing a filtration function on the tiling, we also obtain higher-order α-shapes as slices. These allow us to compute persistence of the multi-covers for varying radius r; the computation for varying k is less straight-foward and involves the rhomboid tiling directly. We apply our algorithms to experimental sphere packings to shed light on their structural properties. Finally, inspired by periodic structures in packings and materials, we propose and implement an algorithm for periodic Delaunay triangulations to be integrated into the Computational Geometry Algorithms Library (CGAL), and discuss the implications on persistence for periodic data sets.}, author = {Osang, Georg F}, issn = {2663-337X}, pages = {134}, publisher = {Institute of Science and Technology Austria}, title = {{Multi-cover persistence and Delaunay mosaics}}, doi = {10.15479/AT:ISTA:9056}, year = {2021}, } @article{9073, abstract = {The sensory and cognitive abilities of the mammalian neocortex are underpinned by intricate columnar and laminar circuits formed from an array of diverse neuronal populations. One approach to determining how interactions between these circuit components give rise to complex behavior is to investigate the rules by which cortical circuits are formed and acquire functionality during development. This review summarizes recent research on the development of the neocortex, from genetic determination in neural stem cells through to the dynamic role that specific neuronal populations play in the earliest circuits of neocortex, and how they contribute to emergent function and cognition. While many of these endeavors take advantage of model systems, consideration will also be given to advances in our understanding of activity in nascent human circuits. Such cross-species perspective is imperative when investigating the mechanisms underlying the dysfunction of early neocortical circuits in neurodevelopmental disorders, so that one can identify targets amenable to therapeutic intervention.}, author = {Hanganu-Opatz, Ileana L. and Butt, Simon J. B. and Hippenmeyer, Simon and De Marco García, Natalia V. and Cardin, Jessica A. and Voytek, Bradley and Muotri, Alysson R.}, issn = {1529-2401}, journal = {The Journal of Neuroscience}, keywords = {General Neuroscience}, number = {5}, pages = {813--822}, publisher = {Society for Neuroscience}, title = {{The logic of developing neocortical circuits in health and disease}}, doi = {10.1523/jneurosci.1655-20.2020}, volume = {41}, year = {2021}, } @unpublished{9082, abstract = {Acquired mutations are sufficiently frequent such that the genome of a single cell offers a record of its history of cell divisions. Among more common somatic genomic alterations are loss of heterozygosity (LOH). Large LOH events are potentially detectable in single cell RNA sequencing (scRNA-seq) datasets as tracts of monoallelic expression for constitutionally heterozygous single nucleotide variants (SNVs) located among contiguous genes. We identified runs of monoallelic expression, consistent with LOH, uniquely distributed throughout the genome in single cell brain cortex transcriptomes of F1 hybrids involving different inbred mouse strains. We then phylogenetically reconstructed single cell lineages and simultaneously identified cell types by corresponding gene expression patterns. Our results are consistent with progenitor cells giving rise to multiple cortical cell types through stereotyped expansion and distinct waves of neurogenesis. Compared to engineered recording systems, LOH events accumulate throughout the genome and across the lifetime of an organism, affording tremendous capacity for encoding lineage information and increasing resolution for later cell divisions. This approach can conceivably be computationally incorporated into scRNA-seq analysis and may be useful for organisms where genetic engineering is prohibitive, such as humans.}, author = {Anderson, Donovan J. and Pauler, Florian and McKenna, Aaron and Shendure, Jay and Hippenmeyer, Simon and Horwitz, Marshall S.}, booktitle = {bioRxiv}, publisher = {Cold Spring Harbor Laboratory}, title = {{Simultaneous identification of brain cell type and lineage via single cell RNA sequencing}}, doi = {10.1101/2020.12.31.425016}, year = {2021}, }