---
_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'
...