@article{10860, abstract = {A tight frame is the orthogonal projection of some orthonormal basis of Rn onto Rk. We show that a set of vectors is a tight frame if and only if the set of all cross products of these vectors is a tight frame. We reformulate a range of problems on the volume of projections (or sections) of regular polytopes in terms of tight frames and write a first-order necessary condition for local extrema of these problems. As applications, we prove new results for the problem of maximization of the volume of zonotopes.}, author = {Ivanov, Grigory}, issn = {1496-4287}, journal = {Canadian Mathematical Bulletin}, keywords = {General Mathematics, Tight frame, Grassmannian, zonotope}, number = {4}, pages = {942--963}, publisher = {Canadian Mathematical Society}, title = {{Tight frames and related geometric problems}}, doi = {10.4153/s000843952000096x}, volume = {64}, year = {2021}, } @unpublished{10912, abstract = {Brain dynamics display collective phenomena as diverse as neuronal oscillations and avalanches. Oscillations are rhythmic, with fluctuations occurring at a characteristic scale, whereas avalanches are scale-free cascades of neural activity. Here we show that such antithetic features can coexist in a very generic class of adaptive neural networks. In the most simple yet fully microscopic model from this class we make direct contact with human brain resting-state activity recordings via tractable inference of the model's two essential parameters. The inferred model quantitatively captures the dynamics over a broad range of scales, from single sensor fluctuations, collective behaviors of nearly-synchronous extreme events on multiple sensors, to neuronal avalanches unfolding over multiple sensors across multiple time-bins. Importantly, the inferred parameters correlate with model-independent signatures of "closeness to criticality", suggesting that the coexistence of scale-specific (neural oscillations) and scale-free (neuronal avalanches) dynamics in brain activity occurs close to a non-equilibrium critical point at the onset of self-sustained oscillations.}, author = {Lombardi, Fabrizio and Pepic, Selver and Shriki, Oren and Tkačik, Gašper and De Martino, Daniele}, pages = {37}, publisher = {arXiv}, title = {{Quantifying the coexistence of neuronal oscillations and avalanches}}, doi = {10.48550/ARXIV.2108.06686}, year = {2021}, } @article{11052, abstract = {In order to combat molecular damage, most cellular proteins undergo rapid turnover. We have previously identified large nuclear protein assemblies that can persist for years in post-mitotic tissues and are subject to age-related decline. Here, we report that mitochondria can be long lived in the mouse brain and reveal that specific mitochondrial proteins have half-lives longer than the average proteome. These mitochondrial long-lived proteins (mitoLLPs) are core components of the electron transport chain (ETC) and display increased longevity in respiratory supercomplexes. We find that COX7C, a mitoLLP that forms a stable contact site between complexes I and IV, is required for complex IV and supercomplex assembly. Remarkably, even upon depletion of COX7C transcripts, ETC function is maintained for days, effectively uncoupling mitochondrial function from ongoing transcription of its mitoLLPs. Our results suggest that modulating protein longevity within the ETC is critical for mitochondrial proteome maintenance and the robustness of mitochondrial function.}, author = {Krishna, Shefali and Arrojo e Drigo, Rafael and Capitanio, Juliana S. and Ramachandra, Ranjan and Ellisman, Mark and HETZER, Martin W}, issn = {1534-5807}, journal = {Developmental Cell}, keywords = {Developmental Biology, Cell Biology, General Biochemistry, Genetics and Molecular Biology, Molecular Biology}, number = {21}, pages = {P2952--2965.e9}, publisher = {Elsevier}, title = {{Identification of long-lived proteins in the mitochondria reveals increased stability of the electron transport chain}}, doi = {10.1016/j.devcel.2021.10.008}, volume = {56}, year = {2021}, } @article{11053, abstract = {Understanding basic mechanisms of aging holds great promise for developing interventions that prevent or delay many age-related declines and diseases simultaneously to increase human healthspan. However, a major confounding factor in aging research is the heterogeneity of the aging process itself. At the organismal level, it is clear that chronological age does not always predict biological age or susceptibility to frailty or pathology. While genetics and environment are major factors driving variable rates of aging, additional complexity arises because different organs, tissues, and cell types are intrinsically heterogeneous and exhibit different aging trajectories normally or in response to the stresses of the aging process (e.g., damage accumulation). Tackling the heterogeneity of aging requires new and specialized tools (e.g., single-cell analyses, mass spectrometry-based approaches, and advanced imaging) to identify novel signatures of aging across scales. Cutting-edge computational approaches are then needed to integrate these disparate datasets and elucidate network interactions between known aging hallmarks. There is also a need for improved, human cell-based models of aging to ensure that basic research findings are relevant to human aging and healthspan interventions. The San Diego Nathan Shock Center (SD-NSC) provides access to cutting-edge scientific resources to facilitate the study of the heterogeneity of aging in general and to promote the use of novel human cell models of aging. The center also has a robust Research Development Core that funds pilot projects on the heterogeneity of aging and organizes innovative training activities, including workshops and a personalized mentoring program, to help investigators new to the aging field succeed. Finally, the SD-NSC participates in outreach activities to educate the general community about the importance of aging research and promote the need for basic biology of aging research in particular.}, author = {Shadel, Gerald S. and Adams, Peter D. and Berggren, W. Travis and Diedrich, Jolene K. and Diffenderfer, Kenneth E. and Gage, Fred H. and Hah, Nasun and Hansen, Malene and HETZER, Martin W and Molina, Anthony J. A. and Manor, Uri and Marek, Kurt and O’Keefe, David D. and Pinto, Antonio F. M. and Sacco, Alessandra and Sharpee, Tatyana O. and Shokriev, Maxim N. and Zambetti, Stefania}, issn = {2509-2715}, journal = {GeroScience}, keywords = {Geriatrics and Gerontology, Aging}, number = {5}, pages = {2139--2148}, publisher = {Springer Nature}, title = {{The San Diego Nathan Shock Center: Tackling the heterogeneity of aging}}, doi = {10.1007/s11357-021-00426-x}, volume = {43}, year = {2021}, } @inproceedings{11436, abstract = {Asynchronous distributed algorithms are a popular way to reduce synchronization costs in large-scale optimization, and in particular for neural network training. However, for nonsmooth and nonconvex objectives, few convergence guarantees exist beyond cases where closed-form proximal operator solutions are available. As training most popular deep neural networks corresponds to optimizing nonsmooth and nonconvex objectives, there is a pressing need for such convergence guarantees. In this paper, we analyze for the first time the convergence of stochastic asynchronous optimization for this general class of objectives. In particular, we focus on stochastic subgradient methods allowing for block variable partitioning, where the shared model is asynchronously updated by concurrent processes. To this end, we use a probabilistic model which captures key features of real asynchronous scheduling between concurrent processes. Under this model, we establish convergence with probability one to an invariant set for stochastic subgradient methods with momentum. From a practical perspective, one issue with the family of algorithms that we consider is that they are not efficiently supported by machine learning frameworks, which mostly focus on distributed data-parallel strategies. To address this, we propose a new implementation strategy for shared-memory based training of deep neural networks for a partitioned but shared model in single- and multi-GPU settings. Based on this implementation, we achieve on average1.2x speed-up in comparison to state-of-the-art training methods for popular image classification tasks, without compromising accuracy.}, author = {Kungurtsev, Vyacheslav and Egan, Malcolm and Chatterjee, Bapi and Alistarh, Dan-Adrian}, booktitle = {35th AAAI Conference on Artificial Intelligence, AAAI 2021}, isbn = {9781713835974}, issn = {2374-3468}, location = {Virtual, Online}, number = {9B}, pages = {8209--8216}, publisher = {AAAI Press}, title = {{Asynchronous optimization methods for efficient training of deep neural networks with guarantees}}, volume = {35}, year = {2021}, } @article{10000, abstract = {Inhibition or targeted deletion of histone deacetylase 3 (HDAC3) is neuroprotective in a variety neurodegenerative conditions, including retinal ganglion cells (RGCs) after acute optic nerve damage. Consistent with this, induced HDAC3 expression in cultured cells shows selective toxicity to neurons. Despite an established role for HDAC3 in neuronal pathology, little is known regarding the mechanism of this pathology.}, author = {Schmitt, Heather M. and Fehrman, Rachel L. and Maes, Margaret E and Yang, Huan and Guo, Lian Wang and Schlamp, Cassandra L. and Pelzel, Heather R. and Nickells, Robert W.}, issn = {1552-5783}, journal = {Investigative Ophthalmology and Visual Science}, number = {10}, publisher = {Association for Research in Vision and Ophthalmology}, title = {{Increased susceptibility and intrinsic apoptotic signaling in neurons by induced HDAC3 expression}}, doi = {10.1167/IOVS.62.10.14}, volume = {62}, year = {2021}, } @inproceedings{10002, abstract = {We present a faster symbolic algorithm for the following central problem in probabilistic verification: Compute the maximal end-component (MEC) decomposition of Markov decision processes (MDPs). This problem generalizes the SCC decomposition problem of graphs and closed recurrent sets of Markov chains. The model of symbolic algorithms is widely used in formal verification and model-checking, where access to the input model is restricted to only symbolic operations (e.g., basic set operations and computation of one-step neighborhood). For an input MDP with n vertices and m edges, the classical symbolic algorithm from the 1990s for the MEC decomposition requires O(n2) symbolic operations and O(1) symbolic space. The only other symbolic algorithm for the MEC decomposition requires O(nm−−√) symbolic operations and O(m−−√) symbolic space. A main open question is whether the worst-case O(n2) bound for symbolic operations can be beaten. We present a symbolic algorithm that requires O˜(n1.5) symbolic operations and O˜(n−−√) symbolic space. Moreover, the parametrization of our algorithm provides a trade-off between symbolic operations and symbolic space: for all 0<ϵ≤1/2 the symbolic algorithm requires O˜(n2−ϵ) symbolic operations and O˜(nϵ) symbolic space ( O˜ hides poly-logarithmic factors). Using our techniques we present faster algorithms for computing the almost-sure winning regions of ω -regular objectives for MDPs. We consider the canonical parity objectives for ω -regular objectives, and for parity objectives with d -priorities we present an algorithm that computes the almost-sure winning region with O˜(n2−ϵ) symbolic operations and O˜(nϵ) symbolic space, for all 0<ϵ≤1/2 .}, author = {Chatterjee, Krishnendu and Dvorak, Wolfgang and Henzinger, Monika H and Svozil, Alexander}, booktitle = {Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science}, isbn = {978-1-6654-4896-3}, issn = {1043-6871}, keywords = {Computer science, Computational modeling, Markov processes, Probabilistic logic, Formal verification, Game Theory}, location = {Rome, Italy}, pages = {1--13}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Symbolic time and space tradeoffs for probabilistic verification}}, doi = {10.1109/LICS52264.2021.9470739}, year = {2021}, } @inproceedings{10004, abstract = {Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs.}, author = {Chatterjee, Krishnendu and Doyen, Laurent}, booktitle = {Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science}, isbn = {978-1-6654-4896-3}, issn = {1043-6871}, keywords = {Computer science, Heuristic algorithms, Memory management, Automata, Markov processes, Probability distribution, Complexity theory}, location = {Rome, Italy}, pages = {1--13}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Stochastic processes with expected stopping time}}, doi = {10.1109/LICS52264.2021.9470595}, year = {2021}, } @article{10005, abstract = {We study systems of nonlinear partial differential equations of parabolic type, in which the elliptic operator is replaced by the first-order divergence operator acting on a flux function, which is related to the spatial gradient of the unknown through an additional implicit equation. This setting, broad enough in terms of applications, significantly expands the paradigm of nonlinear parabolic problems. Formulating four conditions concerning the form of the implicit equation, we first show that these conditions describe a maximal monotone p-coercive graph. We then establish the global-in-time and large-data existence of a (weak) solution and its uniqueness. To this end, we adopt and significantly generalize Minty’s method of monotone mappings. A unified theory, containing several novel tools, is developed in a way to be tractable from the point of view of numerical approximations.}, author = {Bulíček, Miroslav and Maringová, Erika and Málek, Josef}, issn = {1793-6314}, journal = {Mathematical Models and Methods in Applied Sciences}, keywords = {Nonlinear parabolic systems, implicit constitutive theory, weak solutions, existence, uniqueness}, number = {09}, publisher = {World Scientific Publishing}, title = {{On nonlinear problems of parabolic type with implicit constitutive equations involving flux}}, doi = {10.1142/S0218202521500457}, volume = {31}, year = {2021}, } @article{10023, abstract = {We study the temporal dissipation of variance and relative entropy for ergodic Markov Chains in continuous time, and compute explicitly the corresponding dissipation rates. These are identified, as is well known, in the case of the variance in terms of an appropriate Hilbertian norm; and in the case of the relative entropy, in terms of a Dirichlet form which morphs into a version of the familiar Fisher information under conditions of detailed balance. Here we obtain trajectorial versions of these results, valid along almost every path of the random motion and most transparent in the backwards direction of time. Martingale arguments and time reversal play crucial roles, as in the recent work of Karatzas, Schachermayer and Tschiderer for conservative diffusions. Extensions are developed to general “convex divergences” and to countable state-spaces. The steepest descent and gradient flow properties for the variance, the relative entropy, and appropriate generalizations, are studied along with their respective geometries under conditions of detailed balance, leading to a very direct proof for the HWI inequality of Otto and Villani in the present context.}, author = {Karatzas, Ioannis and Maas, Jan and Schachermayer, Walter}, issn = {1526-7555}, journal = {Communications in Information and Systems}, keywords = {Markov Chain, relative entropy, time reversal, steepest descent, gradient flow}, number = {4}, pages = {481--536}, publisher = {International Press}, title = {{Trajectorial dissipation and gradient flow for the relative entropy in Markov chains}}, doi = {10.4310/CIS.2021.v21.n4.a1}, volume = {21}, year = {2021}, } @article{10024, abstract = {In this paper, we introduce a random environment for the exclusion process in obtained by assigning a maximal occupancy to each site. This maximal occupancy is allowed to randomly vary among sites, and partial exclusion occurs. Under the assumption of ergodicity under translation and uniform ellipticity of the environment, we derive a quenched hydrodynamic limit in path space by strengthening the mild solution approach initiated in Nagy (2002) and Faggionato (2007). To this purpose, we prove, employing the technology developed for the random conductance model, a homogenization result in the form of an arbitrary starting point quenched invariance principle for a single particle in the same environment, which is a result of independent interest. The self-duality property of the partial exclusion process allows us to transfer this homogenization result to the particle system and, then, apply the tightness criterion in Redig et al. (2020).}, author = {Floreani, Simone and Redig, Frank and Sau, Federico}, issn = {0304-4149}, journal = {Stochastic Processes and their Applications}, keywords = {hydrodynamic limit, random environment, random conductance model, arbitrary starting point quenched invariance principle, duality, mild solution}, pages = {124--158}, publisher = {Elsevier}, title = {{Hydrodynamics for the partial exclusion process in random environment}}, doi = {10.1016/j.spa.2021.08.006}, volume = {142}, year = {2021}, } @article{10025, abstract = {Ferromagnetism is most common in transition metal compounds but may also arise in low-density two-dimensional electron systems, with signatures observed in silicon, III-V semiconductor systems, and graphene moiré heterostructures. Here we show that gate-tuned van Hove singularities in rhombohedral trilayer graphene drive the spontaneous ferromagnetic polarization of the electron system into one or more spin- and valley flavors. Using capacitance measurements on graphite-gated van der Waals heterostructures, we find a cascade of density- and electronic displacement field tuned phase transitions marked by negative electronic compressibility. The transitions define the boundaries between phases where quantum oscillations have either four-fold, two-fold, or one-fold degeneracy, associated with a spin and valley degenerate normal metal, spin-polarized `half-metal', and spin and valley polarized `quarter metal', respectively. For electron doping, the salient features are well captured by a phenomenological Stoner model with a valley-anisotropic Hund's coupling, likely arising from interactions at the lattice scale. For hole filling, we observe a richer phase diagram featuring a delicate interplay of broken symmetries and transitions in the Fermi surface topology. Finally, by rotational alignment of a hexagonal boron nitride substrate to induce a moiré superlattice, we find that the superlattice perturbs the preexisting isospin order only weakly, leaving the basic phase diagram intact while catalyzing the formation of topologically nontrivial gapped states whenever itinerant half- or quarter metal states occur at half- or quarter superlattice band filling. Our results show that rhombohedral trilayer graphene is an ideal platform for well-controlled tests of many-body theory and reveal magnetism in moiré materials to be fundamentally itinerant in nature.}, author = {Zhou, Haoxin and Xie, Tian and Ghazaryan, Areg and Holder, Tobias and Ehrets, James R. and Spanton, Eric M. and Taniguchi, Takashi and Watanabe, Kenji and Berg, Erez and Serbyn, Maksym and Young, Andrea F.}, issn = {1476-4687}, journal = {Nature}, keywords = {condensed matter - mesoscale and nanoscale physics, condensed matter - strongly correlated electrons, multidisciplinary}, publisher = {Springer Nature}, title = {{Half and quarter metals in rhombohedral trilayer graphene}}, doi = {10.1038/s41586-021-03938-w}, year = {2021}, } @unpublished{10029, abstract = {Superconductor-semiconductor hybrids are platforms for realizing effective p-wave superconductivity. Spin-orbit coupling, combined with the proximity effect, causes the two-dimensional semiconductor to inherit p±ip intraband pairing, and application of magnetic field can then result in transitions to the normal state, partial Bogoliubov Fermi surfaces, or topological phases with Majorana modes. Experimentally probing the hybrid superconductor-semiconductor interface is challenging due to the shunting effect of the conventional superconductor. Consequently, the nature of induced pairing remains an open question. Here, we use the circuit quantum electrodynamics architecture to probe induced superconductivity in a two dimensional Al-InAs hybrid system. We observe a strong suppression of superfluid density and enhanced dissipation driven by magnetic field, which cannot be accounted for by the depairing theory of an s-wave superconductor. These observations are explained by a picture of independent intraband p±ip superconductors giving way to partial Bogoliubov Fermi surfaces, and allow for the first characterization of key properties of the hybrid superconducting system.}, author = {Phan, Duc T and Senior, Jorden L and Ghazaryan, Areg and Hatefipour, M. and Strickland, W. M. and Shabani, J. and Serbyn, Maksym and Higginbotham, Andrew P}, booktitle = {arXiv}, title = {{Breakdown of induced p±ip pairing in a superconductor-semiconductor hybrid}}, doi = {10.48550/arXiv.2107.03695}, year = {2021}, } @article{10033, abstract = {The ⊗*-monoidal structure on the category of sheaves on the Ran space is not pro-nilpotent in the sense of [3]. However, under some connectivity assumptions, we prove that Koszul duality induces an equivalence of categories and that this equivalence behaves nicely with respect to Verdier duality on the Ran space and integrating along the Ran space, i.e. taking factorization homology. Based on ideas sketched in [4], we show that these results also offer a simpler alternative to one of the two main steps in the proof of the Atiyah-Bott formula given in [7] and [5].}, author = {Ho, Quoc P}, issn = {1090-2082}, journal = {Advances in Mathematics}, keywords = {Chiral algebras, Chiral homology, Factorization algebras, Koszul duality, Ran space}, publisher = {Elsevier}, title = {{The Atiyah-Bott formula and connectivity in chiral Koszul duality}}, doi = {10.1016/j.aim.2021.107992}, volume = {392}, year = {2021}, } @article{10051, abstract = {Rab-interacting molecule (RIM)-binding protein 2 (BP2) is a multidomain protein of the presynaptic active zone (AZ). By binding to RIM, bassoon (Bsn), and voltage-gated Ca2+ channels (CaV), it is considered to be a central organizer of the topography of CaV and release sites of synaptic vesicles (SVs) at the AZ. Here, we used RIM-BP2 knock-out (KO) mice and their wild-type (WT) littermates of either sex to investigate the role of RIM-BP2 at the endbulb of Held synapse of auditory nerve fibers (ANFs) with bushy cells (BCs) of the cochlear nucleus, a fast relay of the auditory pathway with high release probability. Disruption of RIM-BP2 lowered release probability altering short-term plasticity and reduced evoked EPSCs. Analysis of SV pool dynamics during high-frequency train stimulation indicated a reduction of SVs with high release probability but an overall normal size of the readily releasable SV pool (RRP). The Ca2+-dependent fast component of SV replenishment after RRP depletion was slowed. Ultrastructural analysis by superresolution light and electron microscopy revealed an impaired topography of presynaptic CaV and a reduction of docked and membrane-proximal SVs at the AZ. We conclude that RIM-BP2 organizes the topography of CaV, and promotes SV tethering and docking. This way RIM-BP2 is critical for establishing a high initial release probability as required to reliably signal sound onset information that we found to be degraded in BCs of RIM-BP2-deficient mice in vivo. SIGNIFICANCE STATEMENT: Rab-interacting molecule (RIM)-binding proteins (BPs) are key organizers of the active zone (AZ). Using a multidisciplinary approach to the calyceal endbulb of Held synapse that transmits auditory information at rates of up to hundreds of Hertz with submillisecond precision we demonstrate a requirement for RIM-BP2 for normal auditory signaling. Endbulb synapses lacking RIM-BP2 show a reduced release probability despite normal whole-terminal Ca2+ influx and abundance of the key priming protein Munc13-1, a reduced rate of SV replenishment, as well as an altered topography of voltage-gated (CaV)2.1 Ca2+ channels, and fewer docked and membrane proximal synaptic vesicles (SVs). This hampers transmission of sound onset information likely affecting downstream neural computations such as of sound localization.}, author = {Butola, Tanvi and Alvanos, Theocharis and Hintze, Anika and Koppensteiner, Peter and Kleindienst, David and Shigemoto, Ryuichi and Wichmann, Carolin and Moser, Tobias}, issn = {1529-2401}, journal = {Journal of Neuroscience}, number = {37}, pages = {7742--7767}, publisher = {Society for Neuroscience}, title = {{RIM-binding protein 2 organizes Ca21 channel topography and regulates release probability and vesicle replenishment at a fast central synapse}}, doi = {10.1523/JNEUROSCI.0586-21.2021}, volume = {41}, year = {2021}, } @inproceedings{10052, abstract = {A deterministic finite automaton (DFA) 𝒜 is composite if its language L(𝒜) can be decomposed into an intersection ⋂_{i = 1}^k L(𝒜_i) of languages of smaller DFAs. Otherwise, 𝒜 is prime. This notion of primality was introduced by Kupferman and Mosheiff in 2013, and while they proved that we can decide whether a DFA is composite, the precise complexity of this problem is still open, with a doubly-exponential gap between the upper and lower bounds. In this work, we focus on permutation DFAs, i.e., those for which the transition monoid is a group. We provide an NP algorithm to decide whether a permutation DFA is composite, and show that the difficulty of this problem comes from the number of non-accepting states of the instance: we give a fixed-parameter tractable algorithm with the number of rejecting states as the parameter. Moreover, we investigate the class of commutative permutation DFAs. Their structural properties allow us to decide compositionality in NL, and even in LOGSPACE if the alphabet size is fixed. Despite this low complexity, we show that complex behaviors still arise in this class: we provide a family of composite DFAs each requiring polynomially many factors with respect to its size. We also consider the variant of the problem that asks whether a DFA is k-factor composite, that is, decomposable into k smaller DFAs, for some given integer k ∈ ℕ. We show that, for commutative permutation DFAs, restricting the number of factors makes the decision computationally harder, and yields a problem with tight bounds: it is NP-complete. Finally, we show that in general, this problem is in PSPACE, and it is in LOGSPACE for DFAs with a singleton alphabet.}, author = {Jecker, Ismael R and Mazzocchi, Nicolas and Wolf, Petra}, booktitle = {32nd International Conference on Concurrency Theory}, isbn = {978-3-9597-7203-7}, issn = {1868-8969}, location = {Paris, France}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Decomposing permutation automata}}, doi = {10.4230/LIPIcs.CONCUR.2021.18}, volume = {203}, year = {2021}, } @inproceedings{10053, abstract = {This paper characterizes the latency of the simplified successive-cancellation (SSC) decoding scheme for polar codes under hardware resource constraints. In particular, when the number of processing elements P that can perform SSC decoding operations in parallel is limited, as is the case in practice, the latency of SSC decoding is O(N1−1 μ+NPlog2log2NP), where N is the block length of the code and μ is the scaling exponent of polar codes for the channel. Three direct consequences of this bound are presented. First, in a fully-parallel implementation where P=N2 , the latency of SSC decoding is O(N1−1/μ) , which is sublinear in the block length. This recovers a result from an earlier work. Second, in a fully-serial implementation where P=1 , the latency of SSC decoding scales as O(Nlog2log2N) . The multiplicative constant is also calculated: we show that the latency of SSC decoding when P=1 is given by (2+o(1))Nlog2log2N . Third, in a semi-parallel implementation, the smallest P that gives the same latency as that of the fully-parallel implementation is P=N1/μ . The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.}, author = {Hashemi, Seyyed Ali and Mondelli, Marco and Fazeli, Arman and Vardy, Alexander and Cioffi, John and Goldsmith, Andrea}, booktitle = {2021 IEEE International Symposium on Information Theory}, isbn = {978-1-5386-8210-4}, issn = {2157-8095}, location = {Melbourne, Australia}, pages = {2369--2374}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Parallelism versus latency in simplified successive-cancellation decoding of polar codes}}, doi = {10.1109/ISIT45174.2021.9518153}, year = {2021}, } @inproceedings{10054, abstract = {Graphs and games on graphs are fundamental models for the analysis of reactive systems, in particular, for model-checking and the synthesis of reactive systems. The class of ω-regular languages provides a robust specification formalism for the desired properties of reactive systems. In the classical infinitary formulation of the liveness part of an ω-regular specification, a "good" event must happen eventually without any bound between the good events. A stronger notion of liveness is bounded liveness, which requires that good events happen within d transitions. Given a graph or a game graph with n vertices, m edges, and a bounded liveness objective, the previous best-known algorithmic bounds are as follows: (i) O(dm) for graphs, which in the worst-case is O(n³); and (ii) O(n² d²) for games on graphs. Our main contributions improve these long-standing algorithmic bounds. For graphs we present: (i) a randomized algorithm with one-sided error with running time O(n^{2.5} log n) for the bounded liveness objectives; and (ii) a deterministic linear-time algorithm for the complement of bounded liveness objectives. For games on graphs, we present an O(n² d) time algorithm for the bounded liveness objectives.}, author = {Chatterjee, Krishnendu and Henzinger, Monika H and Kale, Sagar Sudhir and Svozil, Alexander}, booktitle = {48th International Colloquium on Automata, Languages, and Programming}, isbn = {978-3-95977-195-5}, issn = {1868-8969}, location = {Glasgow, Scotland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Faster algorithms for bounded liveness in graphs and game graphs}}, doi = {10.4230/LIPIcs.ICALP.2021.124}, volume = {198}, year = {2021}, } @inproceedings{10055, abstract = {Repeated idempotent elements are commonly used to characterise iterable behaviours in abstract models of computation. Therefore, given a monoid M, it is natural to ask how long a sequence of elements of M needs to be to ensure the presence of consecutive idempotent factors. This question is formalised through the notion of the Ramsey function R_M associated to M, obtained by mapping every k ∈ ℕ to the minimal integer R_M(k) such that every word u ∈ M^* of length R_M(k) contains k consecutive non-empty factors that correspond to the same idempotent element of M. In this work, we study the behaviour of the Ramsey function R_M by investigating the regular 𝒟-length of M, defined as the largest size L(M) of a submonoid of M isomorphic to the set of natural numbers {1,2, …, L(M)} equipped with the max operation. We show that the regular 𝒟-length of M determines the degree of R_M, by proving that k^L(M) ≤ R_M(k) ≤ (k|M|⁴)^L(M). To allow applications of this result, we provide the value of the regular 𝒟-length of diverse monoids. In particular, we prove that the full monoid of n × n Boolean matrices, which is used to express transition monoids of non-deterministic automata, has a regular 𝒟-length of (n²+n+2)/2.}, author = {Jecker, Ismael R}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science}, isbn = {978-3-9597-7180-1}, issn = {1868-8969}, location = {Saarbrücken, Germany}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{A Ramsey theorem for finite monoids}}, doi = {10.4230/LIPIcs.STACS.2021.44}, volume = {187}, year = {2021}, } @article{10069, abstract = {The extent to which women differ in the course of blood cell counts throughout pregnancy, and the importance of these changes to pregnancy outcomes has not been well defined. Here, we develop a series of statistical analyses of repeated measures data to reveal the degree to which women differ in the course of pregnancy, predict the changes that occur, and determine the importance of these changes for post-partum hemorrhage (PPH) which is one of the leading causes of maternal mortality. We present a prospective cohort of 4082 births recorded at the University Hospital, Lausanne, Switzerland between 2009 and 2014 where full labour records could be obtained, along with complete blood count data taken at hospital admission. We find significant differences, at a [Formula: see text] level, among women in how blood count values change through pregnancy for mean corpuscular hemoglobin, mean corpuscular volume, mean platelet volume, platelet count and red cell distribution width. We find evidence that almost all complete blood count values show trimester-specific associations with PPH. For example, high platelet count (OR 1.20, 95% CI 1.01-1.53), high mean platelet volume (OR 1.58, 95% CI 1.04-2.08), and high erythrocyte levels (OR 1.36, 95% CI 1.01-1.57) in trimester 1 increased PPH, but high values in trimester 3 decreased PPH risk (OR 0.85, 0.79, 0.67 respectively). We show that differences among women in the course of blood cell counts throughout pregnancy have an important role in shaping pregnancy outcome and tracking blood count value changes through pregnancy improves identification of women at increased risk of postpartum hemorrhage. This study provides greater understanding of the complex changes in blood count values that occur through pregnancy and provides indicators to guide the stratification of patients into risk groups.}, author = {Robinson, Matthew Richard and Patxot, Marion and Stojanov, Miloš and Blum, Sabine and Baud, David}, issn = {2045-2322}, journal = {Scientific Reports}, publisher = {Springer Nature}, title = {{Postpartum hemorrhage risk is driven by changes in blood composition through pregnancy}}, doi = {10.1038/s41598-021-98411-z}, volume = {11}, year = {2021}, }