TY - JOUR
AB - We propose a complete process for designing, simulating, and fabricating synthetic skin for an animatronics character that mimics the face of a given subject and its expressions. The process starts with measuring the elastic properties of a material used to manufacture synthetic soft tissue. Given these measurements we use physicsbased simulation to predict the behavior of a face when it is driven by the underlying robotic actuation. Next, we capture 3D facial expressions for a given target subject. As the key component of our process, we present a novel optimization scheme that determines the shape of the synthetic skin as well as the actuation parameters that provide the best match to the target expressions. We demonstrate this computational skin design by physically cloning a real human face onto an animatronics figure.
AU - Bernd Bickel
AU - Kaufmann, Peter
AU - Skouras, Mélina
AU - Thomaszewski, Bernhard
AU - Bradley, Derek J
AU - Beeler, Thabo
AU - Jackson, Philip V
AU - Marschner, Steve
AU - Matusik, Wojciech
AU - Groß, Markus S
ID - 2102
IS - 4
JF - ACM Transactions on Graphics
TI - Physical face cloning
VL - 31
ER -
TY - JOUR
AB - Although facial hair plays an important role in individual expression, facial-hair reconstruction is not addressed by current facecapture systems. Our research addresses this limitation with an algorithm that treats hair and skin surface capture together in a coupled fashion so that a high-quality representation of hair fibers as well as the underlying skin surface can be reconstructed. We propose a passive, camera-based system that is robust against arbitrary motion since all data is acquired within the time period of a single exposure. Our reconstruction algorithm detects and traces hairs in the captured images and reconstructs them in 3D using a multiview stereo approach. Our coupled skin-reconstruction algorithm uses information about the detected hairs to deliver a skin surface that lies underneath all hairs irrespective of occlusions. In dense regions like eyebrows, we employ a hair-synthesis method to create hair fibers that plausibly match the image data. We demonstrate our scanning system on a number of individuals and show that it can successfully reconstruct a variety of facial-hair styles together with the underlying skin surface.
AU - Beeler, Thabo
AU - Bernd Bickel
AU - Noris, Gioacchino
AU - Beardsley, Paul A
AU - Marschner, Steve
AU - Sumner, Robert W
AU - Groß, Markus S
ID - 2103
IS - 4
JF - ACM Transactions on Graphics
TI - Coupled 3D reconstruction of sparse facial hair and skin
VL - 31
ER -
TY - CONF
AB - In recent years, various methods have been introduced to exploit pre-recorded data to improve the performance and/or realism of dynamic deformations, but their differences and similarities have not been adequately analyzed or discussed. So far, the proposed methods have been explored mainly in the research context. They have not been adopted by the computer graphics industry. This course bridges the gap between research labs and industry to present a unifying theory and understanding of data-driven methods for dynamic deformations that may inspire development of novel solutions. It focuses on application of data-driven methods to three areas of computer animation: dynamic deformation of faces, soft volumetric tissue, and cloth. And it describes how to approach these challenges in a data-driven manner, classifies the various methods, and demonstrates how data-driven methods can work in other settings.
AU - Otaduy, Miguel A
AU - Bernd Bickel
AU - Bradley, Derek J
AU - Wang, Huamin
ID - 2104
TI - Data-driven simulation methods in computer graphics: Cloth, tissue and faces
ER -
TY - CONF
AU - Skouras, Mélina
AU - Thomaszewski, Bernhard
AU - Bernd Bickel
AU - Groß, Markus S
ID - 2105
IS - 2
TI - Computational design of rubber balloons
VL - 31
ER -
TY - CONF
AB - Progress in cloth simulation for computer animation and apparel design has led to a multitude of deformation models, each with its own way of relating geometry, deformation, and forces. As simulators improve, differences between these models become more important, but it is difficult to choose a model and a set of parameters to match a given real material simply by looking at simulation results. This paper provides measurement and fitting methods that allow nonlinear models to be fit to the observed deformation of a particular cloth sample. Unlike standard textile testing, our system measures complex 3D deformations of a sheet of cloth, not just one-dimensional force-displacement curves, so it works under a wider range of deformation conditions. The fitted models are then evaluated by comparison to measured deformations with motions very different from those used for fitting.
AU - Miguel, Eder
AU - Bradley, Derek J
AU - Thomaszewski, Bernhard
AU - Bernd Bickel
AU - Matusik, Wojciech
AU - Otaduy, Miguel A
AU - Marschner, Steve
ID - 2106
IS - 2
TI - Data-driven estimation of cloth simulation models
VL - 31
ER -
TY - JOUR
AB - We consider a class of stochastic PDEs of Burgers type in spatial dimension 1, driven by space–time white noise. Even though it is well known that these equations are well posed, it turns out that if one performs a spatial discretization of the nonlinearity in the “wrong” way, then the sequence of approximate equations does converge to a limit, but this limit exhibits an additional correction term. This correction term is proportional to the local quadratic cross-variation (in space) of the gradient of the conserved quantity with the solution itself. This can be understood as a consequence of the fact that for any fixed time, the law of the solution is locally equivalent to Wiener measure, where space plays the role of time. In this sense, the correction term is similar to the usual Itô–Stratonovich correction term that arises when one considers different temporal discretizations of stochastic ODEs.
AU - Hairer, Martin M
AU - Jan Maas
ID - 2125
IS - 4
JF - Annals of Probability
TI - A spatial version of the Itô-Stratonovich correction
VL - 40
ER -
TY - JOUR
AB - We study a new notion of Ricci curvature that applies to Markov chains on discrete spaces. This notion relies on geodesic convexity of the entropy and is analogous to the one introduced by Lott, Sturm, and Villani for geodesic measure spaces. In order to apply to the discrete setting, the role of the Wasserstein metric is taken over by a different metric, having the property that continuous time Markov chains are gradient flows of the entropy. Using this notion of Ricci curvature we prove discrete analogues of fundamental results by Bakry–Émery and Otto–Villani. Further, we show that Ricci curvature bounds are preserved under tensorisation. As a special case we obtain the sharp Ricci curvature lower bound for the discrete hypercube.
AU - Erbar, Matthias
AU - Jan Maas
ID - 2127
IS - 3
JF - Archive for Rational Mechanics and Analysis
TI - Ricci curvature of finite Markov chains via convexity of the entropy
VL - 206
ER -
TY - JOUR
AB - We introduce a technique for handling Whitney decompositions in Gaussian harmonic analysis and apply it to the study of Gaussian analogues of the classical tent spaces T 1,q of Coifman–Meyer–Stein.
AU - Jan Maas
AU - van Neerven, Jan M
AU - Portal, Pierre
ID - 2128
IS - 2
JF - Arkiv för Matematik
TI - Whitney coverings and the tent spaces T 1,q (γ) for the Gaussian measure
VL - 50
ER -
TY - JOUR
AU - Mikhail Lemeshko
AU - Krems, Roman V
AU - Weimer, Hendrik A
ID - 2151
IS - 4
JF - Physical Review Letters
TI - Erratum: Nonadiabatic preparation of spin crystals with ultracold polar molecules
VL - 109
ER -
TY - JOUR
AB - We study the growth dynamics of ordered structures of strongly interacting polar molecules in optical lattices. Using a dipole blockade of microwave excitations, we map the system onto an interacting spin-1/2 model possessing ground states with crystalline order, and describe a way to prepare these states by nonadiabatically driving the transitions between molecular rotational levels. The proposed technique bypasses the need to cross a phase transition and allows for the creation of ordered domains of considerably larger size compared to approaches relying on adiabatic preparation.
AU - Mikhail Lemeshko
AU - Krems, Roman V
AU - Weimer, Hendrik
ID - 2201
IS - 3
JF - Physical Review Letters
TI - Nonadiabatic preparation of spin crystals with ultracold polar molecules
VL - 109
ER -
TY - JOUR
AB - We propose a method for sensitive parallel detection of low-frequency electromagnetic fields based on the fine structure interactions in paramagnetic polar molecules. Compared to the recently implemented scheme employing ultracold 87Rb atoms by Böhi, the technique based on molecules offers a 100-fold higher sensitivity, the possibility to measure both the electric and magnetic field components, and a probe of a wide range of frequencies from the dc limit to the THz regime.
AU - Alyabyshev, Sergey V
AU - Mikhail Lemeshko
AU - Krems, Roman V
ID - 2202
IS - 1
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Sensitive imaging of electromagnetic fields with paramagnetic polar molecules
VL - 86
ER -
TY - JOUR
AB - We show that the electric dipole-dipole interaction between a pair of polar molecules undergoes an all-out transformation when superimposed by a far-off-resonant optical field. The combined interaction potential becomes tunable by variation of wavelength, polarisation and intensity of the optical field and its dependence on the intermolecular separation exhibits a crossover from an inverse-power to an oscillating behaviour. The ability thereby offered to control molecular interactions opens up avenues toward the creation and manipulation of novel phases of ultracold polar gases among whose characteristics is a long-range entanglement of the dipoles' mutual orientation. We devised an accurate analytic model of such optical-field-dressed dipole-dipole interaction potentials, which enables a straightforward access to the optical-field parameters required for the design of intermolecular interactions in the laboratory.
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
ID - 2203
IS - 15-16
JF - Molecular Physics
TI - Interaction between polar molecules subject to a far-off-resonant optical field: Entangled dipoles up- or down-holding each other
VL - 110
ER -
TY - JOUR
AB - Carbon has been used widely as the basis of porous cathodes for nonaqueous Li–O2 cells. However, the stability of carbon and the effect of carbon on electrolyte decomposition in such cells are complex and depend on the hydrophobicity/hydrophilicity of the carbon surface. Analyzing carbon cathodes, cycled in Li–O2 cells between 2 and 4 V, using acid treatment and Fenton’s reagent, and combined with differential electrochemical mass spectrometry and FTIR, demonstrates the following: Carbon is relatively stable below 3.5 V (vs Li/Li+) on discharge or charge, especially so for hydrophobic carbon, but is unstable on charging above 3.5 V (in the presence of Li2O2), oxidatively decomposing to form Li2CO3. Direct chemical reaction with Li2O2 accounts for only a small proportion of the total carbon decomposition on cycling. Carbon promotes electrolyte decomposition during discharge and charge in a Li–O2 cell, giving rise to Li2CO3 and Li carboxylates (DMSO and tetraglyme electrolytes). The Li2CO3 and Li carboxylates present at the end of discharge and those that form on charge result in polarization on the subsequent charge. Li2CO3 (derived from carbon and from the electrolyte) as well as the Li carboxylates (derived from the electrolyte) decompose and form on charging. Oxidation of Li2CO3 on charging to ∼4 V is incomplete; Li2CO3 accumulates on cycling resulting in electrode passivation and capacity fading. Hydrophilic carbon is less stable and more catalytically active toward electrolyte decomposition than carbon with a hydrophobic surface. If the Li–O2 cell could be charged at or below 3.5 V, then carbon may be relatively stable, however, its ability to promote electrolyte decomposition, presenting problems for its use in a practical Li–O2 battery. The results emphasize that stable cycling of Li2O2 at the cathode in a Li–O2 cell depends on the synergy between electrolyte and electrode; the stability of the electrode and the electrolyte cannot be considered in isolation.
AU - Ottakam Thotiyl, Muhammed M.
AU - Freunberger, Stefan Alexander
AU - Peng, Zhangquan
AU - Bruce, Peter G.
ID - 7308
IS - 1
JF - Journal of the American Chemical Society
SN - 0002-7863
TI - The carbon electrode in nonaqueous Li–O2 cells
VL - 135
ER -
TY - JOUR
AB - Energy‐storage technologies, including electrical double‐layer capacitors and rechargeable batteries, have attracted significant attention for applications in portable electronic devices, electric vehicles, bulk electricity storage at power stations, and “load leveling” of renewable sources, such as solar energy and wind power. Transforming lithium batteries and electric double‐layer capacitors requires a step change in the science underpinning these devices, including the discovery of new materials, new electrochemistry, and an increased understanding of the processes on which the devices depend. The Review will consider some of the current scientific issues underpinning lithium batteries and electric double‐layer capacitors.
AU - Choi, Nam-Soon
AU - Chen, Zonghai
AU - Freunberger, Stefan Alexander
AU - Ji, Xiulei
AU - Sun, Yang-Kook
AU - Amine, Khalil
AU - Yushin, Gleb
AU - Nazar, Linda F.
AU - Cho, Jaephil
AU - Bruce, Peter G.
ID - 7309
IS - 40
JF - Angewandte Chemie International Edition
SN - 1433-7851
TI - Challenges facing Lithium batteries and electrical double-layer capacitors
VL - 51
ER -
TY - JOUR
AB - The rechargeable nonaqueous lithium-air (Li-O2) battery is receiving a great deal of interest because, theoretically, its specific energy far exceeds the best that can be achieved with lithium-ion cells. Operation of the rechargeable Li-O2 battery depends critically on repeated and highly reversible formation/decomposition of lithium peroxide (Li2O2) at the cathode upon cycling. Here, we show that this process is possible with the use of a dimethyl sulfoxide electrolyte and a porous gold electrode (95% capacity retention from cycles 1 to 100), whereas previously only partial Li2O2 formation/decomposition and limited cycling could occur. Furthermore, we present data indicating that the kinetics of Li2O2 oxidation on charge is approximately 10 times faster than on carbon electrodes.
AU - Peng, Z.
AU - Freunberger, Stefan Alexander
AU - Chen, Y.
AU - Bruce, P. G.
ID - 7310
IS - 6094
JF - Science
SN - 0036-8075
TI - A reversible and higher-rate Li-O2 battery
VL - 337
ER -
TY - JOUR
AB - Stability of the electrolyte toward reduced oxygen species generated at the cathode is a crucial challenge for the rechargeable nonaqueous Li–O2 battery. Here, we investigate dimethylformamide as the basis of an electrolyte. Although reactions at the O2 cathode on the first discharge–charge cycle are dominated by reversible Li2O2 formation/decomposition, there is also electrolyte decomposition, which increases on cycling. The products of decomposition at the cathode on discharge are Li2O2, Li2CO3, HCO2Li, CH3CO2Li, NO, H2O, and CO2. Li2CO3 accumulates in the electrode with cycling. The stability of dimethylformamide toward reduced oxygen species is insufficient for its use in the rechargeable nonaqueous Li–O2 battery.
AU - Chen, Yuhui
AU - Freunberger, Stefan Alexander
AU - Peng, Zhangquan
AU - Bardé, Fanny
AU - Bruce, Peter G.
ID - 7311
IS - 18
JF - Journal of the American Chemical Society
SN - 0002-7863
TI - Li–O2 battery with a dimethylformamide electrolyte
VL - 134
ER -
TY - CONF
AB - Decades of research in distributed computing have led to a variety of perspectives on what it means for a concurrent algorithm to be efficient, depending on model assumptions, progress guarantees, and complexity metrics. It is therefore natural to ask whether one could compose algorithms that perform efficiently under different conditions, so that the composition preserves the performance of the original components when their conditions are met. In this paper, we evaluate the cost of composing shared-memory algorithms. First, we formally define the notion of safely composable algorithms and we show that every sequential type has a safely composable implementation, as long as enough state is transferred between modules. Since such generic implementations are inherently expensive, we present a more general light-weight specification that allows the designer to transfer very little state between modules, by taking advantage of the semantics of the implemented object. Using this framework, we implement a composed longlived test-and-set object, with the property that each of its modules is asymptotically optimal with respect to the progress condition it ensures, while the entire implementation only uses objects with consensus number at most two. Thus, we show that the overhead of composition can be negligible in the case of some important shared-memory abstractions.
AU - Alistarh, Dan-Adrian
AU - Guerraoui, Rachid
AU - Kuznetsov, Petr
AU - Losa, Giuliano
ID - 762
TI - On the cost of composing shared-memory algorithms
ER -
TY - CONF
AB - Renaming is a fundamental problem in distributed computing, in which a set of n processes need to pick unique names from a namespace of limited size. In this paper, we present the first early-deciding upper bounds for synchronous renaming, in which the running time adapts to the actual number of failures f in the execution. We show that, surprisingly, renaming can be solved in constant time if the number of failures f is limited to O(√n), while for general f ≤ n - 1 renaming can always be solved in O(log f) communication rounds. In the wait-free case, i.e. for f = n - 1, our upper bounds match the Ω(log n) lower bound of Chaudhuri et al. [13].
AU - Alistarh, Dan-Adrian
AU - Attiya, Hagit
AU - Guerraoui, Rachid
AU - Travers, Corentin
ID - 763
TI - Early deciding synchronous renaming in O(log f) rounds or less
VL - 7355 LNCS
ER -
TY - JOUR
AB - Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal results in distributed computing. In synchronous networks, too, the complexity of set agreement has been a significant research challenge that has now been resolved. Real systems, however, are neither purely synchronous nor purely asynchronous. Rather, they tend to alternate between periods of synchrony and periods of asynchrony. Nothing specific is known about the complexity of set agreement in such a "partially synchronous" setting. In this paper, we address this challenge, presenting the first (asymptotically) tight bound on the complexity of set agreement in such systems. We introduce a novel technique for simulating, in a fault-prone asynchronous shared memory, executions of an asynchronous and failure-prone message-passing system in which some fragments appear synchronous to some processes. We use this simulation technique to derive a lower bound on the round complexity of set agreement in a partially synchronous system by a reduction from asynchronous wait-free set agreement. Specifically, we show that every set agreement protocol requires at least $\lfloor\frac t k \rfloor + 2$ synchronous rounds to decide. We present an (asymptotically) matching algorithm that relies on a distributed asynchrony detection mechanism to decide as soon as possible during periods of synchrony. From these two results, we derive the size of the minimal window of synchrony needed to solve set agreement. By relating synchronous, asynchronous and partially synchronous environments, our simulation technique is of independent interest. In particular, it allows us to obtain a new lower bound on the complexity of early deciding k-set agreement complementary to that of Gafni et al. (in SIAM J. Comput. 40(1):63-78, 2011), and to re-derive the combinatorial topology lower bound of Guerraoui et al. (in Theor. Comput. Sci. 410(6-7):570-580, 2009) in an algorithmic way.
AU - Alistarh, Dan-Adrian
AU - Gilbert, Seth
AU - Guerraoui, Rachid
AU - Travers, Corentin
ID - 764
IS - 1-2
JF - Algorithmica (New York)
TI - Of choices, failures and asynchrony: the many faces of set agreement
VL - 62
ER -
TY - CONF
AB - Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key building block for various distributed algorithms. In this paper, we break new ground on this classic problem: we introduce the To-Do Tree concurrent data structure, which improves on the best known randomized and deterministic upper bounds. In the presence of an adaptive adversary, the randomized To-Do Tree algorithm has O(m + p log p log2 m) work complexity. We then show that there exists a deterministic variant of the To-Do Tree algorithm with work complexity O(m + p log5 m log2 max(m, p)). For all values of m and p, our algorithms are within log factors of the Ω(m + p log p) lower bound for this problem. The key technical ingredient in our results is a new approach for analyzing concurrent executions against a strong adaptive scheduler. This technique allows us to handle the complex dependencies between the processes' coin flips and their scheduling, and to tightly bound the work needed to perform subsets of the tasks.
AU - Alistarh, Dan-Adrian
AU - Bender, Michael
AU - Gilbert, Seth
AU - Guerraoui, Rachid
ID - 766
TI - How to allocate tasks asynchronously
ER -
TY - JOUR
AB - Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficiently transform an algorithm that relies on synchronous timing into an algorithm that tolerates asynchronous executions. We introduce a transformation technique from synchronous algorithms to indulgent algorithms (Guerraoui, in PODC, pp. 289-297, 2000), which induces only a constant overhead in terms of time complexity in well-behaved executions. Our technique is based on a new abstraction we call an asynchrony detector, which the participating processes implement collectively. The resulting transformation works for the class of colorless distributed tasks, including consensus and set agreement. Interestingly, we also show that our technique is relevant for colored tasks, by applying it to the renaming problem, to obtain the first indulgent renaming algorithm.
AU - Alistarh, Dan-Adrian
AU - Gilbert, Seth
AU - Guerraoui, Rachid
AU - Travers, Corentin
ID - 767
IS - 4
JF - Theory of Computing Systems
TI - Generating Fast Indulgent Algorithms
VL - 51
ER -
TY - JOUR
AB - Female mate choice acts as an important evolutionary force, yet the influence of the environment on both its expression and the selective pressures acting upon it remains unknown. We found consistent heritable differences between females in their choice of mate based on ornament size during a 25‐year study of a population of collared flycatchers. However, the fitness consequences of mate choice were dependent on environmental conditions experienced whilst breeding. Females breeding with highly ornamented males experienced high relative fitness during dry summer conditions, but low relative fitness during wetter years. Our results imply that sexual selection within a population can be highly variable and dependent upon the prevailing weather conditions experienced by individuals.
AU - Robinson, Matthew Richard
AU - Sander van Doorn, G.
AU - Gustafsson, Lars
AU - Qvarnström, Anna
ID - 7748
IS - 6
JF - Ecology Letters
SN - 1461-023X
TI - Environment-dependent selection on mate choice in a natural population of birds
VL - 15
ER -
TY - JOUR
AB - Although studies on laboratory species and natural populations of vertebrates have shown reproduction to impair later performance, little is known of the age‐specific associations between reproduction and survival, and how such findings apply to the ageing of large, long‐lived species. Herein we develop a framework to examine population‐level patterns of reproduction and survival across lifespan in long‐lived organisms, and decompose those changes into individual‐level effects, and the effects of age‐specific trade‐offs between fitness components. We apply this to an extensive longitudinal dataset on female semi‐captive Asian timber elephants (Elephas maximus) and report the first evidence of age‐specific fitness declines that are driven by age‐specific associations between fitness components in a long‐lived mammal. Associations between reproduction and survival are positive in early life, but negative in later life with up to 71% of later‐life survival declines associated with investing in the production of offspring within this population of this critically endangered species.
AU - Robinson, Matthew Richard
AU - Mar, Khyne U
AU - Lummaa, Virpi
ID - 7749
IS - 3
JF - Ecology Letters
SN - 1461-023X
TI - Senescence and age-specific trade-offs between reproduction and survival in female Asian elephants
VL - 15
ER -
TY - JOUR
AB - We present an analysis of finite-size effects in jammed packings of N soft, frictionless spheres at zero temperature. There is a 1/N correction to the discrete jump in the contact number at the transition so that jammed packings exist only above isostaticity. As a result, the canonical power-law scalings of the contact number and elastic moduli break down at low pressure. These quantities exhibit scaling collapse with a nontrivial scaling function, demonstrating that the jamming transition can be considered a phase transition. Scaling is achieved as a function of N in both two and three dimensions, indicating an upper critical dimension of 2.
AU - Goodrich, Carl Peter
AU - Liu, Andrea J.
AU - Nagel, Sidney R.
ID - 7776
IS - 9
JF - Physical Review Letters
SN - 0031-9007
TI - Finite-size scaling at the jamming transition
VL - 109
ER -
TY - JOUR
AB - Background: Characterizing root system architecture (RSA) is essential to understanding the development and function of vascular plants. Identifying RSA-associated genes also represents an underexplored opportunity for crop improvement. Software tools are needed to accelerate the pace at which quantitative traits of RSA are estimated from images of root networks.Results: We have developed GiA Roots (General Image Analysis of Roots), a semi-automated software tool designed specifically for the high-throughput analysis of root system images. GiA Roots includes user-assisted algorithms to distinguish root from background and a fully automated pipeline that extracts dozens of root system phenotypes. Quantitative information on each phenotype, along with intermediate steps for full reproducibility, is returned to the end-user for downstream analysis. GiA Roots has a GUI front end and a command-line interface for interweaving the software into large-scale workflows. GiA Roots can also be extended to estimate novel phenotypes specified by the end-user.Conclusions: We demonstrate the use of GiA Roots on a set of 2393 images of rice roots representing 12 genotypes from the species Oryza sativa. We validate trait measurements against prior analyses of this image set that demonstrated that RSA traits are likely heritable and associated with genotypic differences. Moreover, we demonstrate that GiA Roots is extensible and an end-user can add functionality so that GiA Roots can estimate novel RSA traits. In summary, we show that the software can function as an efficient tool as part of a workflow to move from large numbers of root images to downstream analysis.
AU - Galkovskyi, Taras
AU - Mileyko, Yuriy
AU - Bucksch, Alexander
AU - Moore, Brad
AU - Symonova, Olga
AU - Price, Charles
AU - Topp, Chrostopher
AU - Iyer Pascuzzi, Anjali
AU - Zurek, Paul
AU - Fang, Suqin
AU - Harer, John
AU - Benfey, Philip
AU - Weitz, Joshua
ID - 492
JF - BMC Plant Biology
TI - GiA Roots: Software for the high throughput analysis of plant root system architecture
VL - 12
ER -
TY - JOUR
AB - The BCI competition IV stands in the tradition of prior BCI competitions that aim to provide high quality neuroscientific data for open access to the scientific community. As experienced already in prior competitions not only scientists from the narrow field of BCI compete, but scholars with a broad variety of backgrounds and nationalities. They include high specialists as well as students.The goals of all BCI competitions have always been to challenge with respect to novel paradigms and complex data. We report on the following challenges: (1) asynchronous data, (2) synthetic, (3) multi-class continuous data, (4) sessionto-session transfer, (5) directionally modulated MEG, (6) finger movements recorded by ECoG. As after past competitions, our hope is that winning entries may enhance the analysis methods of future BCIs.
AU - Tangermann, Michael
AU - Müller, Klaus
AU - Aertsen, Ad
AU - Birbaumer, Niels
AU - Braun, Christoph
AU - Brunner, Clemens
AU - Leeb, Robert
AU - Mehring, Carsten
AU - Miller, Kai
AU - Müller Putz, Gernot
AU - Nolte, Guido
AU - Pfurtscheller, Gert
AU - Preissl, Hubert
AU - Schalk, Gerwin
AU - Schlögl, Alois
AU - Vidaurre, Carmen
AU - Waldert, Stephan
AU - Blankertz, Benjamin
ID - 493
JF - Frontiers in Neuroscience
TI - Review of the BCI competition IV
VL - 6
ER -
TY - JOUR
AB - We solve the longstanding open problems of the blow-up involved in the translations, when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic co-Büchi word automaton (NCW) and to a deterministic co-Büchi word automaton (DCW). For the NBW to NCW translation, the currently known upper bound is 2o(nlog n) and the lower bound is 1.5n. We improve the upper bound to n2n and describe a matching lower bound of 2ω(n). For the NBW to DCW translation, the currently known upper bound is 2o(nlog n). We improve it to 2 o(n), which is asymptotically tight. Both of our upper-bound constructions are based on a simple subset construction, do not involve intermediate automata with richer acceptance conditions, and can be implemented symbolically. We continue and solve the open problems of translating nondeterministic Streett, Rabin, Muller, and parity word automata to NCW and to DCW. Going via an intermediate NBW is not optimal and we describe direct, simple, and asymptotically tight constructions, involving a 2o(n) blow-up. The constructions are variants of the subset construction, providing a unified approach for translating all common classes of automata to NCW and DCW. Beyond the theoretical importance of the results, we point to numerous applications of the new constructions. In particular, they imply a simple subset-construction based translation, when possible, of LTL to deterministic Büchi word automata.
AU - Boker, Udi
AU - Kupferman, Orna
ID - 494
IS - 4
JF - ACM Transactions on Computational Logic (TOCL)
TI - Translating to Co-Büchi made tight, unified, and useful
VL - 13
ER -
TY - CONF
AB - An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.
AU - Kruckman, Alex
AU - Rubin, Sasha
AU - Sheridan, John
AU - Zax, Ben
ID - 495
T2 - Proceedings GandALF 2012
TI - A Myhill Nerode theorem for automata with advice
VL - 96
ER -
TY - CONF
AB - We study the expressive power of logical interpretations on the class of scattered trees, namely those with countably many infinite branches. Scattered trees can be thought of as the tree analogue of scattered linear orders. Every scattered tree has an ordinal rank that reflects the structure of its infinite branches. We prove, roughly, that trees and orders of large rank cannot be interpreted in scattered trees of small rank. We consider a quite general notion of interpretation: each element of the interpreted structure is represented by a set of tuples of subsets of the interpreting tree. Our trees are countable, not necessarily finitely branching, and may have finitely many unary predicates as labellings. We also show how to replace injective set-interpretations in (not necessarily scattered) trees by 'finitary' set-interpretations.
AU - Rabinovich, Alexander
AU - Rubin, Sasha
ID - 496
TI - Interpretations in trees with countably many branches
ER -
TY - CONF
AB - One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n 3·m) time as compared to the previous known O(n 6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n·m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm. © Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath.
AU - Chatterjee, Krishnendu
AU - Chaubal, Siddhesh
AU - Kamath, Pritish
ID - 497
TI - Faster algorithms for alternating refinement relations
VL - 16
ER -
TY - JOUR
AB - Understanding patterns and correlates of local adaptation in heterogeneous landscapes can provide important information in the selection of appropriate seed sources for restoration. We assessed the extent of local adaptation of fitness components in 12 population pairs of the perennial herb Rutidosis leptorrhynchoides (Asteraceae) and examined whether spatial scale (0.7-600 km), environmental distance, quantitative (QST) and neutral (FST) genetic differentiation, and size of the local and foreign populations could predict patterns of adaptive differentiation. Local adaptation varied among populations and fitness components. Including all population pairs, local adaptation was observed for seedling survival, but not for biomass, while foreign genotype advantage was observed for reproduction (number of inflorescences). Among population pairs, local adaptation increased with QST and local population size for biomass. QST was associated with environmental distance, suggesting ecological selection for phenotypic divergence. However, low FST and variation in population structure in small populations demonstrates the interaction of gene flow and drift in constraining local adaptation in R. leptorrhynchoides. Our study indicates that for species in heterogeneous landscapes, collecting seed from large populations from similar environments to candidate sites is likely to provide the most appropriate seed sources for restoration.
AU - Pickup, Melinda
AU - Field, David
AU - Rowell, David
AU - Young, Andrew
ID - 498
IS - 8
JF - Evolutionary Applications
TI - Predicting local adaptation in fragmented plant populations: Implications for restoration genetics
VL - 5
ER -
TY - JOUR
AU - Sixt, Michael K
ID - 506
IS - 3
JF - Journal of Cell Biology
TI - Cell migration: Fibroblasts find a new way to get ahead
VL - 197
ER -
TY - GEN
AB - Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and ω-regular objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean-payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two- player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP- hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two- player pushdown games. Finally we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.
AU - Chatterjee, Krishnendu
AU - Velner, Yaron
ID - 5377
SN - 2664-1690
TI - Mean-payoff pushdown games
ER -
TY - GEN
AB - One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm.
AU - Chatterjee, Krishnendu
AU - Chaubal, Siddhesh
AU - Kamath, Pritish
ID - 5378
SN - 2664-1690
TI - Faster algorithms for alternating refinement relations
ER -
TY - GEN
AB - We consider the problem of inference in agraphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can out-perform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.
AU - Korc, Filip
AU - Kolmogorov, Vladimir
AU - Lampert, Christoph
ID - 5396
SN - 2664-1690
TI - Approximating marginals using discrete energy minimization
ER -
TY - GEN
AB - This document is created as a part of the project “Repository for Research Data on IST Austria”. It summarises the actual state of research data at IST Austria, based on survey results. It supports the choice of appropriate software, which would best fit the requirements of their users, the researchers.
AU - Porsche, Jana
ID - 5398
TI - Actual state of research data @ ISTAustria
ER -
TY - CHAP
AU - Gupta, Ashutosh
ID - 5745
SN - 0302-9743
T2 - Automated Technology for Verification and Analysis
TI - Improved Single Pass Algorithms for Resolution Proof Reduction
VL - 7561
ER -
TY - JOUR
AB - Canny's edge detection algorithm is a classical and robust method for edge detection in gray-scale images. The two
significant features of this method are introduction of NMS (Non-Maximum Suppression) and double thresholding of
the gradient image. Due to poor illumination, the region boundaries in an image may become vague, creating
uncertainties in the gradient image. In this paper, we have proposed an algorithm based on the concept of type-2 fuzzy sets to handle uncertainties that automatically selects the threshold values needed to segment the gradient image using classical Canny’s edge detection algorithm. The results show that our algorithm works significantly well on different benchmark images as well as medical images (hand radiography images).
AU - Biswas, Ranita
AU - Sil, Jaya
ID - 5839
JF - Procedia Technology
SN - 2212-0173
TI - An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets
VL - 4
ER -
TY - JOUR
AB - The human Mediator complex controls RNA polymerase II (pol II) function in ways that remain incompletely understood. Activator-Mediator binding alters Mediator structure, and these activator-induced structural shifts appear to play key roles in regulating transcription. A recent cryo-electron microscopy (EM) analysis revealed that pol II adopted a stable orientation within a Mediator-pol II-TFIIF assembly in which Mediator was bound to the activation domain of viral protein 16 (VP16). Whereas TFIIF was shown to be important for orienting pol II within this assembly, the potential role of the activator was not assessed. To determine how activator binding might affect pol II orientation, we isolated human Mediator-pol II-TFIIF complexes in which Mediator was not bound to an activator. Cryo-EM analysis of this assembly, coupled with pol II crystal structure docking, revealed that pol II binds Mediator at the same general location; however, in contrast to VP16-bound Mediator, pol II does not appear to stably orient in the absence of an activator. Variability in pol II orientation might be important mechanistically, perhaps to enable sense and antisense transcription at human promoters. Because Mediator interacts extensively with pol II, these results suggest that Mediator structural shifts induced by activator binding help stably orient pol II prior to transcription initiation.
AU - Bernecky, Carrie A
AU - Taatjes, Dylan
ID - 596
IS - 5
JF - Journal of Molecular Biology
TI - Activator-mediator binding stabilizes RNA polymerase II orientation within the human mediator-RNA polymerase II-TFIIF assembly
VL - 417
ER -
TY - JOUR
AB - Tonic receptors convey stimulus duration and intensity and are implicated in homeostatic control. However, how tonic homeostatic signals are generated and how they reconfigure neural circuits and modify animal behavior is poorly understood. Here we show that Caenorhabditis elegans O2-sensing neurons are tonic receptors that continuously signal ambient [O2] to set the animal's behavioral state. Sustained signaling relied on a Ca2+ relay involving L-type voltage-gated Ca2+ channels, the ryanodine and the inositol-1,4,5-trisphosphate receptors. Tonic activity evoked continuous neuropeptide release, which helps elicit the enduring behavioral state associated with high [O2]. Sustained O2 receptor signaling was propagated to downstream neural circuits, including the hub interneuron RMG. O2 receptors evoked similar locomotory states at particular O2 concentrations, regardless of previous d[O2]/dt. However, a phasic component of the URX receptors' response to high d[O2]/dt, as well as tonic-to-phasic transformations in downstream interneurons, enabled transient reorientation movements shaped by d[O2]/dt. Our results highlight how tonic homeostatic signals can generate both transient and enduring behavioral change.
AU - Busch, Karl Emanuel
AU - Laurent, Patrick
AU - Soltesz, Zoltan
AU - Murphy, Robin Joseph
AU - Faivre, Olivier
AU - Hedwig, Berthold
AU - Thomas, Martin
AU - Smith, Heather L
AU - de Bono, Mario
ID - 6136
IS - 4
JF - Nature Neuroscience
SN - 1097-6256
TI - Tonic signaling from O2 sensors sets neural circuit activity and behavioral state
VL - 15
ER -
TY - JOUR
AB - First we note that the best polynomial approximation to vertical bar x vertical bar on the set, which consists of an interval on the positive half-axis and a point on the negative half-axis, can be given by means of the classical Chebyshev polynomials. Then we explore the cases when a solution of the related problem on two intervals can be given in elementary functions.
AU - Pausinger, Florian
ID - 6588
IS - 1
JF - Journal of Mathematical Physics, Analysis, Geometry
SN - 1812-9471
TI - Elementary solutions of the Bernstein problem on two intervals
VL - 8
ER -
TY - CONF
AB - This paper proposes a novel cooperative approach for two-hop amplify-and-forward (A&F) relaying that exploits both the signal forwarded by the relay and the one directly transmitted by the source in impulse-radio ultra-wideband (IR-UWB) systems. Specifically, we focus on a non-coherent setup employing a double-differential encoding scheme at the source node and a single differential demodulation at the relay and destination. The log-likelihood ratio based decision rule is derived at the destination node. A semi-analytical power allocation strategy is presented by evaluating a closed-form expression for the effective signal to noise ratio (SNR) at the destination, which is maximized by exhaustive search. Numerical simulations show that the proposed system outperforms both the direct transmission with single differential encoding and the non-cooperative multi-hop approach in different scenarios.
AU - Mondelli, Marco
AU - Zhou, Qi
AU - Ma, Xiaoli
AU - Lottici, Vincenzo
ID - 6746
SN - 1520-6149
T2 - 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
TI - A cooperative approach for amplify-and-forward differential transmitted reference IR-UWB relay systems
ER -
TY - JOUR
AB - The Seebeck coefficients, electrical resistivities, total thermal conductivities, and magnetization are reported for temperatures between 5 and 350 K for n-type Bi0.88Sb0.12 nano-composite alloys made by Ho-doping at the 0, 1, and 3 % atomic levels. The alloys were prepared using a dc hot-pressing method, and are shown to be single phase for both Ho contents with grain sizes on the average of 900 nm. We find the parent compound has a maximum of ZT = 0.28 at 231 K, while doping 1 % Ho increases the maximum ZT to 0.31 at 221 K and the 3 % doped sample suppresses the maximum ZT = 0.24 at a temperature of 260 K.
AU - Lukas, K. C.
AU - Joshi, G.
AU - Modic, Kimberly A
AU - Ren, Z. F.
AU - Opeil, C. P.
ID - 7074
IS - 15
JF - Journal of Materials Science
SN - 0022-2461
TI - Thermoelectric properties of Ho-doped Bi0.88Sb0.12
VL - 47
ER -
TY - CONF
AB - Software model checking, as an undecidable problem, has three possible outcomes: (1) the program satisfies the specification, (2) the program does not satisfy the specification, and (3) the model checker fails. The third outcome usually manifests itself in a space-out, time-out, or one component of the verification tool giving up; in all of these failing cases, significant computation is performed by the verification tool before the failure, but no result is reported. We propose to reformulate the model-checking problem as follows, in order to have the verification tool report a summary of the performed work even in case of failure: given a program and a specification, the model checker returns a condition Ψ - usually a state predicate - such that the program satisfies the specification under the condition Ψ - that is, as long as the program does not leave the states in which Ψ is satisfied. In our experiments, we investigated as one major application of conditional model checking the sequential combination of model checkers with information passing. We give the condition that one model checker produces, as input to a second conditional model checker, such that the verification problem for the second is restricted to the part of the state space that is not covered by the condition, i.e., the second model checker works on the problems that the first model checker could not solve. Our experiments demonstrate that repeated application of conditional model checkers, passing information from one model checker to the next, can significantly improve the verification results and performance, i.e., we can now verify programs that we could not verify before.
AU - Beyer, Dirk
AU - Henzinger, Thomas A
AU - Keremoglu, Mehmet
AU - Wendler, Philipp
ID - 1384
T2 - Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering
TI - Conditional model checking: A technique to pass information between verifiers
ER -
TY - JOUR
AB - Given a possibly reducible and non-reduced spectral cover π: X → C over a smooth projective complex curve C we determine the group of connected components of the Prym variety Prym(X/C). As an immediate application we show that the finite group of n-torsion points of the Jacobian of C acts trivially on the cohomology of the twisted SL n-Higgs moduli space up to the degree which is predicted by topological mirror symmetry. In particular this yields a new proof of a result of Harder-Narasimhan, showing that this finite group acts trivially on the cohomology of the twisted SL n stable bundle moduli space.
AU - Tamas Hausel
AU - Pauly, Christian
ID - 1471
IS - 3
JF - Geometry and Topology
TI - Prym varieties of spectral covers
VL - 16
ER -
TY - JOUR
AB - For G = GL 2, PGL 2, SL 2 we prove that the perverse filtration associated with the Hitchin map on the rational cohomology of the moduli space of twisted G-Higgs bundles on a compact Riemann surface C agrees with the weight filtration on the rational cohomology of the twisted G character variety of C when the cohomologies are identified via non-Abelian Hodge theory. The proof is accomplished by means of a study of the topology of the Hitchin map over the locus of integral spectral curves.
AU - De Cataldo, Mark A
AU - Tamas Hausel
AU - Migliorini, Luca
ID - 1472
IS - 3
JF - Annals of Mathematics
TI - Topology of hitchin systems and Hodge theory of character varieties: The case A 1
VL - 175
ER -
TY - JOUR
AB - In July, 2011, a 32-year-old man presented with thoracic pain radiating to the left arm and upper dorsum, shortness of breath, and palpitations. He had had upper back tension for 6 months. Medical history was unremarkable apart from moderate nicotine use (two pack-years). Echocardiography, electrocardiography, and laboratory tests were unremarkable, excluding a cardiac event. CT of the chest after chest radiography showed a large bulla of 16 cm diameter in the right hemithorax (figure A). We did not detect radiological evidence of underlying pulmonary disease. The bulla wall was unremarkable and no structures were seen within the bulla.
AU - Erne, Barbara
AU - Graff, Mareike
AU - Klemm, Wolfram
AU - Danzl, Johann G
AU - Leschber, Gunda
ID - 1055
IS - 9849
JF - The Lancet
TI - Bulla in the lung
VL - 380
ER -
TY - JOUR
AB - We prepare and study a metastable attractive Mott-insulator state formed with bosonic atoms in a three-dimensional optical lattice. Starting from a Mott insulator with Cs atoms at weak repulsive interactions, we use a magnetic Feshbach resonance to tune the interactions to large attractive values and produce a metastable state pinned by attractive interactions with a lifetime on the order of 10 s. We probe the (de)excitation spectrum via lattice modulation spectroscopy, measuring the interaction dependence of two- and three-body bound-state energies. As a result of increased on-site three-body loss we observe resonance broadening and suppression of tunneling processes that produce three-body occupation.
AU - Mark, Manfred
AU - Haller, Elmar
AU - Lauber, Katharina
AU - Danzl, Johann G
AU - Janisch, Alexander
AU - Büchler, Hans
AU - Daley, Andrew
AU - Nägerl, Hanns
ID - 1056
IS - 21
JF - Physical Review Letters
TI - Preparation and spectroscopy of a metastable mott-insulator state with attractive interactions
VL - 108
ER -
TY - JOUR
AB - Although liquids typically flow around intruding objects, a counterintuitive phenomenon occurs in dense suspensions of micrometre-sized particles: they become liquid-like when perturbed lightly, but harden when driven strongly. Rheological experiments have investigated how such thickening arises under shear, and linked it to hydrodynamic interactions or granular dilation. However, neither of these mechanisms alone can explain the ability of suspensions to generate very large, positive normal stresses under impact. To illustrate the phenomenon, such stresses can be large enough to allow a person to run across a suspension without sinking, and far exceed the upper limit observed under shear or extension. Here we show that these stresses originate from an impact-generated solidification front that transforms an initially compressible particle matrix into a rapidly growing jammed region, ultimately leading to extraordinary amounts of momentum absorption. Using high-speed videography, embedded force sensing and X-ray imaging, we capture the detailed dynamics of this process as it decelerates a metal rod hitting a suspension of cornflour (cornstarch) in water. We develop a model for the dynamic solidification and its effect on the surrounding suspension that reproduces the observed behaviour quantitatively. Our findings suggest that prior interpretations of the impact resistance as dominated by shear thickening need to be revisited.
AU - Waitukaitis, Scott R
AU - Jaeger, Heinrich
ID - 113
IS - 7406
JF - Nature
TI - Impact-activated solidification of dense suspensions via dynamic jamming fronts
VL - 487
ER -
TY - JOUR
AB - We report on an investigation of the solidification of a cornstarch and water suspension during normal impact on its surface. We find that a finite time after impact, the suspension displays characteristics reminiscent of a solid, including localized stress transmission, the development of a yield stress, and some elastic energy storage. The time dependence of these characteristics depends on the thickness of the cornstarch layer, showing that the solidification is a dynamic process driven by the impacting object. These findings confirm previous speculations that rapidly applied normal stress transforms the normally fluid-like suspension into a temporarily jammed solid and draw a clear distinction between the effects of normal stress and shear stress in dense suspensions.
AU - Waitukaitis, Scott R
AU - Jaeger, Heinrich
ID - 114
IS - 1E
JF - Revista Cubana de Fisica
TI - Solidification of a cornstarch and water suspension
VL - 29
ER -