TY - THES AB - Deep learning is best known for its empirical success across a wide range of applications spanning computer vision, natural language processing and speech. Of equal significance, though perhaps less known, are its ramifications for learning theory: deep networks have been observed to perform surprisingly well in the high-capacity regime, aka the overfitting or underspecified regime. Classically, this regime on the far right of the bias-variance curve is associated with poor generalisation; however, recent experiments with deep networks challenge this view. This thesis is devoted to investigating various aspects of underspecification in deep learning. First, we argue that deep learning models are underspecified on two levels: a) any given training dataset can be fit by many different functions, and b) any given function can be expressed by many different parameter configurations. We refer to the second kind of underspecification as parameterisation redundancy and we precisely characterise its extent. Second, we characterise the implicit criteria (the inductive bias) that guide learning in the underspecified regime. Specifically, we consider a nonlinear but tractable classification setting, and show that given the choice, neural networks learn classifiers with a large margin. Third, we consider learning scenarios where the inductive bias is not by itself sufficient to deal with underspecification. We then study different ways of ‘tightening the specification’: i) In the setting of representation learning with variational autoencoders, we propose a hand- crafted regulariser based on mutual information. ii) In the setting of binary classification, we consider soft-label (real-valued) supervision. We derive a generalisation bound for linear networks supervised in this way and verify that soft labels facilitate fast learning. Finally, we explore an application of soft-label supervision to the training of multi-exit models. AU - Bui Thi Mai, Phuong ID - 9418 SN - 2663-337X TI - Underspecification in deep learning ER - TY - GEN AB - The Birkhoff conjecture says that the boundary of a strictly convex integrable billiard table is necessarily an ellipse. In this article, we consider a stronger notion of integrability, namely, integrability close to the boundary, and prove a local version of this conjecture: a small perturbation of almost every ellipse that preserves integrability near the boundary, is itself an ellipse. We apply this result to study local spectral rigidity of ellipses using the connection between the wave trace of the Laplacian and the dynamics near the boundary and establish rigidity for almost all of them. AU - Koval, Illya ID - 14278 T2 - arXiv TI - Local strong Birkhoff conjecture and local spectral rigidity of almost every ellipse ER - TY - THES AB - The design and verification of concurrent systems remains an open challenge due to the non-determinism that arises from the inter-process communication. In particular, concurrent programs are notoriously difficult both to be written correctly and to be analyzed formally, as complex thread interaction has to be accounted for. The difficulties are further exacerbated when concurrent programs get executed on modern-day hardware, which contains various buffering and caching mechanisms for efficiency reasons. This causes further subtle non-determinism, which can often produce very unintuitive behavior of the concurrent programs. Model checking is at the forefront of tackling the verification problem, where the task is to decide, given as input a concurrent system and a desired property, whether the system satisfies the property. The inherent state-space explosion problem in model checking of concurrent systems causes naïve explicit methods not to scale, thus more inventive methods are required. One such method is stateless model checking (SMC), which explores in memory-efficient manner the program executions rather than the states of the program. State-of-the-art SMC is typically coupled with partial order reduction (POR) techniques, which argue that certain executions provably produce identical system behavior, thus limiting the amount of executions one needs to explore in order to cover all possible behaviors. Another method to tackle the state-space explosion is symbolic model checking, where the considered techniques operate on a succinct implicit representation of the input system rather than explicitly accessing the system. In this thesis we present new techniques for verification of concurrent systems. We present several novel POR methods for SMC of concurrent programs under various models of semantics, some of which account for write-buffering mechanisms. Additionally, we present novel algorithms for symbolic model checking of finite-state concurrent systems, where the desired property of the systems is to ensure a formally defined notion of fairness. AU - Toman, Viktor ID - 10199 KW - concurrency KW - verification KW - model checking SN - 2663-337X TI - Improved verification techniques for concurrent systems ER - TY - JOUR AB - We develop a Bayesian model (BayesRR-RC) that provides robust SNP-heritability estimation, an alternative to marker discovery, and accurate genomic prediction, taking 22 seconds per iteration to estimate 8.4 million SNP-effects and 78 SNP-heritability parameters in the UK Biobank. We find that only ≤10% of the genetic variation captured for height, body mass index, cardiovascular disease, and type 2 diabetes is attributable to proximal regulatory regions within 10kb upstream of genes, while 12-25% is attributed to coding regions, 32–44% to introns, and 22-28% to distal 10-500kb upstream regions. Up to 24% of all cis and coding regions of each chromosome are associated with each trait, with over 3,100 independent exonic and intronic regions and over 5,400 independent regulatory regions having ≥95% probability of contributing ≥0.001% to the genetic variance of these four traits. Our open-source software (GMRM) provides a scalable alternative to current approaches for biobank data. AU - Patxot, Marion AU - Trejo Banos, Daniel AU - Kousathanas, Athanasios AU - Orliac, Etienne J AU - Ojavee, Sven E AU - Moser, Gerhard AU - Sidorenko, Julia AU - Kutalik, Zoltan AU - Magi, Reedik AU - Visscher, Peter M AU - Ronnegard, Lars AU - Robinson, Matthew Richard ID - 8429 IS - 1 JF - Nature Communications TI - Probabilistic inference of the genetic architecture underlying functional enrichment of complex traits VL - 12 ER - TY - CONF AB - Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic CONGEST model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labelled graph under batch changes. We investigate, when a batch of alpha edge label changes arrive, - how much time as a function of alpha we need to update an existing solution, and - how much information the nodes have to keep in local memory between batches in order to update the solution quickly. Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. The diverse time complexity of our model spans from constant time, through time polynomial in alpha, and to alpha time, which we show to be enough for any task. AU - Foerster, Klaus-Tycho AU - Korhonen, Janne AU - Paz, Ami AU - Rybicki, Joel AU - Schmid, Stefan ID - 10854 SN - 9781450380720 T2 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems TI - Input-dynamic distributed algorithms for communication networks ER - TY - JOUR AB - Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic \congest model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of α edge label changes arrive, \beginitemize \item how much time as a function of α we need to update an existing solution, and \item how much information the nodes have to keep in local memory between batches in order to update the solution quickly. \enditemize Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. In particular, we derive non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques. AU - Foerster, Klaus-Tycho AU - Korhonen, Janne AU - Paz, Ami AU - Rybicki, Joel AU - Schmid, Stefan ID - 10855 IS - 1 JF - Proceedings of the ACM on Measurement and Analysis of Computing Systems KW - Computer Networks and Communications KW - Hardware and Architecture KW - Safety KW - Risk KW - Reliability and Quality KW - Computer Science (miscellaneous) SN - 2476-1249 TI - Input-dynamic distributed algorithms for communication networks VL - 5 ER - TY - JOUR AB - We consider planning problems for graphs, Markov Decision Processes (MDPs), and games on graphs in an explicit state space. While graphs represent the most basic planning model, MDPs represent interaction with nature and games on graphs represent interaction with an adversarial environment. We consider two planning problems with k different target sets: (a) the coverage problem asks whether there is a plan for each individual target set; and (b) the sequential target reachability problem asks whether the targets can be reached in a given sequence. For the coverage problem, we present a linear-time algorithm for graphs, and quadratic conditional lower bound for MDPs and games on graphs. For the sequential target problem, we present a linear-time algorithm for graphs, a sub-quadratic algorithm for MDPs, and a quadratic conditional lower bound for games on graphs. Our results with conditional lower bounds, based on the boolean matrix multiplication (BMM) conjecture and strong exponential time hypothesis (SETH), establish (i) model-separation results showing that for the coverage problem MDPs and games on graphs are harder than graphs, and for the sequential reachability problem games on graphs are harder than MDPs and graphs; and (ii) problem-separation results showing that for MDPs the coverage problem is harder than the sequential target problem. AU - Chatterjee, Krishnendu AU - Dvořák, Wolfgang AU - Henzinger, Monika H AU - Svozil, Alexander ID - 9293 IS - 8 JF - Artificial Intelligence SN - 0004-3702 TI - Algorithms and conditional lower bounds for planning problems VL - 297 ER - TY - GEN AB - We develop a Bayesian model (BayesRR-RC) that provides robust SNP-heritability estimation, an alternative to marker discovery, and accurate genomic prediction, taking 22 seconds per iteration to estimate 8.4 million SNP-effects and 78 SNP-heritability parameters in the UK Biobank. We find that only $\leq$ 10\% of the genetic variation captured for height, body mass index, cardiovascular disease, and type 2 diabetes is attributable to proximal regulatory regions within 10kb upstream of genes, while 12-25% is attributed to coding regions, 32-44% to introns, and 22-28% to distal 10-500kb upstream regions. Up to 24% of all cis and coding regions of each chromosome are associated with each trait, with over 3,100 independent exonic and intronic regions and over 5,400 independent regulatory regions having >95% probability of contributing >0.001% to the genetic variance of these four traits. Our open-source software (GMRM) provides a scalable alternative to current approaches for biobank data. AU - Robinson, Matthew Richard ID - 13063 TI - Probabilistic inference of the genetic architecture of functional enrichment of complex traits ER - TY - JOUR AB - The high processing cost, poor mechanical properties and moderate performance of Bi2Te3–based alloys used in thermoelectric devices limit the cost-effectiveness of this energy conversion technology. Towards solving these current challenges, in the present work, we detail a low temperature solution-based approach to produce Bi2Te3-Cu2-xTe nanocomposites with improved thermoelectric performance. Our approach consists in combining proper ratios of colloidal nanoparticles and to consolidate the resulting mixture into nanocomposites using a hot press. The transport properties of the nanocomposites are characterized and compared with those of pure Bi2Te3 nanomaterials obtained following the same procedure. In contrast with most previous works, the presence of Cu2-xTe nanodomains does not result in a significant reduction of the lattice thermal conductivity of the reference Bi2Te3 nanomaterial, which is already very low. However, the introduction of Cu2-xTe yields a nearly threefold increase of the power factor associated to a simultaneous increase of the Seebeck coefficient and electrical conductivity at temperatures above 400 K. Taking into account the band alignment of the two materials, we rationalize this increase by considering that Cu2-xTe nanostructures, with a relatively low electron affinity, are able to inject electrons into Bi2Te3, enhancing in this way its electrical conductivity. The simultaneous increase of the Seebeck coefficient is related to the energy filtering of charge carriers at energy barriers within Bi2Te3 domains associated with the accumulation of electrons in regions nearby a Cu2-xTe/Bi2Te3 heterojunction. Overall, with the incorporation of a proper amount of Cu2-xTe nanoparticles, we demonstrate a 250% improvement of the thermoelectric figure of merit of Bi2Te3. AU - Zhang, Yu AU - Xing, Congcong AU - Liu, Yu AU - Li, Mengyao AU - Xiao, Ke AU - Guardia, Pablo AU - Lee, Seungho AU - Han, Xu AU - Moghaddam, Ahmad AU - Roa, Joan J AU - Arbiol, Jordi AU - Ibáñez, Maria AU - Pan, Kai AU - Prato, Mirko AU - Xie, Ying AU - Cabot, Andreu ID - 9304 IS - 8 JF - Chemical Engineering Journal SN - 1385-8947 TI - Influence of copper telluride nanodomains on the transport properties of n-type bismuth telluride VL - 418 ER - TY - JOUR AB - Astrocytes extensively infiltrate the neuropil to regulate critical aspects of synaptic development and function. This process is regulated by transcellular interactions between astrocytes and neurons via cell adhesion molecules. How astrocytes coordinate developmental processes among one another to parse out the synaptic neuropil and form non-overlapping territories is unknown. Here we identify a molecular mechanism regulating astrocyte-astrocyte interactions during development to coordinate astrocyte morphogenesis and gap junction coupling. We show that hepaCAM, a disease-linked, astrocyte-enriched cell adhesion molecule, regulates astrocyte competition for territory and morphological complexity in the developing mouse cortex. Furthermore, conditional deletion of Hepacam from developing astrocytes significantly impairs gap junction coupling between astrocytes and disrupts the balance between synaptic excitation and inhibition. Mutations in HEPACAM cause megalencephalic leukoencephalopathy with subcortical cysts in humans. Therefore, our findings suggest that disruption of astrocyte self-organization mechanisms could be an underlying cause of neural pathology. AU - Baldwin, Katherine T. AU - Tan, Christabel X. AU - Strader, Samuel T. AU - Jiang, Changyu AU - Savage, Justin T. AU - Elorza-Vidal, Xabier AU - Contreras, Ximena AU - Rülicke, Thomas AU - Hippenmeyer, Simon AU - Estévez, Raúl AU - Ji, Ru-Rong AU - Eroglu, Cagla ID - 9793 IS - 15 JF - Neuron SN - 0896-6273 TI - HepaCAM controls astrocyte self-organization and coupling VL - 109 ER - TY - JOUR AB - Copper chalcogenides are outstanding thermoelectric materials for applications in the medium-high temperature range. Among different chalcogenides, while Cu2−xSe is characterized by higher thermoelectric figures of merit, Cu2−xS provides advantages in terms of low cost and element abundance. In the present work, we investigate the effect of different dopants to enhance the Cu2−xS performance and also its thermal stability. Among the tested options, Pb-doped Cu2−xS shows the highest improvement in stability against sulfur volatilization. Additionally, Pb incorporation allows tuning charge carrier concentration, which enables a significant improvement of the power factor. We demonstrate here that the introduction of an optimal additive amount of just 0.3% results in a threefold increase of the power factor in the middle-temperature range (500–800 K) and a record dimensionless thermoelectric figure of merit above 2 at 880 K. AU - Zhang, Yu AU - Xing, Congcong AU - Liu, Yu AU - Spadaro, Maria Chiara AU - Wang, Xiang AU - Li, Mengyao AU - Xiao, Ke AU - Zhang, Ting AU - Guardia, Pablo AU - Lim, Khak Ho AU - Moghaddam, Ahmad Ostovari AU - Llorca, Jordi AU - Arbiol, Jordi AU - Ibáñez, Maria AU - Cabot, Andreu ID - 9305 IS - 7 JF - Nano Energy SN - 2211-2855 TI - Doping-mediated stabilization of copper vacancies to promote thermoelectric properties of Cu2-xS VL - 85 ER - TY - JOUR AB - Plant fitness is largely dependent on the root, the underground organ, which, besides its anchoring function, supplies the plant body with water and all nutrients necessary for growth and development. To exploit the soil effectively, roots must constantly integrate environmental signals and react through adjustment of growth and development. Important components of the root management strategy involve a rapid modulation of the root growth kinetics and growth direction, as well as an increase of the root system radius through formation of lateral roots (LRs). At the molecular level, such a fascinating growth and developmental flexibility of root organ requires regulatory networks that guarantee stability of the developmental program but also allows integration of various environmental inputs. The plant hormone auxin is one of the principal endogenous regulators of root system architecture by controlling primary root growth and formation of LR. In this review, we discuss recent progress in understanding molecular networks where auxin is one of the main players shaping the root system and acting as mediator between endogenous cues and environmental factors. AU - Cavallari, Nicola AU - Artner, Christina AU - Benková, Eva ID - 9212 IS - 7 JF - Cold Spring Harbor Perspectives in Biology SN - 1943-0264 TI - Auxin-regulated lateral root organogenesis VL - 13 ER - TY - JOUR AB - Chronic psychological stress is one of the most important triggers and environmental risk factors for neuropsychiatric disorders. Chronic stress can influence all organs via the secretion of stress hormones, including glucocorticoids by the adrenal glands, which coordinate the stress response across the body. In the brain, glucocorticoid receptors (GR) are expressed by various cell types including microglia, which are its resident immune cells regulating stress-induced inflammatory processes. To study the roles of microglial GR under normal homeostatic conditions and following chronic stress, we generated a mouse model in which the GR gene is depleted in microglia specifically at adulthood to prevent developmental confounds. We first confirmed that microglia were depleted in GR in our model in males and females among the cingulate cortex and the hippocampus, both stress-sensitive brain regions. Then, cohorts of microglial-GR depleted and wild-type (WT) adult female mice were housed for 3 weeks in a standard or stressful condition, using a chronic unpredictable mild stress (CUMS) paradigm. CUMS induced stress-related behavior in both microglial-GR depleted and WT animals as demonstrated by a decrease of both saccharine preference and progressive ratio breakpoint. Nevertheless, the hippocampal microglial and neural mechanisms underlying the adaptation to stress occurred differently between the two genotypes. Upon CUMS exposure, microglial morphology was altered in the WT controls, without any apparent effect in microglial-GR depleted mice. Furthermore, in the standard environment condition, GR depleted-microglia showed increased expression of pro-inflammatory genes, and genes involved in microglial homeostatic functions (such as Trem2, Cx3cr1 and Mertk). On the contrary, in CUMS condition, GR depleted-microglia showed reduced expression levels of pro-inflammatory genes and increased neuroprotective as well as anti-inflammatory genes compared to WT-microglia. Moreover, in microglial-GR depleted mice, but not in WT mice, CUMS led to a significant reduction of CA1 long-term potentiation and paired-pulse ratio. Lastly, differences in adult hippocampal neurogenesis were observed between the genotypes during normal homeostatic conditions, with microglial-GR deficiency increasing the formation of newborn neurons in the dentate gyrus subgranular zone independently from stress exposure. Together, these findings indicate that, although the deletion of microglial GR did not prevent the animal’s ability to respond to stress, it contributed to modulating hippocampal functions in both standard and stressful conditions, notably by shaping the microglial response to chronic stress. AU - Picard, Katherine AU - Bisht, Kanchan AU - Poggini, Silvia AU - Garofalo, Stefano AU - Golia, Maria Teresa AU - Basilico, Bernadette AU - Abdallah, Fatima AU - Ciano Albanese, Naomi AU - Amrein, Irmgard AU - Vernoux, Nathalie AU - Sharma, Kaushik AU - Hui, Chin Wai AU - C. Savage, Julie AU - Limatola, Cristina AU - Ragozzino, Davide AU - Maggi, Laura AU - Branchi, Igor AU - Tremblay, Marie Ève ID - 9953 JF - Brain, Behavior, and Immunity SN - 0889-1591 TI - Microglial-glucocorticoid receptor depletion alters the response of hippocampal microglia and neurons in a chronic unpredictable mild stress paradigm in female mice VL - 97 ER - TY - JOUR AB - Composite materials offer numerous advantages in a wide range of applications, including thermoelectrics. Here, semiconductor–metal composites are produced by just blending nanoparticles of a sulfide semiconductor obtained in aqueous solution and at room temperature with a metallic Cu powder. The obtained blend is annealed in a reducing atmosphere and afterward consolidated into dense polycrystalline pellets through spark plasma sintering (SPS). We observe that, during the annealing process, the presence of metallic copper activates a partial reduction of the PbS, resulting in the formation of PbS–Pb–CuxS composites. The presence of metallic lead during the SPS process habilitates the liquid-phase sintering of the composite. Besides, by comparing the transport properties of PbS, the PbS–Pb–CuxS composites, and PbS–CuxS composites obtained by blending PbS and CuxS nanoparticles, we demonstrate that the presence of metallic lead decisively contributes to a strong increase of the charge carrier concentration through spillover of charge carriers enabled by the low work function of lead. The increase in charge carrier concentration translates into much higher electrical conductivities and moderately lower Seebeck coefficients. These properties translate into power factors up to 2.1 mW m–1 K–2 at ambient temperature, well above those of PbS and PbS + CuxS. Additionally, the presence of multiple phases in the final composite results in a notable decrease in the lattice thermal conductivity. Overall, the introduction of metallic copper in the initial blend results in a significant improvement of the thermoelectric performance of PbS, reaching a dimensionless thermoelectric figure of merit ZT = 1.1 at 750 K, which represents about a 400% increase over bare PbS. Besides, an average ZTave = 0.72 in the temperature range 320–773 K is demonstrated. AU - Li, Mengyao AU - Liu, Yu AU - Zhang, Yu AU - Han, Xu AU - Xiao, Ke AU - Nabahat, Mehran AU - Arbiol, Jordi AU - Llorca, Jordi AU - Ibáñez, Maria AU - Cabot, Andreu ID - 10327 IS - 43 JF - ACS Applied Materials and Interfaces KW - CuxS KW - PbS KW - energy conversion KW - nanocomposite KW - nanoparticle KW - solution synthesis KW - thermoelectric SN - 1944-8244 TI - PbS–Pb–CuxS composites for thermoelectric application VL - 13 ER - TY - JOUR AB - Cu2–xS has become one of the most promising thermoelectric materials for application in the middle-high temperature range. Its advantages include the abundance, low cost, and safety of its elements and a high performance at relatively elevated temperatures. However, stability issues limit its operation current and temperature, thus calling for the optimization of the material performance in the middle temperature range. Here, we present a synthetic protocol for large scale production of covellite CuS nanoparticles at ambient temperature and atmosphere, and using water as a solvent. The crystal phase and stoichiometry of the particles are afterward tuned through an annealing process at a moderate temperature under inert or reducing atmosphere. While annealing under argon results in Cu1.8S nanopowder with a rhombohedral crystal phase, annealing in an atmosphere containing hydrogen leads to tetragonal Cu1.96S. High temperature X-ray diffraction analysis shows the material annealed in argon to transform to the cubic phase at ca. 400 K, while the material annealed in the presence of hydrogen undergoes two phase transitions, first to hexagonal and then to the cubic structure. The annealing atmosphere, temperature, and time allow adjustment of the density of copper vacancies and thus tuning of the charge carrier concentration and material transport properties. In this direction, the material annealed under Ar is characterized by higher electrical conductivities but lower Seebeck coefficients than the material annealed in the presence of hydrogen. By optimizing the charge carrier concentration through the annealing time, Cu2–xS with record figures of merit in the middle temperature range, up to 1.41 at 710 K, is obtained. We finally demonstrate that this strategy, based on a low-cost and scalable solution synthesis process, is also suitable for the production of high performance Cu2–xS layers using high throughput and cost-effective printing technologies. AU - Li, Mengyao AU - Liu, Yu AU - Zhang, Yu AU - Han, Xu AU - Zhang, Ting AU - Zuo, Yong AU - Xie, Chenyang AU - Xiao, Ke AU - Arbiol, Jordi AU - Llorca, Jordi AU - Ibáñez, Maria AU - Liu, Junfeng AU - Cabot, Andreu ID - 9235 IS - 3 JF - ACS Nano KW - General Engineering KW - General Physics and Astronomy KW - General Materials Science SN - 1936-0851 TI - Effect of the annealing atmosphere on crystal phase and thermoelectric properties of copper sulfide VL - 15 ER - TY - JOUR AB - Two common representations of close packings of identical spheres consisting of hexagonal layers, called Barlow stackings, appear abundantly in minerals and metals. These motifs, however, occupy an identical portion of space and bear identical first-order topological signatures as measured by persistent homology. Here we present a novel method based on k-fold covers that unambiguously distinguishes between these patterns. Moreover, our approach provides topological evidence that the FCC motif is the more stable of the two in the context of evolving experimental sphere packings during the transition from disordered to an ordered state. We conclude that our approach can be generalised to distinguish between various Barlow stackings manifested in minerals and metals. AU - Osang, Georg F AU - Edelsbrunner, Herbert AU - Saadatfar, Mohammad ID - 10204 IS - 40 JF - Soft Matter SN - 1744-683X TI - Topological signatures and stability of hexagonal close packing and Barlow stackings VL - 17 ER - TY - CONF AB - We firstly introduce the self-assembled growth of highly uniform Ge quantum wires with controllable position, distance and length on patterned Si (001) substrates. We then present the electrically tunable strong spin-orbit coupling, the first Ge hole spin qubit and ultrafast operation of hole spin qubit in the Ge/Si quantum wires. AU - Gao, Fei AU - Zhang, Jie Yin AU - Wang, Jian Huan AU - Ming, Ming AU - Wang, Tina AU - Zhang, Jian Jun AU - Watzinger, Hannes AU - Kukucka, Josip AU - Vukušić, Lada AU - Katsaros, Georgios AU - Wang, Ke AU - Xu, Gang AU - Li, Hai Ou AU - Guo, Guo Ping ID - 9464 SN - 9781728181769 T2 - 2021 5th IEEE Electron Devices Technology and Manufacturing Conference, EDTM 2021 TI - Ge/Si quantum wires for quantum computing ER - TY - CONF AB - Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness. AU - Corbet, René AU - Kerber, Michael AU - Lesnick, Michael AU - Osang, Georg F ID - 9605 SN - 18688969 T2 - Leibniz International Proceedings in Informatics TI - Computing the multicover bifiltration VL - 189 ER - TY - CONF AB - Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. AU - Boissonnat, Jean-Daniel AU - Kachanovich, Siargey AU - Wintraecken, Mathijs ID - 9441 SN - 1868-8969 T2 - 37th International Symposium on Computational Geometry (SoCG 2021) TI - Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations VL - 189 ER - TY - JOUR AB - We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff, the ratio, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with bounded treewidth—a class that contains the control flow graphs of most programs. Let n denote the number of nodes of a graph, m the number of edges (for bounded treewidth 𝑚=𝑂(𝑛)) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for the minimum initial credit problem we show that (1) for general graphs the problem can be solved in 𝑂(𝑛2⋅𝑚) time and the associated decision problem in 𝑂(𝑛⋅𝑚) time, improving the previous known 𝑂(𝑛3⋅𝑚⋅log(𝑛⋅𝑊)) and 𝑂(𝑛2⋅𝑚) bounds, respectively; and (2) for bounded treewidth graphs we present an algorithm that requires 𝑂(𝑛⋅log𝑛) time. Second, for bounded treewidth graphs we present an algorithm that approximates the mean-payoff value within a factor of 1+𝜖 in time 𝑂(𝑛⋅log(𝑛/𝜖)) as compared to the classical exact algorithms on general graphs that require quadratic time. Third, for the ratio property we present an algorithm that for bounded treewidth graphs works in time 𝑂(𝑛⋅log(|𝑎⋅𝑏|))=𝑂(𝑛⋅log(𝑛⋅𝑊)), when the output is 𝑎𝑏, as compared to the previously best known algorithm on general graphs with running time 𝑂(𝑛2⋅log(𝑛⋅𝑊)). We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks. AU - Chatterjee, Krishnendu AU - Ibsen-Jensen, Rasmus AU - Pavlogiannis, Andreas ID - 9393 JF - Formal Methods in System Design SN - 0925-9856 TI - Faster algorithms for quantitative verification in bounded treewidth graphs VL - 57 ER -