@article{9197, abstract = {In this paper we introduce and study all-pay bidding games, a class of two player, zero-sum games on graphs. The game proceeds as follows. We place a token on some vertex in the graph and assign budgets to the two players. Each turn, each player submits a sealed legal bid (non-negative and below their remaining budget), which is deducted from their budget and the highest bidder moves the token onto an adjacent vertex. The game ends once a sink is reached, and Player 1 pays Player 2 the outcome that is associated with the sink. The players attempt to maximize their expected outcome. Our games model settings where effort (of no inherent value) needs to be invested in an ongoing and stateful manner. On the negative side, we show that even in simple games on DAGs, optimal strategies may require a distribution over bids with infinite support. A central quantity in bidding games is the ratio of the players budgets. On the positive side, we show a simple FPTAS for DAGs, that, for each budget ratio, outputs an approximation for the optimal strategy for that ratio. We also implement it, show that it performs well, and suggests interesting properties of these games. Then, given an outcome c, we show an algorithm for finding the necessary and sufficient initial ratio for guaranteeing outcome c with probability 1 and a strategy ensuring such. Finally, while the general case has not previously been studied, solving the specific game in which Player 1 wins iff he wins the first two auctions, has been long stated as an open question, which we solve.}, author = {Avni, Guy and Ibsen-Jensen, Rasmus and Tkadlec, Josef}, isbn = {9781577358350}, issn = {2374-3468}, journal = {Proceedings of the AAAI Conference on Artificial Intelligence}, location = {New York, NY, United States}, number = {02}, pages = {1798--1805}, publisher = {Association for the Advancement of Artificial Intelligence}, title = {{All-pay bidding games on graphs}}, doi = {10.1609/aaai.v34i02.5546}, volume = {34}, year = {2020}, } @inproceedings{9202, abstract = {We propose a novel hybridization method for stability analysis that over-approximates nonlinear dynamical systems by switched systems with linear inclusion dynamics. We observe that existing hybridization techniques for safety analysis that over-approximate nonlinear dynamical systems by switched affine inclusion dynamics and provide fixed approximation error, do not suffice for stability analysis. Hence, we propose a hybridization method that provides a state-dependent error which converges to zero as the state tends to the equilibrium point. The crux of our hybridization computation is an elegant recursive algorithm that uses partial derivatives of a given function to obtain upper and lower bound matrices for the over-approximating linear inclusion. We illustrate our method on some examples to demonstrate the application of the theory for stability analysis. In particular, our method is able to establish stability of a nonlinear system which does not admit a polynomial Lyapunov function.}, author = {Garcia Soto, Miriam and Prabhakar, Pavithra}, booktitle = {2020 IEEE Real-Time Systems Symposium}, issn = {2576-3172}, location = {Houston, TX, USA }, pages = {244--256}, publisher = {IEEE}, title = {{Hybridization for stability verification of nonlinear switched systems}}, doi = {10.1109/RTSS49844.2020.00031}, year = {2020}, } @article{9208, abstract = {Bending-active structures are able to efficiently produce complex curved shapes from flat panels. The desired deformation of the panels derives from the proper selection of their elastic properties. Optimized panels, called FlexMaps, are designed such that, once they are bent and assembled, the resulting static equilibrium configuration matches a desired input 3D shape. The FlexMaps elastic properties are controlled by locally varying spiraling geometric mesostructures, which are optimized in size and shape to match specific bending requests, namely the global curvature of the target shape. The design pipeline starts from a quad mesh representing the input 3D shape, which defines the edge size and the total amount of spirals: every quad will embed one spiral. Then, an optimization algorithm tunes the geometry of the spirals by using a simplified pre-computed rod model. This rod model is derived from a non-linear regression algorithm which approximates the non-linear behavior of solid FEM spiral models subject to hundreds of load combinations. This innovative pipeline has been applied to the project of a lightweight plywood pavilion named FlexMaps Pavilion, which is a single-layer piecewise twisted arch that fits a bounding box of 3.90x3.96x3.25 meters. This case study serves to test the applicability of this methodology at the architectural scale. The structure is validated via FE analyses and the fabrication of the full scale prototype.}, author = {Laccone, Francesco and Malomo, Luigi and Perez Rodriguez, Jesus and Pietroni, Nico and Ponchio, Federico and Bickel, Bernd and Cignoni, Paolo}, issn = {2523-3971}, journal = {SN Applied Sciences}, number = {9}, publisher = {Springer Nature}, title = {{A bending-active twisted-arch plywood structure: Computational design and fabrication of the FlexMaps Pavilion}}, doi = {10.1007/s42452-020-03305-w}, volume = {2}, year = {2020}, } @inproceedings{9221, abstract = {Recent works have shown that gradient descent can find a global minimum for over-parameterized neural networks where the widths of all the hidden layers scale polynomially with N (N being the number of training samples). In this paper, we prove that, for deep networks, a single layer of width N following the input layer suffices to ensure a similar guarantee. In particular, all the remaining layers are allowed to have constant widths, and form a pyramidal topology. We show an application of our result to the widely used LeCun’s initialization and obtain an over-parameterization requirement for the single wide layer of order N2. }, author = {Nguyen, Quynh and Mondelli, Marco}, booktitle = {34th Conference on Neural Information Processing Systems}, location = {Vancouver, Canada}, pages = {11961–11972}, publisher = {Neural Information Processing Systems Foundation}, title = {{Global convergence of deep networks with one wide layer followed by pyramidal topology}}, volume = {33}, year = {2020}, } @misc{9222, author = {Katsaros, Georgios}, publisher = {Institute of Science and Technology Austria}, title = {{Transport data for: Site‐controlled uniform Ge/Si Hut wires with electrically tunable spin–orbit coupling}}, doi = {10.15479/AT:ISTA:9222}, year = {2020}, } @article{9249, abstract = {Rhombic dodecahedron is a space filling polyhedron which represents the close packing of spheres in 3D space and the Voronoi structures of the face centered cubic (FCC) lattice. In this paper, we describe a new coordinate system where every 3-integer coordinates grid point corresponds to a rhombic dodecahedron centroid. In order to illustrate the interest of the new coordinate system, we propose the characterization of 3D digital plane with its topological features, such as the interrelation between the thickness of the digital plane and the separability constraint we aim to obtain. We also present the characterization of 3D digital lines and study it as the intersection of multiple digital planes. Characterization of 3D digital sphere with relevant topological features is proposed as well along with the 48-symmetry appearing in the new coordinate system.}, author = {Biswas, Ranita and Largeteau-Skapin, Gaëlle and Zrour, Rita and Andres, Eric}, issn = {2353-3390}, journal = {Mathematical Morphology - Theory and Applications}, number = {1}, pages = {143--158}, publisher = {De Gruyter}, title = {{Digital objects in rhombic dodecahedron grid}}, doi = {10.1515/mathm-2020-0106}, volume = {4}, year = {2020}, } @inproceedings{9299, abstract = {We call a multigraph non-homotopic if it can be drawn in the plane in such a way that no two edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. It is easy to see that a non-homotopic multigraph on n>1 vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with n vertices and m>4n edges is larger than cm2n for some constant c>0 , and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as n is fixed and m⟶∞ .}, author = {Pach, János and Tardos, Gábor and Tóth, Géza}, booktitle = {28th International Symposium on Graph Drawing and Network Visualization}, isbn = {9783030687656}, issn = {1611-3349}, location = {Virtual, Online}, pages = {359--371}, publisher = {Springer Nature}, title = {{Crossings between non-homotopic edges}}, doi = {10.1007/978-3-030-68766-3_28}, volume = {12590}, year = {2020}, } @article{9308, author = {Avvakumov, Sergey and Wagner, Uli and Mabillard, Isaac and Skopenkov, A. B.}, issn = {0036-0279}, journal = {Russian Mathematical Surveys}, number = {6}, pages = {1156--1158}, publisher = {IOP Publishing}, title = {{Eliminating higher-multiplicity intersections, III. Codimension 2}}, doi = {10.1070/RM9943}, volume = {75}, year = {2020}, } @misc{9326, abstract = {The mitochondrial respiratory chain, formed by five protein complexes, utilizes energy from catabolic processes to synthesize ATP. Complex I, the first and the largest protein complex of the chain, harvests electrons from NADH to reduce quinone, while pumping protons across the mitochondrial membrane. Detailed knowledge of the working principle of such coupled charge-transfer processes remains, however, fragmentary due to bottlenecks in understanding redox-driven conformational transitions and their interplay with the hydrated proton pathways. Complex I from Thermus thermophilus encases 16 subunits with nine iron–sulfur clusters, reduced by electrons from NADH. Here, employing the latest crystal structure of T. thermophilus complex I, we have used microsecond-scale molecular dynamics simulations to study the chemo-mechanical coupling between redox changes of the iron–sulfur clusters and conformational transitions across complex I. First, we identify the redox switches within complex I, which allosterically couple the dynamics of the quinone binding pocket to the site of NADH reduction. Second, our free-energy calculations reveal that the affinity of the quinone, specifically menaquinone, for the binding-site is higher than that of its reduced, menaquinol forma design essential for menaquinol release. Remarkably, the barriers to diffusive menaquinone dynamics are lesser than that of the more ubiquitous ubiquinone, and the naphthoquinone headgroup of the former furnishes stronger binding interactions with the pocket, favoring menaquinone for charge transport in T. thermophilus. Our computations are consistent with experimentally validated mutations and hierarchize the key residues into three functional classes, identifying new mutation targets. Third, long-range hydrogen-bond networks connecting the quinone-binding site to the transmembrane subunits are found to be responsible for proton pumping. Put together, the simulations reveal the molecular design principles linking redox reactions to quinone turnover to proton translocation in complex I.}, author = {Gupta, Chitrak and Khaniya, Umesh and Chan, Chun and Dehez, Francois and Shekhar, Mrinal and Gunner, M. R. and Sazanov, Leonid A and Chipot, Christophe and Singharoy, Abhishek}, publisher = {American Chemical Society}, title = {{Charge transfer and chemo-mechanical coupling in respiratory complex I}}, doi = {10.1021/jacs.9b13450.s002}, year = {2020}, } @article{9526, abstract = {DNA methylation and histone H1 mediate transcriptional silencing of genes and transposable elements, but how they interact is unclear. In plants and animals with mosaic genomic methylation, functionally mysterious methylation is also common within constitutively active housekeeping genes. Here, we show that H1 is enriched in methylated sequences, including genes, of Arabidopsis thaliana, yet this enrichment is independent of DNA methylation. Loss of H1 disperses heterochromatin, globally alters nucleosome organization, and activates H1-bound genes, but only weakly de-represses transposable elements. However, H1 loss strongly activates transposable elements hypomethylated through mutation of DNA methyltransferase MET1. Hypomethylation of genes also activates antisense transcription, which is modestly enhanced by H1 loss. Our results demonstrate that H1 and DNA methylation jointly maintain transcriptional homeostasis by silencing transposable elements and aberrant intragenic transcripts. Such functionality plausibly explains why DNA methylation, a well-known mutagen, has been maintained within coding sequences of crucial plant and animal genes.}, author = {Choi, Jaemyung and Lyons, David B. and Kim, M. Yvonne and Moore, Jonathan D. and Zilberman, Daniel}, issn = {1097-4164}, journal = {Molecular Cell}, number = {2}, pages = {310--323.e7}, publisher = {Elsevier}, title = {{DNA methylation and histone H1 jointly repress transposable elements and aberrant intragenic transcripts}}, doi = {10.1016/j.molcel.2019.10.011}, volume = {77}, year = {2020}, } @article{9630, abstract = {Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probability distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory needed for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable the usage of existing computational topology software in this context.}, author = {Edelsbrunner, Herbert and Virk, Ziga and Wagner, Hubert}, issn = {1920-180X}, journal = {Journal of Computational Geometry}, number = {2}, pages = {162--182}, publisher = {Carleton University}, title = {{Topological data analysis in information space}}, doi = {10.20382/jocg.v11i2a7}, volume = {11}, year = {2020}, } @inproceedings{9631, abstract = {The ability to leverage large-scale hardware parallelism has been one of the key enablers of the accelerated recent progress in machine learning. Consequently, there has been considerable effort invested into developing efficient parallel variants of classic machine learning algorithms. However, despite the wealth of knowledge on parallelization, some classic machine learning algorithms often prove hard to parallelize efficiently while maintaining convergence. In this paper, we focus on efficient parallel algorithms for the key machine learning task of inference on graphical models, in particular on the fundamental belief propagation algorithm. We address the challenge of efficiently parallelizing this classic paradigm by showing how to leverage scalable relaxed schedulers in this context. We present an extensive empirical study, showing that our approach outperforms previous parallel belief propagation implementations both in terms of scalability and in terms of wall-clock convergence time, on a range of practical applications.}, author = {Aksenov, Vitaly and Alistarh, Dan-Adrian and Korhonen, Janne}, isbn = {9781713829546}, issn = {1049-5258}, location = {Vancouver, Canada}, pages = {22361--22372}, publisher = {Neural Information Processing Systems Foundation}, title = {{Scalable belief propagation via relaxed scheduling}}, volume = {33}, year = {2020}, } @inproceedings{9632, abstract = {Second-order information, in the form of Hessian- or Inverse-Hessian-vector products, is a fundamental tool for solving optimization problems. Recently, there has been significant interest in utilizing this information in the context of deep neural networks; however, relatively little is known about the quality of existing approximations in this context. Our work examines this question, identifies issues with existing approaches, and proposes a method called WoodFisher to compute a faithful and efficient estimate of the inverse Hessian. Our main application is to neural network compression, where we build on the classic Optimal Brain Damage/Surgeon framework. We demonstrate that WoodFisher significantly outperforms popular state-of-the-art methods for oneshot pruning. Further, even when iterative, gradual pruning is allowed, our method results in a gain in test accuracy over the state-of-the-art approaches, for standard image classification datasets such as ImageNet ILSVRC. We examine how our method can be extended to take into account first-order information, as well as illustrate its ability to automatically set layer-wise pruning thresholds and perform compression in the limited-data regime. The code is available at the following link, https://github.com/IST-DASLab/WoodFisher.}, author = {Singh, Sidak Pal and Alistarh, Dan-Adrian}, isbn = {9781713829546}, issn = {1049-5258}, location = {Vancouver, Canada}, pages = {18098--18109}, publisher = {Neural Information Processing Systems Foundation}, title = {{WoodFisher: Efficient second-order approximation for neural network compression}}, volume = {33}, year = {2020}, } @misc{9706, abstract = {Additional file 2: Supplementary Tables. The association of pre-adjusted protein levels with biological and technical covariates. Protein levels were adjusted for age, sex, array plate and four genetic principal components (population structure) prior to analyses. Significant associations are emboldened. (Table S1). pQTLs associated with inflammatory biomarker levels from Bayesian penalised regression model (Posterior Inclusion Probability > 95%). (Table S2). All pQTLs associated with inflammatory biomarker levels from ordinary least squares regression model (P < 7.14 × 10− 10). (Table S3). Summary of lambda values relating to ordinary least squares GWAS and EWAS performed on inflammatory protein levels (n = 70) in Lothian Birth Cohort 1936 study. (Table S4). Conditionally significant pQTLs associated with inflammatory biomarker levels from ordinary least squares regression model (P < 7.14 × 10− 10). (Table S5). Comparison of variance explained by ordinary least squares and Bayesian penalised regression models for concordantly identified SNPs. (Table S6). Estimate of heritability for blood protein levels as well as proportion of variance explained attributable to different prior mixtures. (Table S7). Comparison of heritability estimates from Ahsan et al. (maximum likelihood) and Hillary et al. (Bayesian penalised regression). (Table S8). List of concordant SNPs identified by linear model and Bayesian penalised regression and whether they have been previously identified as eQTLs. (Table S9). Bayesian tests of colocalisation for cis pQTLs and cis eQTLs. (Table S10). Sherlock algorithm: Genes whose expression are putatively associated with circulating inflammatory proteins that harbour pQTLs. (Table S11). CpGs associated with inflammatory protein biomarkers as identified by Bayesian model (Bayesian model; Posterior Inclusion Probability > 95%). (Table S12). CpGs associated with inflammatory protein biomarkers as identified by linear model (limma) at P < 5.14 × 10− 10. (Table S13). CpGs associated with inflammatory protein biomarkers as identified by mixed linear model (OSCA) at P < 5.14 × 10− 10. (Table S14). Estimate of variance explained for blood protein levels by DNA methylation as well as proportion of explained attributable to different prior mixtures - BayesR+. (Table S15). Comparison of variance in protein levels explained by genome-wide DNA methylation data by mixed linear model (OSCA) and Bayesian penalised regression model (BayesR+). (Table S16). Variance in circulating inflammatory protein biomarker levels explained by common genetic and methylation data (joint and conditional estimates from BayesR+). Ordered by combined variance explained by genetic and epigenetic data - smallest to largest. Significant results from t-tests comparing distributions for variance explained by methylation or genetics alone versus combined estimate are emboldened. (Table S17). Genetic and epigenetic factors identified by BayesR+ when conditioning on all SNPs and CpGs together. (Table S18). Mendelian Randomisation analyses to assess whether proteins with concordantly identified genetic signals are causally associated with Alzheimer’s disease risk. (Table S19).}, author = {Hillary, Robert F. and Trejo-Banos, Daniel and Kousathanas, Athanasios and McCartney, Daniel L. and Harris, Sarah E. and Stevenson, Anna J. and Patxot, Marion and Ojavee, Sven Erik and Zhang, Qian and Liewald, David C. and Ritchie, Craig W. and Evans, Kathryn L. and Tucker-Drob, Elliot M. and Wray, Naomi R. and McRae, Allan F. and Visscher, Peter M. and Deary, Ian J. and Robinson, Matthew Richard and Marioni, Riccardo E. }, publisher = {Springer Nature}, title = {{Additional file 2 of multi-method genome- and epigenome-wide studies of inflammatory protein levels in healthy older adults}}, doi = {10.6084/m9.figshare.12629697.v1}, year = {2020}, } @misc{9708, abstract = {This research data supports 'Hard antinodal gap revealed by quantum oscillations in the pseudogap regime of underdoped high-Tc superconductors'. A Readme file for plotting each figure is provided.}, author = {Hartstein, Mate and Hsu, Yu-Te and Modic, Kimberly A and Porras, Juan and Loew, Toshinao and Le Tacon, Matthieu and Zuo, Huakun and Wang, Jinhua and Zhu, Zengwei and Chan, Mun and McDonald, Ross and Lonzarich, Gilbert and Keimer, Bernhard and Sebastian, Suchitra and Harrison, Neil}, publisher = {Apollo - University of Cambridge}, title = {{Accompanying dataset for 'Hard antinodal gap revealed by quantum oscillations in the pseudogap regime of underdoped high-Tc superconductors'}}, doi = {10.17863/cam.50169}, year = {2020}, } @misc{9776, author = {Grah, Rok and Friedlander, Tamar}, publisher = {Public Library of Science}, title = {{Supporting information}}, doi = {10.1371/journal.pcbi.1007642.s001}, year = {2020}, } @misc{9777, author = {Grah, Rok and Friedlander, Tamar}, publisher = {Public Library of Science}, title = {{Maximizing crosstalk}}, doi = {10.1371/journal.pcbi.1007642.s002}, year = {2020}, } @misc{9779, author = {Grah, Rok and Friedlander, Tamar}, publisher = {Public Library of Science}, title = {{Distribution of crosstalk values}}, doi = {10.1371/journal.pcbi.1007642.s003}, year = {2020}, } @misc{9780, abstract = {PADREV : 4,4'-dimethoxy[1,1'-biphenyl]-2,2',5,5'-tetrol Space Group: C 2 (5), Cell: a 24.488(16)Å b 5.981(4)Å c 3.911(3)Å, α 90° β 91.47(3)° γ 90°}, author = {Schlemmer, Werner and Nothdurft, Philipp and Petzold, Alina and Riess, Gisbert and Frühwirt, Philipp and Schmallegger, Max and Gescheidt-Demner, Georg and Fischer, Roland and Freunberger, Stefan Alexander and Kern, Wolfgang and Spirk, Stefan}, publisher = {CCDC}, title = {{CCDC 1991959: Experimental Crystal Structure Determination}}, doi = {10.5517/ccdc.csd.cc24vsrk}, year = {2020}, } @misc{9798, abstract = {Fitness interactions between mutations can influence a population’s evolution in many different ways. While epistatic effects are difficult to measure precisely, important information is captured by the mean and variance of log fitnesses for individuals carrying different numbers of mutations. We derive predictions for these quantities from a class of simple fitness landscapes, based on models of optimizing selection on quantitative traits. We also explore extensions to the models, including modular pleiotropy, variable effect sizes, mutational bias and maladaptation of the wild type. We illustrate our approach by reanalysing a large dataset of mutant effects in a yeast snoRNA. Though characterized by some large epistatic effects, these data give a good overall fit to the non-epistatic null model, suggesting that epistasis might have limited influence on the evolutionary dynamics in this system. We also show how the amount of epistasis depends on both the underlying fitness landscape and the distribution of mutations, and so is expected to vary in consistent ways between new mutations, standing variation and fixed mutations.}, author = {Fraisse, Christelle and Welch, John J.}, publisher = {Royal Society of London}, title = {{Simulation code for Fig S2 from the distribution of epistasis on simple fitness landscapes}}, doi = {10.6084/m9.figshare.7957472.v1}, year = {2020}, }