TY - JOUR
AB - The environment changes constantly at various time scales and, in order to survive, species need to keep adapting. Whether these species succeed in avoiding extinction is a major evolutionary question. Using a multilocus evolutionary model of a mutation‐limited population adapting under strong selection, we investigate the effects of the frequency of environmental fluctuations on adaptation. Our results rely on an “adaptive‐walk” approximation and use mathematical methods from evolutionary computation theory to investigate the interplay between fluctuation frequency, the similarity of environments, and the number of loci contributing to adaptation. First, we assume a linear additive fitness function, but later generalize our results to include several types of epistasis. We show that frequent environmental changes prevent populations from reaching a fitness peak, but they may also prevent the large fitness loss that occurs after a single environmental change. Thus, the population can survive, although not thrive, in a wide range of conditions. Furthermore, we show that in a frequently changing environment, the similarity of threats that a population faces affects the level of adaptation that it is able to achieve. We check and supplement our analytical results with simulations.
AU - Trubenova, Barbora
AU - Krejca, Martin
AU - Lehre, Per Kristian
AU - Kötzing, Timo
ID - 6637
IS - 7
JF - Evolution
TI - Surfing on the seascape: Adaptation in a changing environment
VL - 73
ER -
TY - JOUR
AB - The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one.
AU - Silva, André
AU - Arroyo Guevara, Alan M
AU - Richter, Bruce
AU - Lee, Orlando
ID - 6638
IS - 11
JF - Discrete Mathematics
SN - 0012-365X
TI - Graphs with at most one crossing
VL - 342
ER -
TY - CONF
AB - We present a thermodynamically based approach to the design of models for viscoelastic fluids with stress diffusion effect. In particular, we show how to add a stress diffusion term to some standard viscoelastic rate-type models (Giesekus, FENE-P, Johnson–Segalman, Phan-Thien–Tanner and Bautista–Manero–Puig) so that the resulting models with the added stress diffusion term are thermodynamically consistent in the sense that they obey the first and the second law of thermodynamics. We point out the potential applications of the provided thermodynamical background in the study of flows of fluids described by the proposed models.
AU - Dostalík, Mark
AU - Pruša, Vít
AU - Skrivan, Tomas
ID - 6642
T2 - AIP Conference Proceedings
TI - On diffusive variants of some classical viscoelastic rate-type models
VL - 2107
ER -
TY - CONF
AB - We demonstrate robust retention of valley coherence and its control via polariton pseudospin precession through the optical TE-TM splitting in bilayer WS2 microcavity exciton polaritons at room temperature.
AU - Khatoniar, Mandeep
AU - Yama, Nicholas
AU - Ghazaryan, Areg
AU - Guddala, Sriram
AU - Ghaemi, Pouyan
AU - Menon, Vinod
ID - 6646
SN - 9781943580576
T2 - CLEO: Applications and Technology
TI - Room temperature control of valley coherence in bilayer WS2 exciton polaritons
ER -
TY - CONF
AB - The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.
AU - Fulek, Radoslav
AU - Gärtner, Bernd
AU - Kupavskii, Andrey
AU - Valtr, Pavel
AU - Wagner, Uli
ID - 6647
SN - 1868-8969
T2 - 35th International Symposium on Computational Geometry
TI - The crossing Tverberg theorem
VL - 129
ER -
TY - CONF
AB - 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.
AU - Edelsbrunner, Herbert
AU - Virk, Ziga
AU - Wagner, Hubert
ID - 6648
SN - 9783959771047
T2 - 35th International Symposium on Computational Geometry
TI - Topological data analysis in information space
VL - 129
ER -
TY - JOUR
AB - We propose a novel technique for the automatic design of molds to cast highly complex shapes. The technique generates composite, two-piece molds. Each mold piece is made up of a hard plastic shell and a flexible silicone part. Thanks to the thin, soft, and smartly shaped silicone part, which is kept in place by a hard plastic shell, we can cast objects of unprecedented complexity. An innovative algorithm based on a volumetric analysis defines the layout of the internal cuts in the silicone mold part. Our approach can robustly handle thin protruding features and intertwined topologies that have caused previous methods to fail. We compare our results with state of the art techniques, and we demonstrate the casting of shapes with extremely complex geometry.
AU - Alderighi, Thomas
AU - Malomo, Luigi
AU - Giorgi, Daniela
AU - Bickel, Bernd
AU - Cignoni, Paolo
AU - Pietroni, Nico
ID - 6650
IS - 4
JF - ACM Transactions on Graphics
SN - 0730-0301
TI - Volume-aware design of composite molds
VL - 38
ER -
TY - JOUR
AB - In this article a model is described how Open Access definitions can be formed on the basis of objective criteria. The common Open Access definitions such as "gold" and "green" are not exactly defined. This becomes a problem as soon as one begins to measure Open Access, for example if the development of the Open Access share should be monitored. This was discussed in the working group on Open Access Monitoring of the AT2OA project and the present model was developed, which is based on 5 critics with 4 characteristics: location, licence, version, embargo and conditions of the Open Access publication are taken into account. In the meantime, the model has also been tested in practice using R scripts, and the initial results are quite promising.
AU - Danowski, Patrick
ID - 6657
IS - 1
JF - VOEB-Mitteilungen
TI - An Austrian proposal for the classification of Open Access Tuples (COAT) - distinguish different open access types beyond colors
VL - 72
ER -
TY - JOUR
AB - New genes are a major source of novelties, and a disproportionate amount of them are known to show testis expression in later phases of male gametogenesis in different groups such as mammals and plants. Here, we propose that this enhanced expression is a consequence of haploid selection during the latter stages of male gametogenesis. Because emerging adaptive mutations will be fixed faster if their phenotypes are expressed by haploid rather than diploid genotypes, new genes with advantageous functions arising during this unique stage of development have a better chance to become fixed. To test this hypothesis, expression levels of genes of differing evolutionary age were examined at various stages of Drosophila spermatogenesis. We found, consistent with a model based on haploid selection, that new Drosophila genes are both expressed in later haploid phases of spermatogenesis and harbor a significant enrichment of adaptive mutations. Additionally, the observed overexpression of new genes in the latter phases of spermatogenesis was limited to the autosomes. Because all male cells exhibit hemizygous expression for X-linked genes (and therefore effectively haploid), there is no expectation that selection acting on late spermatogenesis will have a different effect on X-linked genes in comparison to initial diploid phases. Together, our proposed hypothesis and the analyzed data suggest that natural selection in haploid cells elucidates several aspects of the origin of new genes by explaining the general prevalence of their testis expression, and a parsimonious solution for new alleles to avoid being lost by genetic drift or pseudogenization.
AU - Raices, Julia
AU - Otto, Paulo
AU - Vibranovski, Maria
ID - 6658
IS - 7
JF - Genome Research
TI - Haploid selection drives new gene male germline expression
VL - 29
ER -
TY - JOUR
AB - Chemical labeling of proteins with synthetic molecular probes offers the possibility to probe the functions of proteins of interest in living cells. However, the methods for covalently labeling targeted proteins using complementary peptide tag-probe pairs are still limited, irrespective of the versatility of such pairs in biological research. Herein, we report the new CysHis tag-Ni(II) probe pair for the specific covalent labeling of proteins. A broad-range evaluation of the reactivity profiles of the probe and the CysHis peptide tag afforded a tag-probe pair with an optimized and high labeling selectivity and reactivity. In particular, the labeling specificity of this pair was notably improved compared to the previously reported one. This pair was successfully utilized for the fluorescence imaging of membrane proteins on the surfaces of living cells, demonstrating its potential utility in biological research.
AU - Zenmyo, Naoki
AU - Tokumaru, Hiroki
AU - Uchinomiya, Shohei
AU - Fuchida, Hirokazu
AU - Tabata, Shigekazu
AU - Hamachi, Itaru
AU - Shigemoto, Ryuichi
AU - Ojida, Akio
ID - 6659
IS - 5
JF - Bulletin of the Chemical Society of Japan
SN - 00092673
TI - Optimized reaction pair of the CysHis tag and Ni(II)-NTA probe for highly selective chemical labeling of membrane proteins
VL - 92
ER -
TY - JOUR
AB - Commercially available full-color 3D printing allows for detailed control of material deposition in a volume, but an exact reproduction of a target surface appearance is hampered by the strong subsurface scattering that causes nontrivial volumetric cross-talk at the print surface. Previous work showed how an iterative optimization scheme based on accumulating absorptive materials at the surface can be used to find a volumetric distribution of print materials that closely approximates a given target appearance.
In this work, we first revisit the assumption that pushing the absorptive materials to the surface results in minimal volumetric cross-talk. We design a full-fledged optimization on a small domain for this task and confirm this previously reported heuristic. Then, we extend the above approach that is critically limited to color reproduction on planar surfaces, to arbitrary 3D shapes. Our method enables high-fidelity color texture reproduction on 3D prints by effectively compensating for internal light scattering within arbitrarily shaped objects. In addition, we propose a content-aware gamut mapping that significantly improves color reproduction for the pathological case of thin geometric features. Using a wide range of sample objects with complex textures and geometries, we demonstrate color reproduction whose fidelity is superior to state-of-the-art drivers for color 3D printers.
AU - Sumin, Denis
AU - Weyrich, Tim
AU - Rittig, Tobias
AU - Babaei, Vahid
AU - Nindel, Thomas
AU - Wilkie, Alexander
AU - Didyk, Piotr
AU - Bickel, Bernd
AU - Křivánek, Jaroslav
AU - Myszkowski, Karol
ID - 6660
IS - 4
JF - ACM Transactions on Graphics
SN - 0730-0301
TI - Geometry-aware scattering compensation for 3D printing
VL - 38
ER -
TY - JOUR
AB - In phase retrieval, we want to recover an unknown signal 𝑥∈ℂ𝑑 from n quadratic measurements of the form 𝑦𝑖=|⟨𝑎𝑖,𝑥⟩|2+𝑤𝑖, where 𝑎𝑖∈ℂ𝑑 are known sensing vectors and 𝑤𝑖 is measurement noise. We ask the following weak recovery question: What is the minimum number of measurements n needed to produce an estimator 𝑥^(𝑦) that is positively correlated with the signal 𝑥? We consider the case of Gaussian vectors 𝑎𝑎𝑖. We prove that—in the high-dimensional limit—a sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For 𝑛≤𝑑−𝑜(𝑑), no estimator can do significantly better than random and achieve a strictly positive correlation. For 𝑛≥𝑑+𝑜(𝑑), a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theoretic arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper bound and lower bound generalize beyond phase retrieval to measurements 𝑦𝑖 produced according to a generalized linear model. As a by-product of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm.
AU - Mondelli, Marco
AU - Montanari, Andrea
ID - 6662
IS - 3
JF - Foundations of Computational Mathematics
TI - Fundamental limits of weak recovery with applications to phase retrieval
VL - 19
ER -
TY - JOUR
AB - Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, we know from two independent works by Schürch and by Bardet et al. that the synthetic channels are partially ordered with respect to degradation. Hence, it is natural to ask whether the partial order can be exploited to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order, we can construct a polar code by computing the reliability of roughly a fraction 1/ log 3/2 N of the synthetic channels. In particular, we prove that N/ log 3/2 N is a lower bound on the number of synthetic channels to be considered and such a bound is tight up to a multiplicative factor log log N. This set of roughly N/ log 3/2 N synthetic channels is universal, in the sense that it allows one to construct polar codes for any W, and it can be identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists of reducing the construction problem to the problem of computing the maximum cardinality of an antichain for a suitable partially ordered set. As such, this method is general, and it can be used to further improve the complexity of the construction problem, in case a refined partial order on the synthetic channels of polar codes is discovered.
AU - Mondelli, Marco
AU - Hassani, Hamed
AU - Urbanke, Rudiger
ID - 6663
IS - 5
JF - IEEE
TI - Construction of polar codes with sublinear complexity
VL - 65
ER -
TY - JOUR
AB - In this paper we discuss three results. The first two concern general sets of positive reach: we first characterize the reach of a closed set by means of a bound on the metric distortion between the distance measured in the ambient Euclidean space and the shortest path distance measured in the set. Secondly, we prove that the intersection of a ball with radius less than the reach with the set is geodesically convex, meaning that the shortest path between any two points in the intersection lies itself in the intersection. For our third result we focus on manifolds with positive reach and give a bound on the angle between tangent spaces at two different points in terms of the reach and the distance between the two points.
AU - Boissonnat, Jean-Daniel
AU - Lieutier, André
AU - Wintraecken, Mathijs
ID - 6671
IS - 1-2
JF - Journal of Applied and Computational Topology
SN - 2367-1726
TI - The reach, metric distortion, geodesic convexity and the variation of tangent spaces
VL - 3
ER -
TY - JOUR
AB - The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in $\mathbb{R}^2$ and on surfaces embedded in $\mathbb{R}^3$ as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points $\mathcal{P}$ in a domain $\Omega$ equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of $\mathcal{P}$ to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in $\Omega$ under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened.
AU - Boissonnat, Jean-Daniel
AU - Rouxel-Labbé, Mael
AU - Wintraecken, Mathijs
ID - 6672
IS - 3
JF - SIAM Journal on Computing
SN - 0097-5397
TI - Anisotropic triangulations via discrete Riemannian Voronoi diagrams
VL - 48
ER -
TY - CONF
AB - Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared state, which gets updated progressively. While the sequential variant of such algorithms usually specifies a fixed (but sometimes random) order in which the tasks should be performed, a standard approach to parallelizing such algorithms is to relax this constraint to allow for out-of-order parallel execution. This is the case for parallel implementations of Dijkstra's single-source shortest-paths (SSSP) algorithm, and for parallel Delaunay mesh triangulation. While many software frameworks parallelize incremental computation in this way, it is still not well understood whether this relaxed ordering approach can still provide any complexity guarantees. In this paper, we address this problem, and analyze the efficiency guarantees provided by a range of incremental algorithms when parallelized via relaxed schedulers. We show that, for algorithms such as Delaunay mesh triangulation and sorting by insertion, schedulers with a maximum relaxation factor of k in terms of the maximum priority inversion allowed will introduce a maximum amount of wasted work of O(łog n poly(k)), where n is the number of tasks to be executed. For SSSP, we show that the additional work is O(poly(k), dmax / wmin), where dmax is the maximum distance between two nodes, and wmin is the minimum such distance. In practical settings where n >> k, this suggests that the overheads of relaxation will be outweighed by the improved scalability of the relaxed scheduler. On the negative side, we provide lower bounds showing that certain algorithms will inherently incur a non-trivial amount of wasted work due to scheduler relaxation, even for relatively benign relaxed schedulers.
AU - Alistarh, Dan-Adrian
AU - Nadiradze, Giorgi
AU - Koval, Nikita
ID - 6673
SN - 9781450361842
T2 - 31st ACM Symposium on Parallelism in Algorithms and Architectures
TI - Efficiency guarantees for parallel incremental algorithms under relaxed schedulers
ER -
TY - CONF
AB - It is impossible to deterministically solve wait-free consensus in an asynchronous system. The classic proof uses a valency argument, which constructs an infinite execution by repeatedly extending a finite execution. We introduce extension-based proofs, a class of impossibility proofs that are modelled as an interaction between a prover and a protocol and that include valency arguments.
Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power.
AU - Alistarh, Dan-Adrian
AU - Aspnes, James
AU - Ellen, Faith
AU - Gelashvili, Rati
AU - Zhu, Leqi
ID - 6676
SN - 9781450367059
T2 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
TI - Why extension-based proofs fail
ER -
TY - CONF
AB - The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.
We show that solving the END−OF−METERED−LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT.
Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n).
AU - Choudhuri, Arka Rai
AU - Hubáček, Pavel
AU - Kamath Hosdurg, Chethan
AU - Pietrzak, Krzysztof Z
AU - Rosen, Alon
AU - Rothblum, Guy N.
ID - 6677
SN - 9781450367059
T2 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019
TI - Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
ER -
TY - THES
AB - The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2.
However, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,
we construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X).
In the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space.
AU - Zhechev, Stephan Y
ID - 6681
SN - 2663-337X
TI - Algorithmic aspects of homotopy theory and embeddability
ER -
TY - JOUR
AB - Sexual dimorphism in morphology, physiology or life history traits is common in dioecious plants at reproductive maturity, but it is typically inconspicuous or absent in juveniles. Although plants of different sexes probably begin to diverge in gene expression both before their reproduction commences and before dimorphism becomes readily apparent, to our knowledge transcriptome-wide differential gene expression has yet to be demonstrated for any angiosperm species.
AU - Cossard, Guillaume
AU - Toups, Melissa A
AU - Pannell, John
ID - 6710
IS - 7
JF - Annals of botany
TI - Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb
VL - 123
ER -
TY - CONF
AB - A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Γ of cost functions, called a language.
Recent breakthrough results have established a complete complexity classification of such classes with respect to language Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Γ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ))) time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm, assuming that SETH holds.
AU - Kolmogorov, Vladimir
ID - 6725
SN - 1868-8969
T2 - 46th International Colloquium on Automata, Languages and Programming
TI - Testing the complexity of a valued CSP language
VL - 132
ER -
TY - CHAP
AB - Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so.
AU - Walter, Michael
ED - Buchmann, J
ED - Nitaj, A
ED - Rachidi, T
ID - 6726
SN - 0302-9743
T2 - Progress in Cryptology – AFRICACRYPT 2019
TI - Sampling the integers with low relative error
VL - 11627
ER -
TY - CONF
AB - We establish connections between the problem of learning a two-layer neural network and tensor decomposition. We consider a model with feature vectors x∈ℝd, r hidden units with weights {wi}1≤i≤r and output y∈ℝ, i.e., y=∑ri=1σ(w𝖳ix), with activation functions given by low-degree polynomials. In particular, if σ(x)=a0+a1x+a3x3, we prove that no polynomial-time learning algorithm can outperform the trivial predictor that assigns to each example the response variable 𝔼(y), when d3/2≪r≪d2. Our conclusion holds for a `natural data distribution', namely standard Gaussian feature vectors x, and output distributed according to a two-layer neural network with random isotropic weights, and under a certain complexity-theoretic assumption on tensor decomposition. Roughly speaking, we assume that no polynomial-time algorithm can substantially outperform current methods for tensor decomposition based on the sum-of-squares hierarchy. We also prove generalizations of this statement for higher degree polynomial activations, and non-random weight vectors. Remarkably, several existing algorithms for learning two-layer networks with rigorous guarantees are based on tensor decomposition. Our results support the idea that this is indeed the core computational difficulty in learning such networks, under the stated generative model for the data. As a side result, we show that under this model learning the network requires accurate learning of its weights, a property that does not hold in a more general setting.
AU - Mondelli, Marco
AU - Montanari, Andrea
ID - 6747
T2 - Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics
TI - On the connection between learning two-layers neural networks and tensor decomposition
VL - 89
ER -
TY - JOUR
AB - Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only 38% of the total area of the memory-based base-line decoder when 5G code rates are supported.
AU - Hashemi, Seyyed Ali
AU - Condo, Carlo
AU - Mondelli, Marco
AU - Gross, Warren J
ID - 6750
IS - 22
JF - IEEE Transactions on Signal Processing
SN - 1053587X
TI - Rate-flexible fast polar decoders
VL - 67
ER -
TY - JOUR
AB - Two-player games on graphs are widely studied in formal methods, as they model the interaction between a system and its environment. The game is played by moving a token throughout a graph to produce an infinite path. There are several common modes to determine how the players move the token through the graph; e.g., in turn-based games the players alternate turns in moving the token. We study the bidding mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. The following bidding rule was previously defined and called Richman bidding. Both players have separate budgets, which sum up to 1. In each turn, a bidding takes place: Both players submit bids simultaneously, where a bid is legal if it does not exceed the available budget, and the higher bidder pays his bid to the other player and moves the token. The central question studied in bidding games is a necessary and sufficient initial budget for winning the game: a threshold budget in a vertex is a value t ∈ [0, 1] such that if Player 1’s budget exceeds t, he can win the game; and if Player 2’s budget exceeds 1 − t, he can win the game. Threshold budgets were previously shown to exist in every vertex of a reachability game, which have an interesting connection with random-turn games—a sub-class of simple stochastic games in which the player who moves is chosen randomly. We show the existence of threshold budgets for a qualitative class of infinite-duration games, namely parity games, and a quantitative class, namely mean-payoff games. The key component of the proof is a quantitative solution to strongly connected mean-payoff bidding games in which we extend the connection with random-turn games to these games, and construct explicit optimal strategies for both players.
AU - Avni, Guy
AU - Henzinger, Thomas A
AU - Chonev, Ventsislav K
ID - 6752
IS - 4
JF - Journal of the ACM
SN - 00045411
TI - Infinite-duration bidding games
VL - 66
ER -
TY - JOUR
AB - Differentiated sex chromosomes are accompanied by a difference in gene dose between X/Z-specific and autosomal genes. At the transcriptomic level, these sex-linked genes can lead to expression imbalance, or gene dosage can be compensated by epigenetic mechanisms and results into expression level equalization. Schistosoma mansoni has been previously described as a ZW species (i.e., female heterogamety, in opposition to XY male heterogametic species) with a partial dosage compensation, but underlying mechanisms are still unexplored. Here, we combine transcriptomic (RNA-Seq) and epigenetic data (ChIP-Seq against H3K4me3, H3K27me3,andH4K20me1histonemarks) in free larval cercariae and intravertebrate parasitic stages. For the first time, we describe differences in dosage compensation status in ZW females, depending on the parasitic status: free cercariae display global dosage compensation, whereas intravertebrate stages show a partial dosage compensation. We also highlight regional differences of gene expression along the Z chromosome in cercariae, but not in the intravertebrate stages. Finally, we feature a consistent permissive chromatin landscape of the Z chromosome in both sexes and stages. We argue that dosage compensation in schistosomes is characterized by chromatin remodeling mechanisms in the Z-specific region.
AU - Picard, Marion A L
AU - Vicoso, Beatriz
AU - Roquis, David
AU - Bulla, Ingo
AU - Augusto, Ronaldo C.
AU - Arancibia, Nathalie
AU - Grunau, Christoph
AU - Boissier, Jérôme
AU - Cosseau, Céline
ID - 6755
IS - 7
JF - Genome biology and evolution
TI - Dosage compensation throughout the Schistosoma mansoni lifecycle: Specific chromatin landscape of the Z chromosome
VL - 11
ER -
TY - JOUR
AB - We study the topology generated by the temperature fluctuations of the cosmic microwave background (CMB) radiation, as quantified by the number of components and holes, formally given by the Betti numbers, in the growing excursion sets. We compare CMB maps observed by the Planck satellite with a thousand simulated maps generated according to the ΛCDM paradigm with Gaussian distributed fluctuations. The comparison is multi-scale, being performed on a sequence of degraded maps with mean pixel separation ranging from 0.05 to 7.33°. The survey of the CMB over 𝕊2 is incomplete due to obfuscation effects by bright point sources and other extended foreground objects like our own galaxy. To deal with such situations, where analysis in the presence of “masks” is of importance, we introduce the concept of relative homology. The parametric χ2-test shows differences between observations and simulations, yielding p-values at percent to less than permil levels roughly between 2 and 7°, with the difference in the number of components and holes peaking at more than 3σ sporadically at these scales. The highest observed deviation between the observations and simulations for b0 and b1 is approximately between 3σ and 4σ at scales of 3–7°. There are reports of mildly unusual behaviour of the Euler characteristic at 3.66° in the literature, computed from independent measurements of the CMB temperature fluctuations by Planck’s predecessor, the Wilkinson Microwave Anisotropy Probe (WMAP) satellite. The mildly anomalous behaviour of the Euler characteristic is phenomenologically related to the strongly anomalous behaviour of components and holes, or the zeroth and first Betti numbers, respectively. Further, since these topological descriptors show consistent anomalous behaviour over independent measurements of Planck and WMAP, instrumental and systematic errors may be an unlikely source. These are also the scales at which the observed maps exhibit low variance compared to the simulations, and approximately the range of scales at which the power spectrum exhibits a dip with respect to the theoretical model. Non-parametric tests show even stronger differences at almost all scales. Crucially, Gaussian simulations based on power-spectrum matching the characteristics of the observed dipped power spectrum are not able to resolve the anomaly. Understanding the origin of the anomalies in the CMB, whether cosmological in nature or arising due to late-time effects, is an extremely challenging task. Regardless, beyond the trivial possibility that this may still be a manifestation of an extreme Gaussian case, these observations, along with the super-horizon scales involved, may motivate the study of primordial non-Gaussianity. Alternative scenarios worth exploring may be models with non-trivial topology, including topological defect models.
AU - Pranav, Pratyush
AU - Adler, Robert J.
AU - Buchert, Thomas
AU - Edelsbrunner, Herbert
AU - Jones, Bernard J.T.
AU - Schwartzman, Armin
AU - Wagner, Hubert
AU - Van De Weygaert, Rien
ID - 6756
JF - Astronomy and Astrophysics
SN - 00046361
TI - Unexpected topology of the temperature fluctuations in the cosmic microwave background
VL - 627
ER -
TY - JOUR
AB - We consider the graph class Grounded-L corresponding to graphs that admit an intersection representation by L-shaped curves, where additionally the topmost points of each curve are assumed to belong to a common horizontal line. We prove that Grounded-L graphs admit an equivalent characterisation in terms of vertex ordering with forbidden patterns.
We also compare this class to related intersection classes, such as the grounded segment graphs, the monotone L-graphs (a.k.a. max point-tolerance graphs), or the outer-1-string graphs. We give constructions showing that these classes are all distinct and satisfy only trivial or previously known inclusions.
AU - Jelínek, Vít
AU - Töpfer, Martin
ID - 6759
IS - 3
JF - Electronic Journal of Combinatorics
TI - On grounded L-graphs and their relatives
VL - 26
ER -
TY - JOUR
AB - We present and study novel optimal control problems motivated by the search for photovoltaic materials with high power-conversion efficiency. The material must perform the first step: convert light (photons) into electronic excitations. We formulate various desirable properties of the excitations as mathematical control goals at the Kohn-Sham-DFT level
of theory, with the control being given by the nuclear charge distribution. We prove that nuclear distributions exist which give rise to optimal HOMO-LUMO excitations, and present illustrative numerical simulations for 1D finite nanocrystals. We observe pronounced goal-dependent features such as large electron-hole separation, and a hierarchy of length scales: internal HOMO and LUMO wavelengths < atomic spacings < (irregular) fluctuations of the doping profiles < system size.
AU - Friesecke, Gero
AU - Kniely, Michael
ID - 6762
IS - 3
JF - Multiscale Modeling and Simulation
SN - 15403459
TI - New optimal control problems in density functional theory motivated by photovoltaics
VL - 17
ER -
TY - JOUR
AB - When grape-sized aqueous dimers are irradiated in a microwave oven, an intense electromagnetic hotspot forms at their point of contact, often igniting a plasma. Here we show that this irradiation can result in the injection of mechanical energy. By examining irradiated hydrogel dimers through high-speed imaging, we find that they repeatedly bounce off of each other while irradiated. We determine that an average of 1 lJ of mechanical energy is injected into the pair during each collision. Furthermore, a characteristic high-pitched audio signal is found to accompany each collision.
We show that both the audio signal and the energy injection arise via an interplay between vaporization and elastic deformations in the region of contact, the so-called ‘elastic Liedenfrost effect’. Our results establish a novel, non-contact method of injecting mechanical energy into soft matter systems, suggesting application in fields such as soft robotics.
AU - Khattak, Hamza K.
AU - Waitukaitis, Scott R
AU - Slepkov, Aaron D.
ID - 6763
IS - 29
JF - Soft Matter
SN - 1744683X
TI - Microwave induced mechanical activation of hydrogel dimers
VL - 15
ER -
TY - JOUR
AB - An important adaptation during colonization of land by plants is gravitropic growth of roots, which enabled roots to reach water and nutrients, and firmly anchor plants in the ground. Here we provide insights into the evolution of an efficient root gravitropic mechanism in the seed plants. Architectural innovation, with gravity perception constrained in the root tips
along with a shootward transport route for the phytohormone auxin, appeared only upon the emergence of seed plants. Interspecies complementation and protein domain swapping revealed functional innovations within the PIN family of auxin transporters leading to the evolution of gravitropism-specific PINs. The unique apical/shootward subcellular localization of PIN proteins is the major evolutionary innovation that connected the anatomically separated sites of gravity perception and growth response via the mobile auxin signal. We conclude that the crucial anatomical and functional components emerged hand-in-hand to facilitate the evolution of fast gravitropic response, which is one of the major adaptations of seed plants to dry land.
AU - Zhang, Yuzhou
AU - Xiao, G
AU - Wang, X
AU - Zhang, Xixi
AU - Friml, Jiří
ID - 6778
JF - Nature Communications
SN - 2041-1723
TI - Evolution of fast root gravitropism in seed plants
VL - 10
ER -
TY - JOUR
AB - Recent studies suggest that unstable recurrent solutions of the Navier-Stokes equation provide new insights
into dynamics of turbulent flows. In this study, we compute an extensive network of dynamical connections
between such solutions in a weakly turbulent quasi-two-dimensional Kolmogorov flow that lies in the inversion symmetric subspace. In particular, we find numerous isolated heteroclinic connections between different
types of solutions—equilibria, periodic, and quasiperiodic orbits—as well as continua of connections forming
higher-dimensional connecting manifolds. We also compute a homoclinic connection of a periodic orbit and
provide strong evidence that the associated homoclinic tangle forms the chaotic repeller that underpins transient
turbulence in the symmetric subspace.
AU - Suri, Balachandra
AU - Pallantla, Ravi Kumar
AU - Schatz, Michael F.
AU - Grigoriev, Roman O.
ID - 6779
IS - 1
JF - Physical Review E
SN - 2470-0045
TI - Heteroclinic and homoclinic connections in a Kolmogorov-like flow
VL - 100
ER -
TY - JOUR
AB - Dipolar coupling plays a fundamental role in the interaction between electrically or magnetically polarized species such as magnetic atoms and dipolar molecules in a gas or dipolar excitons in the solid state. Unlike Coulomb or contactlike interactions found in many atomic, molecular, and condensed-matter systems, this interaction is long-ranged and highly anisotropic, as it changes from repulsive to attractive depending on the relative positions and orientation of the dipoles. Because of this unique property, many exotic, symmetry-breaking collective states have been recently predicted for cold dipolar gases, but only a few have been experimentally detected and only in dilute atomic dipolar Bose-Einstein condensates. Here, we report on the first observation of attractive dipolar coupling between excitonic dipoles using a new design of stacked semiconductor bilayers. We show that the presence of a dipolar exciton fluid in one bilayer modifies the spatial distribution and increases the binding energy of excitonic dipoles in a vertically remote layer. The binding energy changes are explained using a many-body polaron model describing the deformation of the exciton cloud due to its interaction with a remote dipolar exciton. The surprising nonmonotonic dependence on the cloud density indicates the important role of dipolar correlations, which is unique to dense, strongly interacting dipolar solid-state systems. Our concept provides a route for the realization of dipolar lattices with strong anisotropic interactions in semiconductor systems, which open the way for the observation of theoretically predicted new and exotic collective phases, as well as for engineering and sensing their collective excitations.
AU - Hubert, Colin
AU - Baruchi, Yifat
AU - Mazuz-Harpaz, Yotam
AU - Cohen, Kobi
AU - Biermann, Klaus
AU - Lemeshko, Mikhail
AU - West, Ken
AU - Pfeiffer, Loren
AU - Rapaport, Ronen
AU - Santos, Paulo
ID - 6786
IS - 2
JF - Physical Review X
TI - Attractive dipolar coupling between stacked exciton fluids
VL - 9
ER -
TY - JOUR
AB - We consider the Nelson model with ultraviolet cutoff, which describes the interaction between non-relativistic particles and a positive or zero mass quantized scalar field. We take the non-relativistic particles to obey Fermi statistics and discuss the time evolution in a mean-field limit of many fermions. In this case, the limit is known to be also a semiclassical limit. We prove convergence in terms of reduced density matrices of the many-body state to a tensor product of a Slater determinant with semiclassical structure and a coherent state, which evolve according to a fermionic version of the Schrödinger–Klein–Gordon equations.
AU - Leopold, Nikolai K
AU - Petrat, Sören P
ID - 6788
IS - 10
JF - Annales Henri Poincare
SN - 1424-0637
TI - Mean-field dynamics for the Nelson model with fermions
VL - 20
ER -
TY - JOUR
AB - The Regge symmetry is a set of remarkable relations between two tetrahedra whose edge lengths are related in a simple fashion. It was first discovered as a consequence of an asymptotic formula in mathematical physics. Here, we give a simple geometric proof of Regge symmetries in Euclidean, spherical, and hyperbolic geometry.
AU - Akopyan, Arseniy
AU - Izmestiev, Ivan
ID - 6793
IS - 5
JF - Bulletin of the London Mathematical Society
SN - 00246093
TI - The Regge symmetry, confocal conics, and the Schläfli formula
VL - 51
ER -
TY - JOUR
AB - The green‐beard effect is one proposed mechanism predicted to underpin the evolu‐tion of altruistic behavior. It relies on the recognition and the selective help of altruists to each other in order to promote and sustain altruistic behavior. However, this mechanism has often been dismissed as unlikely or uncommon, as it is assumed that both the signaling trait and altruistic trait need to be encoded by the same gene or through tightly linked genes. Here, we use models of indirect genetic effects (IGEs) to find the minimum correlation between the signaling and altruistic trait required for the evolution of the latter. We show that this correlation threshold depends on the strength of the interaction (influence of the green beard on the expression of the altruistic trait), as well as the costs and benefits of the altruistic behavior. We further show that this correlation does not necessarily have to be high and support our analytical results by simulations.
AU - Trubenova, Barbora
AU - Hager, Reinmar
ID - 6795
IS - 17
JF - Ecology and Evolution
TI - Green beards in the light of indirect genetic effects
VL - 9
ER -
TY - JOUR
AB - Indigoidine is a blue natural pigment, which can be efficiently synthetized in E. coli. In addition to its antioxidant and antimicrobial activities indigoidine due to its stability and deep blue color can find an application as an industrial, environmentally friendly dye. Moreover, similarly to its counterpart regular indigo dye, due to its molecular structure, indigoidine is an organic semiconductor. Fully conjugated aromatic moiety and intermolecular hydrogen bonding of indigoidine result in an unusually narrow bandgap for such a small molecule. This, in its turn, result is tight molecular packing in the solid state and opens a path for a wide range of application in organic and bio-electronics, such as electrochemical and field effect transistors, organic solar cells, light and bio-sensors etc.
AU - Yumusak, Cigdem
AU - Prochazkova, Anna Jancik
AU - Apaydin, Dogukan H
AU - Seelajaroen, Hathaichanok
AU - Sariciftci, Niyazi Serdar
AU - Weiter, Martin
AU - Krajcovic, Jozef
AU - Qin, Yong
AU - Zhang, Wei
AU - Zhan, Jixun
AU - Kovalenko, Alexander
ID - 6818
JF - Dyes and Pigments
SN - 0143-7208
TI - Indigoidine - Biosynthesized organic semiconductor
VL - 171
ER -
TY - JOUR
AB - To determine the visual sensitivities of an organism of interest, quantitative reverse transcription–polymerase chain reaction (qRT–PCR) is often used to quantify expression of the light‐sensitive opsins in the retina. While qRT–PCR is an affordable, high‐throughput method for measuring expression, it comes with inherent normalization issues that affect the interpretation of results, especially as opsin expression can vary greatly based on developmental stage, light environment or diurnal cycles. We tested for diurnal cycles of opsin expression over a period of 24 hr at 1‐hr increments and examined how normalization affects a data set with fluctuating expression levels using qRT–PCR and transcriptome data from the retinae of the cichlid Pelmatolapia mariae. We compared five methods of normalizing opsin expression relative to (a) the average of three stably expressed housekeeping genes (Ube2z, EF1‐α and β‐actin), (b) total RNA concentration, (c) GNAT2, (the cone‐specific subunit of transducin), (d) total opsin expression and (e) only opsins expressed in the same cone type. Normalizing by proportion of cone type produced the least variation and would be best for removing time‐of‐day variation. In contrast, normalizing by housekeeping genes produced the highest daily variation in expression and demonstrated that the peak of cone opsin expression was in the late afternoon. A weighted correlation network analysis showed that the expression of different cone opsins follows a very similar daily cycle. With the knowledge of how these normalization methods affect opsin expression data, we make recommendations for designing sampling approaches and quantification methods based upon the scientific question being examined.
AU - Yourick, Miranda R.
AU - Sandkam, Benjamin A.
AU - Gammerdinger, William J
AU - Escobar-Camacho, Daniel
AU - Nandamuri, Sri Pratima
AU - Clark, Frances E.
AU - Joyce, Brendan
AU - Conte, Matthew A.
AU - Kocher, Thomas D.
AU - Carleton, Karen L.
ID - 6821
IS - 6
JF - Molecular Ecology Resources
TI - Diurnal variation in opsin expression and common housekeeping genes necessitates comprehensive normalization methods for quantitative real-time PCR analyses
VL - 19
ER -
TY - CONF
AB - In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the qualitative winner or quantitative payoff of the game. In bidding games, in each turn, we hold an auction between the two players to determine which player moves the token. Bidding games have largely been studied with concrete bidding mechanisms that are variants of a first-price auction: in each turn both players simultaneously submit bids, the higher
bidder moves the token, and pays his bid to the lower bidder in Richman bidding, to the bank in poorman bidding, and in taxman bidding, the bid is split between the other player and the bank according to a predefined constant factor. Bidding games are deterministic games. They have an intriguing connection with a fragment of stochastic games called
randomturn games. We study, for the first time, a combination of bidding games with probabilistic behavior; namely, we study bidding games that are played on Markov decision processes, where the players bid for the right to choose the next action, which determines the probability distribution according to which the next vertex is chosen. We study parity and meanpayoff bidding games on MDPs and extend results from the deterministic bidding setting to the probabilistic one.
AU - Avni, Guy
AU - Henzinger, Thomas A
AU - Ibsen-Jensen, Rasmus
AU - Novotny, Petr
ID - 6822
SN - 0302-9743
T2 - Proceedings of the 13th International Conference of Reachability Problems
TI - Bidding games on Markov decision processes
VL - 11674
ER -
TY - JOUR
AB - Platelets are small anucleate cellular fragments that are released by megakaryocytes and safeguard vascular integrity through a process termed ‘haemostasis’. However, platelets have important roles beyond haemostasis as they contribute to the initiation and coordination of intravascular immune responses. They continuously monitor blood vessel integrity and tightly coordinate vascular trafficking and functions of multiple cell types. In this way platelets act as ‘patrolling officers of the vascular highway’ that help to establish effective immune responses to infections and cancer. Here we discuss the distinct biological features of platelets that allow them to shape immune responses to pathogens and tumour cells, highlighting the parallels between these responses.
AU - Gärtner, Florian R
AU - Massberg, Steffen
ID - 6824
IS - 12
JF - Nature Reviews Immunology
SN - 1474-1733
TI - Patrolling the vascular borders: Platelets in immunity to infection and cancer
VL - 19
ER -
TY - JOUR
AB - In this paper we construct a family of exact functors from the category of Whittaker modules of the simple complex Lie algebra of type to the category of finite-dimensional modules of the graded affine Hecke algebra of type . Using results of Backelin [2] and of Arakawa-Suzuki [1], we prove that these functors map standard modules to standard modules (or zero) and simple modules to simple modules (or zero). Moreover, we show that each simple module of the graded affine Hecke algebra appears as the image of a simple Whittaker module. Since the Whittaker category contains the BGG category as a full subcategory, our results generalize results of Arakawa-Suzuki [1], which in turn generalize Schur-Weyl duality between finite-dimensional representations of and representations of the symmetric group .
AU - Brown, Adam
ID - 6828
JF - Journal of Algebra
SN - 0021-8693
TI - Arakawa-Suzuki functors for Whittaker modules
VL - 538
ER -
TY - JOUR
AB - Steady-state turnover is a hallmark of epithelial tissues throughout adult life. Intestinal epithelial turnover is marked by continuous cell migration, which is assumed to be driven by mitotic pressure from the crypts. However, the balance of forces in renewal remains ill-defined. Combining biophysical modeling and quantitative three-dimensional tissue imaging with genetic and physical manipulations, we revealed the existence of an actin-related protein 2/3 complex–dependent active migratory force, which explains quantitatively the profiles of cell speed, density, and tissue tension along the villi. Cells migrate collectively with minimal rearrangements while displaying dual—apicobasal and front-back—polarity characterized by actin-rich basal protrusions oriented in the direction of migration. We propose that active migration is a critical component of gut epithelial turnover.
AU - Krndija, Denis
AU - Marjou, Fatima El
AU - Guirao, Boris
AU - Richon, Sophie
AU - Leroy, Olivier
AU - Bellaiche, Yohanns
AU - Hannezo, Edouard B
AU - Vignjevic, Danijela Matic
ID - 6832
IS - 6454
JF - Science
TI - Active cell migration is critical for steady-state epithelial turnover in the gut
VL - 365
ER -
TY - JOUR
AB - We derive the Hasse principle and weak approximation for fibrations of certain varieties in the spirit of work by Colliot-Thélène–Sansuc and Harpaz–Skorobogatov–Wittenberg. Our varieties are defined through polynomials in many variables and part of our work is devoted to establishing Schinzel's hypothesis for polynomials of this kind. This last part is achieved by using arguments behind Birch's well-known result regarding the Hasse principle for complete intersections with the notable difference that we prove our result in 50% fewer variables than in the classical Birch setting. We also study the problem of square-free values of an integer polynomial with 66.6% fewer variables than in the Birch setting.
AU - Destagnol, Kevin N
AU - Sofos, Efthymios
ID - 6835
IS - 11
JF - Bulletin des Sciences Mathematiques
SN - 0007-4497
TI - Rational points and prime values of polynomials in moderately many variables
VL - 156
ER -
TY - JOUR
AB - Direct reciprocity is a powerful mechanism for the evolution of cooperation on the basis of repeated interactions1,2,3,4. It requires that interacting individuals are sufficiently equal, such that everyone faces similar consequences when they cooperate or defect. Yet inequality is ubiquitous among humans5,6 and is generally considered to undermine cooperation and welfare7,8,9,10. Most previous models of reciprocity do not include inequality11,12,13,14,15. These models assume that individuals are the same in all relevant aspects. Here we introduce a general framework to study direct reciprocity among unequal individuals. Our model allows for multiple sources of inequality. Subjects can differ in their endowments, their productivities and in how much they benefit from public goods. We find that extreme inequality prevents cooperation. But if subjects differ in productivity, some endowment inequality can be necessary for cooperation to prevail. Our mathematical predictions are supported by a behavioural experiment in which we vary the endowments and productivities of the subjects. We observe that overall welfare is maximized when the two sources of heterogeneity are aligned, such that more productive individuals receive higher endowments. By contrast, when endowments and productivities are misaligned, cooperation quickly breaks down. Our findings have implications for policy-makers concerned with equity, efficiency and the provisioning of public goods.
AU - Hauser, Oliver P.
AU - Hilbe, Christian
AU - Chatterjee, Krishnendu
AU - Nowak, Martin A.
ID - 6836
IS - 7770
JF - Nature
SN - 00280836
TI - Social dilemmas among unequals
VL - 572
ER -
TY - JOUR
AB - Migrasomes are a recently discovered type of extracellular vesicles that are characteristically generated along retraction fibers in migrating cells. Two studies now show how migrasomes are formed and how they function in the physiologically relevant context of the developing zebrafish embryo.
AU - Tavano, Ste
AU - Heisenberg, Carl-Philipp J
ID - 6837
IS - 8
JF - Nature Cell Biology
TI - Migrasomes take center stage
VL - 21
ER -
TY - JOUR
AB - We discuss thermodynamic properties of harmonically trapped
imperfect quantum gases. The spatial inhomogeneity of these systems imposes
a redefinition of the mean-field interparticle potential energy as compared
to the homogeneous case. In our approach, it takes the form a
2N2 ωd, where
N is the number of particles, ω—the harmonic trap frequency, d—system’s
dimensionality, and a is a parameter characterizing the interparticle interaction.
We provide arguments that this model corresponds to the limiting case of
a long-ranged interparticle potential of vanishingly small amplitude. This
conclusion is drawn from a computation similar to the well-known Kac scaling
procedure, which is presented here in a form adapted to the case of an isotropic
harmonic trap. We show that within the model, the imperfect gas of trapped
repulsive bosons undergoes the Bose–Einstein condensation provided d > 1.
The main result of our analysis is that in d = 1 the gas of attractive imperfect
fermions with a = −aF < 0 is thermodynamically equivalent to the gas of
repulsive bosons with a = aB > 0 provided the parameters aF and aB fulfill
the relation aB + aF = . This result supplements similar recent conclusion
about thermodynamic equivalence of two-dimensional (2D) uniform imperfect
repulsive Bose and attractive Fermi gases.
AU - Mysliwy, Krzysztof
AU - Napiórkowski, Marek
ID - 6840
IS - 6
JF - Journal of Statistical Mechanics: Theory and Experiment
TI - Thermodynamics of inhomogeneous imperfect quantum gases in harmonic traps
VL - 2019
ER -
TY - JOUR
AB - The aim of this short paper is to offer a complete characterization of all (not necessarily surjective) isometric embeddings of the Wasserstein space Wp(X), where S is a countable discrete metric space and 0