@unpublished{8185, abstract = {In this paper we study envy-free division problems. The classical approach to some of such problems, used by David Gale, reduces to considering continuous maps of a simplex to itself and finding sufficient conditions when this map hits the center of the simplex. The mere continuity is not sufficient for such a conclusion, the usual assumption (for example, in the Knaster--Kuratowski--Mazurkiewicz and the Gale theorem) is a certain boundary condition. We follow Erel Segal-Halevi, Fr\'ed\'eric Meunier, and Shira Zerbib, and replace the boundary condition by another assumption, which has the economic meaning of possibility for a player to prefer an empty part in the segment partition problem. We solve the problem positively when $n$, the number of players that divide the segment, is a prime power, and we provide counterexamples for every $n$ which is not a prime power. We also provide counterexamples relevant to a wider class of fair or envy-free partition problems when $n$ is odd and not a prime power.}, author = {Avvakumov, Sergey and Karasev, Roman}, booktitle = {arXiv}, title = {{Envy-free division using mapping degree}}, doi = {10.48550/arXiv.1907.11183}, year = {2019}, } @article{151, abstract = {We construct planar bi-Sobolev mappings whose local volume distortion is bounded from below by a given function f∈Lp with p>1. More precisely, for any 1<q<(p+1)/2 we construct W1,q-bi-Sobolev maps with identity boundary conditions; for f∈L∞, we provide bi-Lipschitz maps. The basic building block of our construction are bi-Lipschitz maps which stretch a given compact subset of the unit square by a given factor while preserving the boundary. The construction of these stretching maps relies on a slight strengthening of the celebrated covering result of Alberti, Csörnyei, and Preiss for measurable planar sets in the case of compact sets. We apply our result to a model functional in nonlinear elasticity, the integrand of which features fast blowup as the Jacobian determinant of the deformation becomes small. For such functionals, the derivation of the equilibrium equations for minimizers requires an additional regularization of test functions, which our maps provide.}, author = {Fischer, Julian L and Kneuss, Olivier}, journal = {Journal of Differential Equations}, number = {1}, pages = {257 -- 311}, publisher = {Elsevier}, title = {{Bi-Sobolev solutions to the prescribed Jacobian inequality in the plane with L p data and applications to nonlinear elasticity}}, doi = {10.1016/j.jde.2018.07.045}, volume = {266}, year = {2019}, } @article{175, abstract = {An upper bound sieve for rational points on suitable varieties isdeveloped, together with applications tocounting rational points in thin sets,to local solubility in families, and to the notion of “friable” rational pointswith respect to divisors. In the special case of quadrics, sharper estimates areobtained by developing a version of the Selberg sieve for rational points.}, author = {Browning, Timothy D and Loughran, Daniel}, issn = {10886850}, journal = {Transactions of the American Mathematical Society}, number = {8}, pages = {5757--5785}, publisher = {American Mathematical Society}, title = {{Sieving rational points on varieties}}, doi = {10.1090/tran/7514}, volume = {371}, year = {2019}, } @article{196, abstract = {The abelian sandpile serves as a model to study self-organized criticality, a phenomenon occurring in biological, physical and social processes. The identity of the abelian group is a fractal composed of self-similar patches, and its limit is subject of extensive collaborative research. Here, we analyze the evolution of the sandpile identity under harmonic fields of different orders. We show that this evolution corresponds to periodic cycles through the abelian group characterized by the smooth transformation and apparent conservation of the patches constituting the identity. The dynamics induced by second and third order harmonics resemble smooth stretchings, respectively translations, of the identity, while the ones induced by fourth order harmonics resemble magnifications and rotations. Starting with order three, the dynamics pass through extended regions of seemingly random configurations which spontaneously reassemble into accentuated patterns. We show that the space of harmonic functions projects to the extended analogue of the sandpile group, thus providing a set of universal coordinates identifying configurations between different domains. Since the original sandpile group is a subgroup of the extended one, this directly implies that it admits a natural renormalization. Furthermore, we show that the harmonic fields can be induced by simple Markov processes, and that the corresponding stochastic dynamics show remarkable robustness over hundreds of periods. Finally, we encode information into seemingly random configurations, and decode this information with an algorithm requiring minimal prior knowledge. Our results suggest that harmonic fields might split the sandpile group into sub-sets showing different critical coefficients, and that it might be possible to extend the fractal structure of the identity beyond the boundaries of its domain. }, author = {Lang, Moritz and Shkolnikov, Mikhail}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, number = {8}, pages = {2821--2830}, publisher = {National Academy of Sciences}, title = {{Harmonic dynamics of the Abelian sandpile}}, doi = {10.1073/pnas.1812015116}, volume = {116}, year = {2019}, } @article{138, abstract = {Autoregulation is the direct modulation of gene expression by the product of the corresponding gene. Autoregulation of bacterial gene expression has been mostly studied at the transcriptional level, when a protein acts as the cognate transcriptional repressor. A recent study investigating dynamics of the bacterial toxin–antitoxin MazEF system has shown how autoregulation at both the transcriptional and post-transcriptional levels affects the heterogeneity of Escherichia coli populations. Toxin–antitoxin systems hold a crucial but still elusive part in bacterial response to stress. This perspective highlights how these modules can also serve as a great model system for investigating basic concepts in gene regulation. However, as the genomic background and environmental conditions substantially influence toxin activation, it is important to study (auto)regulation of toxin–antitoxin systems in well-defined setups as well as in conditions that resemble the environmental niche.}, author = {Nikolic, Nela}, journal = {Current Genetics}, number = {1}, pages = {133--138}, publisher = {Springer}, title = {{Autoregulation of bacterial gene expression: lessons from the MazEF toxin–antitoxin system}}, doi = {10.1007/s00294-018-0879-8}, volume = {65}, year = {2019}, } @inproceedings{14184, abstract = {Learning disentangled representations is considered a cornerstone problem in representation learning. Recently, Locatello et al. (2019) demonstrated that unsupervised disentanglement learning without inductive biases is theoretically impossible and that existing inductive biases and unsupervised methods do not allow to consistently learn disentangled representations. However, in many practical settings, one might have access to a limited amount of supervision, for example through manual labeling of (some) factors of variation in a few training examples. In this paper, we investigate the impact of such supervision on state-of-the-art disentanglement methods and perform a large scale study, training over 52000 models under well-defined and reproducible experimental conditions. We observe that a small number of labeled examples (0.01--0.5\% of the data set), with potentially imprecise and incomplete labels, is sufficient to perform model selection on state-of-the-art unsupervised models. Further, we investigate the benefit of incorporating supervision into the training process. Overall, we empirically validate that with little and imprecise supervision it is possible to reliably learn disentangled representations.}, author = {Locatello, Francesco and Tschannen, Michael and Bauer, Stefan and Rätsch, Gunnar and Schölkopf, Bernhard and Bachem, Olivier}, booktitle = {8th International Conference on Learning Representations}, location = {Virtual}, title = {{Disentangling factors of variation using few labels}}, year = {2019}, } @inproceedings{14189, abstract = {We consider the problem of recovering a common latent source with independent components from multiple views. This applies to settings in which a variable is measured with multiple experimental modalities, and where the goal is to synthesize the disparate measurements into a single unified representation. We consider the case that the observed views are a nonlinear mixing of component-wise corruptions of the sources. When the views are considered separately, this reduces to nonlinear Independent Component Analysis (ICA) for which it is provably impossible to undo the mixing. We present novel identifiability proofs that this is possible when the multiple views are considered jointly, showing that the mixing can theoretically be undone using function approximators such as deep neural networks. In contrast to known identifiability results for nonlinear ICA, we prove that independent latent sources with arbitrary mixing can be recovered as long as multiple, sufficiently different noisy views are available.}, author = {Gresele, Luigi and Rubenstein, Paul K. and Mehrjou, Arash and Locatello, Francesco and Schölkopf, Bernhard}, booktitle = {Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence}, location = {Tel Aviv, Israel}, pages = {217--227}, publisher = {ML Research Press}, title = {{The incomplete Rosetta Stone problem: Identifiability results for multi-view nonlinear ICA}}, volume = {115}, year = {2019}, } @inproceedings{14190, abstract = {Learning meaningful and compact representations with disentangled semantic aspects is considered to be of key importance in representation learning. Since real-world data is notoriously costly to collect, many recent state-of-the-art disentanglement models have heavily relied on synthetic toy data-sets. In this paper, we propose a novel data-set which consists of over one million images of physical 3D objects with seven factors of variation, such as object color, shape, size and position. In order to be able to control all the factors of variation precisely, we built an experimental platform where the objects are being moved by a robotic arm. In addition, we provide two more datasets which consist of simulations of the experimental setup. These datasets provide for the first time the possibility to systematically investigate how well different disentanglement methods perform on real data in comparison to simulation, and how simulated data can be leveraged to build better representations of the real world. We provide a first experimental study of these questions and our results indicate that learned models transfer poorly, but that model and hyperparameter selection is an effective means of transferring information to the real world.}, author = {Gondal, Muhammad Waleed and Wüthrich, Manuel and Miladinović, Đorđe and Locatello, Francesco and Breidt, Martin and Volchkov, Valentin and Akpo, Joel and Bachem, Olivier and Schölkopf, Bernhard and Bauer, Stefan}, booktitle = {Advances in Neural Information Processing Systems}, isbn = {9781713807933}, location = {Vancouver, Canada}, title = {{On the transfer of inductive bias from simulation to the real world: a new disentanglement dataset}}, volume = {32}, year = {2019}, } @inproceedings{14191, abstract = {A broad class of convex optimization problems can be formulated as a semidefinite program (SDP), minimization of a convex function over the positive-semidefinite cone subject to some affine constraints. The majority of classical SDP solvers are designed for the deterministic setting where problem data is readily available. In this setting, generalized conditional gradient methods (aka Frank-Wolfe-type methods) provide scalable solutions by leveraging the so-called linear minimization oracle instead of the projection onto the semidefinite cone. Most problems in machine learning and modern engineering applications, however, contain some degree of stochasticity. In this work, we propose the first conditional-gradient-type method for solving stochastic optimization problems under affine constraints. Our method guarantees O(k−1/3) convergence rate in expectation on the objective residual and O(k−5/12) on the feasibility gap.}, author = {Locatello, Francesco and Yurtsever, Alp and Fercoq, Olivier and Cevher, Volkan}, booktitle = {Advances in Neural Information Processing Systems}, isbn = {9781713807933}, location = {Vancouver, Canada}, pages = {14291–14301}, title = {{Stochastic Frank-Wolfe for composite convex minimization}}, volume = {32}, year = {2019}, } @inproceedings{14193, abstract = {A disentangled representation encodes information about the salient factors of variation in the data independently. Although it is often argued that this representational format is useful in learning to solve many real-world down-stream tasks, there is little empirical evidence that supports this claim. In this paper, we conduct a large-scale study that investigates whether disentangled representations are more suitable for abstract reasoning tasks. Using two new tasks similar to Raven's Progressive Matrices, we evaluate the usefulness of the representations learned by 360 state-of-the-art unsupervised disentanglement models. Based on these representations, we train 3600 abstract reasoning models and observe that disentangled representations do in fact lead to better down-stream performance. In particular, they enable quicker learning using fewer samples.}, author = {Steenkiste, Sjoerd van and Locatello, Francesco and Schmidhuber, Jürgen and Bachem, Olivier}, booktitle = {Advances in Neural Information Processing Systems}, isbn = {9781713807933}, location = {Vancouver, Canada}, title = {{Are disentangled representations helpful for abstract visual reasoning?}}, volume = {32}, year = {2019}, } @inproceedings{14197, abstract = {Recently there has been a significant interest in learning disentangled representations, as they promise increased interpretability, generalization to unseen scenarios and faster learning on downstream tasks. In this paper, we investigate the usefulness of different notions of disentanglement for improving the fairness of downstream prediction tasks based on representations. We consider the setting where the goal is to predict a target variable based on the learned representation of high-dimensional observations (such as images) that depend on both the target variable and an \emph{unobserved} sensitive variable. We show that in this setting both the optimal and empirical predictions can be unfair, even if the target variable and the sensitive variable are independent. Analyzing the representations of more than \num{12600} trained state-of-the-art disentangled models, we observe that several disentanglement scores are consistently correlated with increased fairness, suggesting that disentanglement may be a useful property to encourage fairness when sensitive variables are not observed.}, author = {Locatello, Francesco and Abbati, Gabriele and Rainforth, Tom and Bauer, Stefan and Schölkopf, Bernhard and Bachem, Olivier}, booktitle = {Advances in Neural Information Processing Systems}, isbn = {9781713807933}, location = {Vancouver, Canada}, pages = {14611–14624}, title = {{On the fairness of disentangled representations}}, volume = {32}, year = {2019}, } @inproceedings{14200, abstract = {The key idea behind the unsupervised learning of disentangled representations is that real-world data is generated by a few explanatory factors of variation which can be recovered by unsupervised learning algorithms. In this paper, we provide a sober look at recent progress in the field and challenge some common assumptions. We first theoretically show that the unsupervised learning of disentangled representations is fundamentally impossible without inductive biases on both the models and the data. Then, we train more than 12000 models covering most prominent methods and evaluation metrics in a reproducible large-scale experimental study on seven different data sets. We observe that while the different methods successfully enforce properties ``encouraged'' by the corresponding losses, well-disentangled models seemingly cannot be identified without supervision. Furthermore, increased disentanglement does not seem to lead to a decreased sample complexity of learning for downstream tasks. Our results suggest that future work on disentanglement learning should be explicit about the role of inductive biases and (implicit) supervision, investigate concrete benefits of enforcing disentanglement of the learned representations, and consider a reproducible experimental setup covering several data sets.}, author = {Locatello, Francesco and Bauer, Stefan and Lucic, Mario and Rätsch, Gunnar and Gelly, Sylvain and Schölkopf, Bernhard and Bachem, Olivier}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, location = {Long Beach, CA, United States}, pages = {4114--4124}, publisher = {ML Research Press}, title = {{Challenging common assumptions in the unsupervised learning of disentangled representations}}, volume = {97}, year = {2019}, } @article{5678, abstract = {The order-k Voronoi tessellation of a locally finite set 𝑋⊆ℝ𝑛 decomposes ℝ𝑛 into convex domains whose points have the same k nearest neighbors in X. Assuming X is a stationary Poisson point process, we give explicit formulas for the expected number and total area of faces of a given dimension per unit volume of space. We also develop a relaxed version of discrete Morse theory and generalize by counting only faces, for which the k nearest points in X are within a given distance threshold.}, author = {Edelsbrunner, Herbert and Nikitenko, Anton}, issn = {14320444}, journal = {Discrete and Computational Geometry}, number = {4}, pages = {865–878}, publisher = {Springer}, title = {{Poisson–Delaunay Mosaics of Order k}}, doi = {10.1007/s00454-018-0049-2}, volume = {62}, year = {2019}, } @article{5680, abstract = {Pollinators display a remarkable diversity of foraging strategies with flowering plants, from primarily mutualistic interactions to cheating through nectar robbery. Despite numerous studies on the effect of nectar robbing on components of plant fitness, its contribution to reproductive isolation is unclear. We experimentally tested the impact of different pollinator strategies in a natural hybrid zone between two subspecies of Antirrhinum majus with alternate flower colour guides. On either side of a steep cline in flower colour between Antirrhinum majus pseudomajus (magenta) and A. m. striatum (yellow), we quantified the behaviour of all floral visitors at different time points during the flowering season. Using long-run camera surveys, we quantify the impact of nectar robbing on the number of flowers visited per inflorescence and the flower probing time. We further experimentally tested the effect of nectar robbing on female reproductive success by manipulating the intensity of robbing. While robbing increased over time the number of legitimate visitors tended to decrease concomitantly. We found that the number of flowers pollinated on a focal inflorescence decreased with the number of prior robbing events. However, in the manipulative experiment, fruit set and fruit volume did not vary significantly between low robbing and control treatments. Our findings challenge the idea that robbers have a negative impact on plant fitness through female function. This study also adds to our understanding of the components of pollinator-mediated reproductive isolation and the maintenance of Antirrhinum hybrid zones.}, author = {Andalo, Christophe and Burrus, Monique and Paute, Sandrine and Lauzeral, Christine and Field, David}, issn = {23818115}, journal = {Botany Letters}, number = {1}, pages = {80--92}, publisher = {Taylor and Francis}, title = {{Prevalence of legitimate pollinators and nectar robbers and the consequences for fruit set in an Antirrhinum majus hybrid zone}}, doi = {10.1080/23818107.2018.1545142}, volume = {166}, year = {2019}, } @article{5789, abstract = {Tissue morphogenesis is driven by mechanical forces that elicit changes in cell size, shape and motion. The extent by which forces deform tissues critically depends on the rheological properties of the recipient tissue. Yet, whether and how dynamic changes in tissue rheology affect tissue morphogenesis and how they are regulated within the developing organism remain unclear. Here, we show that blastoderm spreading at the onset of zebrafish morphogenesis relies on a rapid, pronounced and spatially patterned tissue fluidization. Blastoderm fluidization is temporally controlled by mitotic cell rounding-dependent cell–cell contact disassembly during the last rounds of cell cleavages. Moreover, fluidization is spatially restricted to the central blastoderm by local activation of non-canonical Wnt signalling within the blastoderm margin, increasing cell cohesion and thereby counteracting the effect of mitotic rounding on contact disassembly. Overall, our results identify a fluidity transition mediated by loss of cell cohesion as a critical regulator of embryo morphogenesis.}, author = {Petridou, Nicoletta and Grigolon, Silvia and Salbreux, Guillaume and Hannezo, Edouard B and Heisenberg, Carl-Philipp J}, issn = {14657392}, journal = {Nature Cell Biology}, pages = {169–178}, publisher = {Nature Publishing Group}, title = {{Fluidization-mediated tissue spreading by mitotic cell rounding and non-canonical Wnt signalling}}, doi = {10.1038/s41556-018-0247-4}, volume = {21}, year = {2019}, } @article{5790, abstract = {The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph G and a partial representation R′ giving some predrawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire graph G, that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of G. Our main result is an O(n3) time algorithm for partial representation extension of circle graphs, where n is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest.}, author = {Chaplick, Steven and Fulek, Radoslav and Klavík, Pavel}, issn = {03649024}, journal = {Journal of Graph Theory}, number = {4}, pages = {365--394}, publisher = {Wiley}, title = {{Extending partial representations of circle graphs}}, doi = {10.1002/jgt.22436}, volume = {91}, year = {2019}, } @inbook{5793, abstract = {The transcription coactivator, Yes-associated protein (YAP), which is a nuclear effector of the Hippo signaling pathway, has been shown to be a mechano-transducer. By using mutant fish and human 3D spheroids, we have recently demonstrated that YAP is also a mechano-effector. YAP functions in three-dimensional (3D) morphogenesis of organ and global body shape by controlling actomyosin-mediated tissue tension. In this chapter, we present a platform that links the findings in fish embryos with human cells. The protocols for analyzing tissue tension-mediated global body shape/organ morphogenesis in vivo and ex vivo using medaka fish embryos and in vitro using human cell spheroids represent useful tools for unraveling the molecular mechanisms by which YAP functions in regulating global body/organ morphogenesis.}, author = {Asaoka, Yoichi and Morita, Hitoshi and Furumoto, Hiroko and Heisenberg, Carl-Philipp J and Furutani-Seiki, Makoto}, booktitle = {The hippo pathway}, editor = {Hergovich, Alexander}, isbn = {978-1-4939-8909-6}, pages = {167--181}, publisher = {Springer}, title = {{Studying YAP-mediated 3D morphogenesis using fish embryos and human spheroids}}, doi = {10.1007/978-1-4939-8910-2_14}, volume = {1893}, year = {2019}, } @article{5817, abstract = {We theoretically study the shapes of lipid vesicles confined to a spherical cavity, elaborating a framework based on the so-called limiting shapes constructed from geometrically simple structural elements such as double-membrane walls and edges. Partly inspired by numerical results, the proposed non-compartmentalized and compartmentalized limiting shapes are arranged in the bilayer-couple phase diagram which is then compared to its free-vesicle counterpart. We also compute the area-difference-elasticity phase diagram of the limiting shapes and we use it to interpret shape transitions experimentally observed in vesicles confined within another vesicle. The limiting-shape framework may be generalized to theoretically investigate the structure of certain cell organelles such as the mitochondrion.}, author = {Kavcic, Bor and Sakashita, A. and Noguchi, H. and Ziherl, P.}, issn = {1744-6848}, journal = {Soft Matter}, number = {4}, pages = {602--614}, publisher = {Royal Society of Chemistry}, title = {{Limiting shapes of confined lipid vesicles}}, doi = {10.1039/c8sm01956h}, volume = {15}, year = {2019}, } @article{5828, abstract = {Hippocampus is needed for both spatial working and reference memories. Here, using a radial eight-arm maze, we examined how the combined demand on these memories influenced CA1 place cell assemblies while reference memories were partially updated. This was contrasted with control tasks requiring only working memory or the update of reference memory. Reference memory update led to the reward-directed place field shifts at newly rewarded arms and to the gradual strengthening of firing in passes between newly rewarded arms but not between those passes that included a familiar-rewarded arm. At the maze center, transient network synchronization periods preferentially replayed trajectories of the next chosen arm in reference memory tasks but the previously visited arm in the working memory task. Hence, reference memory demand was uniquely associated with a gradual, goal novelty-related reorganization of place cell assemblies and with trajectory replay that reflected the animal's decision of which arm to visit next.}, author = {Xu, Haibing and Baracskay, Peter and O'Neill, Joseph and Csicsvari, Jozsef L}, issn = {10974199}, journal = {Neuron}, number = {1}, pages = {119--132.e4}, publisher = {Elsevier}, title = {{Assembly responses of hippocampal CA1 place cells predict learned behavior in goal-directed spatial tasks on the radial eight-arm maze}}, doi = {10.1016/j.neuron.2018.11.015}, volume = {101}, year = {2019}, } @article{5856, abstract = {We give a bound on the ground-state energy of a system of N non-interacting fermions in a three-dimensional cubic box interacting with an impurity particle via point interactions. We show that the change in energy compared to the system in the absence of the impurity is bounded in terms of the gas density and the scattering length of the interaction, independently of N. Our bound holds as long as the ratio of the mass of the impurity to the one of the gas particles is larger than a critical value m∗ ∗≈ 0.36 , which is the same regime for which we recently showed stability of the system.}, author = {Moser, Thomas and Seiringer, Robert}, issn = {14240637}, journal = {Annales Henri Poincare}, number = {4}, pages = {1325–1365}, publisher = {Springer}, title = {{Energy contribution of a point-interacting impurity in a Fermi gas}}, doi = {10.1007/s00023-018-00757-0}, volume = {20}, year = {2019}, }