@article{7412, abstract = {We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while (we hope) not introducing many new violations. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lovász local lemma (LLL), a nonconstructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement, and one needs to step outside the class. Here we introduce the notion of measure distortion and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary algorithm of such type and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure.}, author = {Achlioptas, Dimitris and Iliopoulos, Fotis and Kolmogorov, Vladimir}, issn = {1095-7111}, journal = {SIAM Journal on Computing}, number = {5}, pages = {1583--1602}, publisher = {SIAM}, title = {{A local lemma for focused stochastical algorithms}}, doi = {10.1137/16m109332x}, volume = {48}, year = {2019}, } @article{7418, abstract = {Multiple importance sampling (MIS) has become an indispensable tool in Monte Carlo rendering, widely accepted as a near-optimal solution for combining different sampling techniques. But an MIS combination, using the common balance or power heuristics, often results in an overly defensive estimator, leading to high variance. We show that by generalizing the MIS framework, variance can be substantially reduced. Specifically, we optimize one of the combined sampling techniques so as to decrease the overall variance of the resulting MIS estimator. We apply the approach to the computation of direct illumination due to an HDR environment map and to the computation of global illumination using a path guiding algorithm. The implementation can be as simple as subtracting a constant value from the tabulated sampling density done entirely in a preprocessing step. This produces a consistent noise reduction in all our tests with no negative influence on run time, no artifacts or bias, and no failure cases.}, author = {Karlík, Ondřej and Šik, Martin and Vévoda, Petr and Skrivan, Tomas and Křivánek, Jaroslav}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {6}, publisher = {ACM}, title = {{MIS compensation: Optimizing sampling techniques in multiple importance sampling}}, doi = {10.1145/3355089.3356565}, volume = {38}, year = {2019}, } @article{7413, abstract = {We consider Bose gases consisting of N particles trapped in a box with volume one and interacting through a repulsive potential with scattering length of order N−1 (Gross–Pitaevskii regime). We determine the ground state energy and the low-energy excitation spectrum, up to errors vanishing as N→∞. Our results confirm Bogoliubov’s predictions.}, author = {Boccato, Chiara and Brennecke, Christian and Cenatiempo, Serena and Schlein, Benjamin}, issn = {1871-2509}, journal = {Acta Mathematica}, number = {2}, pages = {219--335}, publisher = {International Press of Boston}, title = {{Bogoliubov theory in the Gross–Pitaevskii limit}}, doi = {10.4310/acta.2019.v222.n2.a1}, volume = {222}, year = {2019}, } @article{7393, abstract = {The study of parallel ecological divergence provides important clues to the operation of natural selection. Parallel divergence often occurs in heterogeneous environments with different kinds of environmental gradients in different locations, but the genomic basis underlying this process is unknown. We investigated the genomics of rapid parallel adaptation in the marine snail Littorina saxatilis in response to two independent environmental axes (crab-predation versus wave-action and low-shore versus high-shore). Using pooled whole-genome resequencing, we show that sharing of genomic regions of high differentiation between environments is generally low but increases at smaller spatial scales. We identify different shared genomic regions of divergence for each environmental axis and show that most of these regions overlap with candidate chromosomal inversions. Several inversion regions are divergent and polymorphic across many localities. We argue that chromosomal inversions could store shared variation that fuels rapid parallel adaptation to heterogeneous environments, possibly as balanced polymorphism shared by adaptive gene flow.}, author = {Morales, Hernán E. and Faria, Rui and Johannesson, Kerstin and Larsson, Tomas and Panova, Marina and Westram, Anja M and Butlin, Roger K.}, issn = {2375-2548}, journal = {Science Advances}, number = {12}, publisher = {AAAS}, title = {{Genomic architecture of parallel ecological divergence: Beyond a single environmental contrast}}, doi = {10.1126/sciadv.aav9963}, volume = {5}, year = {2019}, } @article{7397, abstract = {Polymer additives can substantially reduce the drag of turbulent flows and the upperlimit, the so called “maximum drag reduction” (MDR) asymptote is universal, i.e. inde-pendent of the type of polymer and solvent used. Until recently, the consensus was that,in this limit, flows are in a marginal state where only a minimal level of turbulence activ-ity persists. Observations in direct numerical simulations using minimal sized channelsappeared to support this view and reported long “hibernation” periods where turbu-lence is marginalized. In simulations of pipe flow we find that, indeed, with increasingWeissenberg number (Wi), turbulence expresses long periods of hibernation if the domainsize is small. However, with increasing pipe length, the temporal hibernation continuouslyalters to spatio-temporal intermittency and here the flow consists of turbulent puffs sur-rounded by laminar flow. Moreover, upon an increase in Wi, the flow fully relaminarises,in agreement with recent experiments. At even larger Wi, a different instability is en-countered causing a drag increase towards MDR. Our findings hence link earlier minimalflow unit simulations with recent experiments and confirm that the addition of polymersinitially suppresses Newtonian turbulence and leads to a reverse transition. The MDRstate on the other hand results from a separate instability and the underlying dynamicscorresponds to the recently proposed state of elasto-inertial-turbulence (EIT).}, author = {Lopez Alonso, Jose M and Choueiri, George H and Hof, Björn}, issn = {1469-7645}, journal = {Journal of Fluid Mechanics}, pages = {699--719}, publisher = {CUP}, title = {{Dynamics of viscoelastic pipe flow at low Reynolds numbers in the maximum drag reduction limit}}, doi = {10.1017/jfm.2019.486}, volume = {874}, 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{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}, } @phdthesis{6957, abstract = {In many shear flows like pipe flow, plane Couette flow, plane Poiseuille flow, etc. turbulence emerges subcritically. Here, when subjected to strong enough perturbations, the flow becomes turbulent in spite of the laminar base flow being linearly stable. The nature of this instability has puzzled the scientific community for decades. At onset, turbulence appears in localized patches and flows are spatio-temporally intermittent. In pipe flow the localized turbulent structures are referred to as puffs and in planar flows like plane Couette and channel flow, patches arise in the form of localized oblique bands. In this thesis, we study the onset of turbulence in channel flow in direct numerical simulations from a dynamical system theory perspective, as well as by performing experiments in a large aspect ratio channel. The aim of the experimental work is to determine the critical Reynolds number where turbulence first becomes sustained. Recently, the onset of turbulence has been described in analogy to absorbing state phase transition (i.e. directed percolation). In particular, it has been shown that the critical point can be estimated from the competition between spreading and decay processes. Here, by performing experiments, we identify the mechanisms underlying turbulence proliferation in channel flow and find the critical Reynolds number, above which turbulence becomes sustained. Above the critical point, the continuous growth at the tip of the stripes outweighs the stochastic shedding of turbulent patches at the tail and the stripes expand. For growing stripes, the probability to decay decreases while the probability of stripe splitting increases. Consequently, and unlike for the puffs in pipe flow, neither of these two processes is time-independent i.e. memoryless. Coupling between stripe expansion and creation of new stripes via splitting leads to a significantly lower critical point ($Re_c=670+/-10$) than most earlier studies suggest. While the above approach sheds light on how turbulence first becomes sustained, it provides no insight into the origin of the stripes themselves. In the numerical part of the thesis we investigate how turbulent stripes form from invariant solutions of the Navier-Stokes equations. The origin of these turbulent stripes can be identified by applying concepts from the dynamical system theory. In doing so, we identify the exact coherent structures underlying stripes and their bifurcations and how they give rise to the turbulent attractor in phase space. We first report a family of localized nonlinear traveling wave solutions of the Navier-Stokes equations in channel flow. These solutions show structural similarities with turbulent stripes in experiments like obliqueness, quasi-streamwise streaks and vortices, etc. A parametric study of these traveling wave solution is performed, with parameters like Reynolds number, stripe tilt angle and domain size, including the stability of the solutions. These solutions emerge through saddle-node bifurcations and form a phase space skeleton for the turbulent stripes observed in the experiments. The lower branches of these TW solutions at different tilt angles undergo Hopf bifurcation and new solutions branches of relative periodic orbits emerge. These RPO solutions do not belong to the same family and therefore the routes to chaos for different angles are different. In shear flows, turbulence at onset is transient in nature. Consequently,turbulence can not be tracked to lower Reynolds numbers, where the dynamics may simplify. Before this happens, turbulence becomes short-lived and laminarizes. In the last part of the thesis, we show that using numerical simulations we can continue turbulent stripes in channel flow past the 'relaminarization barrier' all the way to their origin. Here, turbulent stripe dynamics simplifies and the fluctuations are no longer stochastic and the stripe settles down to a relative periodic orbit. This relative periodic orbit originates from the aforementioned traveling wave solutions. Starting from the relative periodic orbit, a small increase in speed i.e. Reynolds number gives rise to chaos and the attractor dimension sharply increases in contrast to the classical transition scenario where the instabilities affect the flow globally and give rise to much more gradual route to turbulence.}, author = {Paranjape, Chaitanya S}, issn = {2663-337X}, keywords = {Instabilities, Turbulence, Nonlinear dynamics}, pages = {138}, publisher = {Institute of Science and Technology Austria}, title = {{Onset of turbulence in plane Poiseuille flow}}, doi = {10.15479/AT:ISTA:6957}, year = {2019}, } @article{6182, abstract = {We consider large random matrices with a general slowly decaying correlation among its entries. We prove universality of the local eigenvalue statistics and optimal local laws for the resolvent away from the spectral edges, generalizing the recent result of Ajanki et al. [‘Stability of the matrix Dyson equation and random matrices with correlations’, Probab. Theory Related Fields 173(1–2) (2019), 293–373] to allow slow correlation decay and arbitrary expectation. The main novel tool is a systematic diagrammatic control of a multivariate cumulant expansion.}, author = {Erdös, László and Krüger, Torben H and Schröder, Dominik J}, issn = {20505094}, journal = {Forum of Mathematics, Sigma}, publisher = {Cambridge University Press}, title = {{Random matrices with slow correlation decay}}, doi = {10.1017/fms.2019.2}, volume = {7}, year = {2019}, }