--- _id: '7412' abstract: - lang: eng text: 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. article_processing_charge: No article_type: original author: - first_name: Dimitris full_name: Achlioptas, Dimitris last_name: Achlioptas - first_name: Fotis full_name: Iliopoulos, Fotis last_name: Iliopoulos - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: Achlioptas D, Iliopoulos F, Kolmogorov V. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 2019;48(5):1583-1602. doi:10.1137/16m109332x apa: Achlioptas, D., Iliopoulos, F., & Kolmogorov, V. (2019). A local lemma for focused stochastical algorithms. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/16m109332x chicago: Achlioptas, Dimitris, Fotis Iliopoulos, and Vladimir Kolmogorov. “A Local Lemma for Focused Stochastical Algorithms.” SIAM Journal on Computing. SIAM, 2019. https://doi.org/10.1137/16m109332x. ieee: D. Achlioptas, F. Iliopoulos, and V. Kolmogorov, “A local lemma for focused stochastical algorithms,” SIAM Journal on Computing, vol. 48, no. 5. SIAM, pp. 1583–1602, 2019. ista: Achlioptas D, Iliopoulos F, Kolmogorov V. 2019. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 48(5), 1583–1602. mla: Achlioptas, Dimitris, et al. “A Local Lemma for Focused Stochastical Algorithms.” SIAM Journal on Computing, vol. 48, no. 5, SIAM, 2019, pp. 1583–602, doi:10.1137/16m109332x. short: D. Achlioptas, F. Iliopoulos, V. Kolmogorov, SIAM Journal on Computing 48 (2019) 1583–1602. date_created: 2020-01-30T09:27:32Z date_published: 2019-10-31T00:00:00Z date_updated: 2023-09-06T15:25:29Z day: '31' department: - _id: VlKo doi: 10.1137/16m109332x ec_funded: 1 external_id: arxiv: - '1809.01537' isi: - '000493900200005' intvolume: ' 48' isi: 1 issue: '5' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1809.01537 month: '10' oa: 1 oa_version: Preprint page: 1583-1602 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication: SIAM Journal on Computing publication_identifier: eissn: - 1095-7111 issn: - 0097-5397 publication_status: published publisher: SIAM quality_controlled: '1' scopus_import: '1' status: public title: A local lemma for focused stochastical algorithms type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 48 year: '2019' ... --- _id: '7418' abstract: - lang: eng text: 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. article_number: '151' article_processing_charge: No article_type: original author: - first_name: Ondřej full_name: Karlík, Ondřej last_name: Karlík - first_name: Martin full_name: Šik, Martin last_name: Šik - first_name: Petr full_name: Vévoda, Petr last_name: Vévoda - first_name: Tomas full_name: Skrivan, Tomas id: 486A5A46-F248-11E8-B48F-1D18A9856A87 last_name: Skrivan - first_name: Jaroslav full_name: Křivánek, Jaroslav last_name: Křivánek citation: ama: 'Karlík O, Šik M, Vévoda P, Skrivan T, Křivánek J. MIS compensation: Optimizing sampling techniques in multiple importance sampling. ACM Transactions on Graphics. 2019;38(6). doi:10.1145/3355089.3356565' apa: 'Karlík, O., Šik, M., Vévoda, P., Skrivan, T., & Křivánek, J. (2019). MIS compensation: Optimizing sampling techniques in multiple importance sampling. ACM Transactions on Graphics. ACM. https://doi.org/10.1145/3355089.3356565' chicago: 'Karlík, Ondřej, Martin Šik, Petr Vévoda, Tomas Skrivan, and Jaroslav Křivánek. “MIS Compensation: Optimizing Sampling Techniques in Multiple Importance Sampling.” ACM Transactions on Graphics. ACM, 2019. https://doi.org/10.1145/3355089.3356565.' ieee: 'O. Karlík, M. Šik, P. Vévoda, T. Skrivan, and J. Křivánek, “MIS compensation: Optimizing sampling techniques in multiple importance sampling,” ACM Transactions on Graphics, vol. 38, no. 6. ACM, 2019.' ista: 'Karlík O, Šik M, Vévoda P, Skrivan T, Křivánek J. 2019. MIS compensation: Optimizing sampling techniques in multiple importance sampling. ACM Transactions on Graphics. 38(6), 151.' mla: 'Karlík, Ondřej, et al. “MIS Compensation: Optimizing Sampling Techniques in Multiple Importance Sampling.” ACM Transactions on Graphics, vol. 38, no. 6, 151, ACM, 2019, doi:10.1145/3355089.3356565.' short: O. Karlík, M. Šik, P. Vévoda, T. Skrivan, J. Křivánek, ACM Transactions on Graphics 38 (2019). date_created: 2020-01-30T10:19:43Z date_published: 2019-11-01T00:00:00Z date_updated: 2023-09-06T15:22:23Z day: '01' department: - _id: ChWo doi: 10.1145/3355089.3356565 external_id: isi: - '000498397300001' intvolume: ' 38' isi: 1 issue: '6' language: - iso: eng month: '11' oa_version: None publication: ACM Transactions on Graphics publication_identifier: eissn: - 1557-7368 issn: - 0730-0301 publication_status: published publisher: ACM quality_controlled: '1' scopus_import: '1' status: public title: 'MIS compensation: Optimizing sampling techniques in multiple importance sampling' type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 38 year: '2019' ... --- _id: '7413' abstract: - lang: eng text: 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. article_processing_charge: No article_type: original author: - first_name: Chiara full_name: Boccato, Chiara id: 342E7E22-F248-11E8-B48F-1D18A9856A87 last_name: Boccato - first_name: Christian full_name: Brennecke, Christian last_name: Brennecke - first_name: Serena full_name: Cenatiempo, Serena last_name: Cenatiempo - first_name: Benjamin full_name: Schlein, Benjamin last_name: Schlein citation: ama: Boccato C, Brennecke C, Cenatiempo S, Schlein B. Bogoliubov theory in the Gross–Pitaevskii limit. Acta Mathematica. 2019;222(2):219-335. doi:10.4310/acta.2019.v222.n2.a1 apa: Boccato, C., Brennecke, C., Cenatiempo, S., & Schlein, B. (2019). Bogoliubov theory in the Gross–Pitaevskii limit. Acta Mathematica. International Press of Boston. https://doi.org/10.4310/acta.2019.v222.n2.a1 chicago: Boccato, Chiara, Christian Brennecke, Serena Cenatiempo, and Benjamin Schlein. “Bogoliubov Theory in the Gross–Pitaevskii Limit.” Acta Mathematica. International Press of Boston, 2019. https://doi.org/10.4310/acta.2019.v222.n2.a1. ieee: C. Boccato, C. Brennecke, S. Cenatiempo, and B. Schlein, “Bogoliubov theory in the Gross–Pitaevskii limit,” Acta Mathematica, vol. 222, no. 2. International Press of Boston, pp. 219–335, 2019. ista: Boccato C, Brennecke C, Cenatiempo S, Schlein B. 2019. Bogoliubov theory in the Gross–Pitaevskii limit. Acta Mathematica. 222(2), 219–335. mla: Boccato, Chiara, et al. “Bogoliubov Theory in the Gross–Pitaevskii Limit.” Acta Mathematica, vol. 222, no. 2, International Press of Boston, 2019, pp. 219–335, doi:10.4310/acta.2019.v222.n2.a1. short: C. Boccato, C. Brennecke, S. Cenatiempo, B. Schlein, Acta Mathematica 222 (2019) 219–335. date_created: 2020-01-30T09:30:41Z date_published: 2019-06-07T00:00:00Z date_updated: 2023-09-06T15:24:31Z day: '07' department: - _id: RoSe doi: 10.4310/acta.2019.v222.n2.a1 external_id: arxiv: - '1801.01389' isi: - '000495865300001' intvolume: ' 222' isi: 1 issue: '2' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1801.01389 month: '06' oa: 1 oa_version: Preprint page: 219-335 publication: Acta Mathematica publication_identifier: eissn: - 1871-2509 issn: - 0001-5962 publication_status: published publisher: International Press of Boston quality_controlled: '1' scopus_import: '1' status: public title: Bogoliubov theory in the Gross–Pitaevskii limit type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 222 year: '2019' ... --- _id: '7393' abstract: - lang: eng text: 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. article_number: eaav9963 article_processing_charge: No article_type: original author: - first_name: Hernán E. full_name: Morales, Hernán E. last_name: Morales - first_name: Rui full_name: Faria, Rui last_name: Faria - first_name: Kerstin full_name: Johannesson, Kerstin last_name: Johannesson - first_name: Tomas full_name: Larsson, Tomas last_name: Larsson - first_name: Marina full_name: Panova, Marina last_name: Panova - first_name: Anja M full_name: Westram, Anja M id: 3C147470-F248-11E8-B48F-1D18A9856A87 last_name: Westram orcid: 0000-0003-1050-4969 - first_name: Roger K. full_name: Butlin, Roger K. last_name: Butlin citation: ama: 'Morales HE, Faria R, Johannesson K, et al. Genomic architecture of parallel ecological divergence: Beyond a single environmental contrast. Science Advances. 2019;5(12). doi:10.1126/sciadv.aav9963' apa: 'Morales, H. E., Faria, R., Johannesson, K., Larsson, T., Panova, M., Westram, A. M., & Butlin, R. K. (2019). Genomic architecture of parallel ecological divergence: Beyond a single environmental contrast. Science Advances. AAAS. https://doi.org/10.1126/sciadv.aav9963' chicago: 'Morales, Hernán E., Rui Faria, Kerstin Johannesson, Tomas Larsson, Marina Panova, Anja M Westram, and Roger K. Butlin. “Genomic Architecture of Parallel Ecological Divergence: Beyond a Single Environmental Contrast.” Science Advances. AAAS, 2019. https://doi.org/10.1126/sciadv.aav9963.' ieee: 'H. E. Morales et al., “Genomic architecture of parallel ecological divergence: Beyond a single environmental contrast,” Science Advances, vol. 5, no. 12. AAAS, 2019.' ista: 'Morales HE, Faria R, Johannesson K, Larsson T, Panova M, Westram AM, Butlin RK. 2019. Genomic architecture of parallel ecological divergence: Beyond a single environmental contrast. Science Advances. 5(12), eaav9963.' mla: 'Morales, Hernán E., et al. “Genomic Architecture of Parallel Ecological Divergence: Beyond a Single Environmental Contrast.” Science Advances, vol. 5, no. 12, eaav9963, AAAS, 2019, doi:10.1126/sciadv.aav9963.' short: H.E. Morales, R. Faria, K. Johannesson, T. Larsson, M. Panova, A.M. Westram, R.K. Butlin, Science Advances 5 (2019). date_created: 2020-01-29T15:58:27Z date_published: 2019-12-04T00:00:00Z date_updated: 2023-09-06T15:35:56Z day: '04' ddc: - '570' department: - _id: NiBa doi: 10.1126/sciadv.aav9963 ec_funded: 1 external_id: isi: - '000505069600008' pmid: - '31840052' file: - access_level: open_access checksum: af99a5dcdc66c6d6102051faf3be48d8 content_type: application/pdf creator: dernst date_created: 2020-02-03T13:33:25Z date_updated: 2020-07-14T12:47:57Z file_id: '7442' file_name: 2019_ScienceAdvances_Morales.pdf file_size: 1869449 relation: main_file file_date_updated: 2020-07-14T12:47:57Z has_accepted_license: '1' intvolume: ' 5' isi: 1 issue: '12' language: - iso: eng license: https://creativecommons.org/licenses/by-nc/4.0/ month: '12' oa: 1 oa_version: Published Version pmid: 1 project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships - _id: 265B41B8-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '797747' name: Theoretical and empirical approaches to understanding Parallel Adaptation publication: Science Advances publication_identifier: issn: - 2375-2548 publication_status: published publisher: AAAS quality_controlled: '1' scopus_import: '1' status: public title: 'Genomic architecture of parallel ecological divergence: Beyond a single environmental contrast' tmp: image: /images/cc_by_nc.png legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) short: CC BY-NC (4.0) type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 5 year: '2019' ... --- _id: '7397' abstract: - lang: eng text: 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). article_processing_charge: No article_type: original author: - first_name: Jose M full_name: Lopez Alonso, Jose M id: 40770848-F248-11E8-B48F-1D18A9856A87 last_name: Lopez Alonso orcid: 0000-0002-0384-2022 - first_name: George H full_name: Choueiri, George H id: 448BD5BC-F248-11E8-B48F-1D18A9856A87 last_name: Choueiri - first_name: Björn full_name: Hof, Björn id: 3A374330-F248-11E8-B48F-1D18A9856A87 last_name: Hof orcid: 0000-0003-2057-2754 citation: ama: Lopez Alonso JM, Choueiri GH, Hof B. Dynamics of viscoelastic pipe flow at low Reynolds numbers in the maximum drag reduction limit. Journal of Fluid Mechanics. 2019;874:699-719. doi:10.1017/jfm.2019.486 apa: Lopez Alonso, J. M., Choueiri, G. H., & Hof, B. (2019). Dynamics of viscoelastic pipe flow at low Reynolds numbers in the maximum drag reduction limit. Journal of Fluid Mechanics. CUP. https://doi.org/10.1017/jfm.2019.486 chicago: Lopez Alonso, Jose M, George H Choueiri, and Björn Hof. “Dynamics of Viscoelastic Pipe Flow at Low Reynolds Numbers in the Maximum Drag Reduction Limit.” Journal of Fluid Mechanics. CUP, 2019. https://doi.org/10.1017/jfm.2019.486. ieee: J. M. Lopez Alonso, G. H. Choueiri, and B. Hof, “Dynamics of viscoelastic pipe flow at low Reynolds numbers in the maximum drag reduction limit,” Journal of Fluid Mechanics, vol. 874. CUP, pp. 699–719, 2019. ista: Lopez Alonso JM, Choueiri GH, Hof B. 2019. Dynamics of viscoelastic pipe flow at low Reynolds numbers in the maximum drag reduction limit. Journal of Fluid Mechanics. 874, 699–719. mla: Lopez Alonso, Jose M., et al. “Dynamics of Viscoelastic Pipe Flow at Low Reynolds Numbers in the Maximum Drag Reduction Limit.” Journal of Fluid Mechanics, vol. 874, CUP, 2019, pp. 699–719, doi:10.1017/jfm.2019.486. short: J.M. Lopez Alonso, G.H. Choueiri, B. Hof, Journal of Fluid Mechanics 874 (2019) 699–719. date_created: 2020-01-29T16:05:19Z date_published: 2019-09-10T00:00:00Z date_updated: 2023-09-06T15:36:36Z day: '10' department: - _id: BjHo doi: 10.1017/jfm.2019.486 external_id: arxiv: - '1808.04080' isi: - '000475349900001' intvolume: ' 874' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1808.04080 month: '09' oa: 1 oa_version: Preprint page: 699-719 publication: Journal of Fluid Mechanics publication_identifier: eissn: - 1469-7645 issn: - 0022-1120 publication_status: published publisher: CUP quality_controlled: '1' scopus_import: '1' status: public title: Dynamics of viscoelastic pipe flow at low Reynolds numbers in the maximum drag reduction limit type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 874 year: '2019' ...