---
OA_place: repository
OA_type: green
_id: '21623'
abstract:
- lang: eng
text: We present a method to overcome the Manley-Rowe limit in a Q-factor
engineered multimodal nonlinear cavity. Cascading nonlinear processes enable continuous-wave
terahertz generation with a theoretical conversion efficiency of 98.8%.
article_number: FTu2J.3
article_processing_charge: No
author:
- first_name: Yannick
full_name: Salamin, Yannick
last_name: Salamin
- first_name: Charles
full_name: Roques-Carmes, Charles
id: e2e68fc9-6505-11ef-a541-eb4e72cc3e82
last_name: Roques-Carmes
- first_name: Zin
full_name: Lin, Zin
last_name: Lin
- first_name: Steven G.
full_name: Johnson, Steven G.
last_name: Johnson
- first_name: Marin
full_name: Soljačić, Marin
last_name: Soljačić
citation:
ama: 'Salamin Y, Roques-Carmes C, Lin Z, Johnson SG, Soljačić M. Overcoming the
Manley-Rowe limit for CW terahertz generation in Q-engineered multimodal cavity.
In: Conference on Lasers and Electro-Optics. Optica Publishing Group; 2021.
doi:10.1364/cleo_qels.2021.ftu2j.3'
apa: 'Salamin, Y., Roques-Carmes, C., Lin, Z., Johnson, S. G., & Soljačić, M.
(2021). Overcoming the Manley-Rowe limit for CW terahertz generation in Q-engineered
multimodal cavity. In Conference on Lasers and Electro-Optics. San Jose,
CA, United States: Optica Publishing Group. https://doi.org/10.1364/cleo_qels.2021.ftu2j.3'
chicago: Salamin, Yannick, Charles Roques-Carmes, Zin Lin, Steven G. Johnson, and
Marin Soljačić. “Overcoming the Manley-Rowe Limit for CW Terahertz Generation
in Q-Engineered Multimodal Cavity.” In Conference on Lasers and Electro-Optics.
Optica Publishing Group, 2021. https://doi.org/10.1364/cleo_qels.2021.ftu2j.3.
ieee: Y. Salamin, C. Roques-Carmes, Z. Lin, S. G. Johnson, and M. Soljačić, “Overcoming
the Manley-Rowe limit for CW terahertz generation in Q-engineered multimodal cavity,”
in Conference on Lasers and Electro-Optics, San Jose, CA, United States,
2021.
ista: 'Salamin Y, Roques-Carmes C, Lin Z, Johnson SG, Soljačić M. 2021. Overcoming
the Manley-Rowe limit for CW terahertz generation in Q-engineered multimodal cavity.
Conference on Lasers and Electro-Optics. CLEO: Fundamental Science, FTu2J.3.'
mla: Salamin, Yannick, et al. “Overcoming the Manley-Rowe Limit for CW Terahertz
Generation in Q-Engineered Multimodal Cavity.” Conference on Lasers and Electro-Optics,
FTu2J.3, Optica Publishing Group, 2021, doi:10.1364/cleo_qels.2021.ftu2j.3.
short: Y. Salamin, C. Roques-Carmes, Z. Lin, S.G. Johnson, M. Soljačić, in:, Conference
on Lasers and Electro-Optics, Optica Publishing Group, 2021.
conference:
end_date: 2021-05-14
location: San Jose, CA, United States
name: 'CLEO: Fundamental Science'
start_date: 2021-05-09
date_created: 2026-03-30T12:22:48Z
date_published: 2021-06-01T00:00:00Z
date_updated: 2026-05-04T13:13:11Z
day: '01'
doi: 10.1364/cleo_qels.2021.ftu2j.3
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://hdl.handle.net/1721.1/142554.2
month: '06'
oa: 1
oa_version: Accepted Version
publication: Conference on Lasers and Electro-Optics
publication_identifier:
eisbn:
- '9781943580910'
publication_status: published
publisher: Optica Publishing Group
quality_controlled: '1'
status: public
title: Overcoming the Manley-Rowe limit for CW terahertz generation in Q-engineered
multimodal cavity
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '14987'
abstract:
- lang: eng
text: "The goal of zero-shot learning is to construct a classifier that can identify
object classes for which no training examples are available. When training data
for some of the object classes is available but not for others, the name generalized
zero-shot learning is commonly used.\r\nIn a wider sense, the phrase zero-shot
is also used to describe other machine learning-based approaches that require
no training data from the problem of interest, such as zero-shot action recognition
or zero-shot machine translation."
article_processing_charge: No
author:
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Lampert C. Zero-Shot Learning. In: Ikeuchi K, ed. Computer Vision.
2nd ed. Cham: Springer; 2021:1395-1397. doi:10.1007/978-3-030-63416-2_874'
apa: 'Lampert, C. (2021). Zero-Shot Learning. In K. Ikeuchi (Ed.), Computer Vision
(2nd ed., pp. 1395–1397). Cham: Springer. https://doi.org/10.1007/978-3-030-63416-2_874'
chicago: 'Lampert, Christoph. “Zero-Shot Learning.” In Computer Vision, edited
by Katsushi Ikeuchi, 2nd ed., 1395–97. Cham: Springer, 2021. https://doi.org/10.1007/978-3-030-63416-2_874.'
ieee: 'C. Lampert, “Zero-Shot Learning,” in Computer Vision, 2nd ed., K.
Ikeuchi, Ed. Cham: Springer, 2021, pp. 1395–1397.'
ista: 'Lampert C. 2021.Zero-Shot Learning. In: Computer Vision. , 1395–1397.'
mla: Lampert, Christoph. “Zero-Shot Learning.” Computer Vision, edited by
Katsushi Ikeuchi, 2nd ed., Springer, 2021, pp. 1395–97, doi:10.1007/978-3-030-63416-2_874.
short: C. Lampert, in:, K. Ikeuchi (Ed.), Computer Vision, 2nd ed., Springer, Cham,
2021, pp. 1395–1397.
corr_author: '1'
date_created: 2024-02-14T14:05:32Z
date_published: 2021-10-13T00:00:00Z
date_updated: 2024-10-09T21:08:12Z
day: '13'
department:
- _id: ChLa
doi: 10.1007/978-3-030-63416-2_874
edition: '2'
editor:
- first_name: Katsushi
full_name: Ikeuchi, Katsushi
last_name: Ikeuchi
language:
- iso: eng
month: '10'
oa_version: None
page: 1395-1397
place: Cham
publication: Computer Vision
publication_identifier:
eisbn:
- '9783030634162'
isbn:
- '9783030634155'
publication_status: published
publisher: Springer
quality_controlled: '1'
status: public
title: Zero-Shot Learning
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '15137'
abstract:
- lang: eng
text: Characteristic properties of type III CRISPR-Cas systems include recognition
of target RNA and the subsequent induction of a multifaceted immune response.
This involves sequence-specific cleavage of the target RNA and production of cyclic
oligoadenylate (cOA) molecules. Here we report that an exposed seed region at
the 3′ end of the crRNA is essential for target RNA binding and cleavage, whereas
cOA production requires base pairing at the 5′ end of the crRNA. Moreover, we
uncover that the variation in the size and composition of type III complexes within
a single host results in variable seed regions. This may prevent escape by invading
genetic elements, while controlling cOA production tightly to prevent unnecessary
damage to the host. Lastly, we use these findings to develop a new diagnostic
tool, SCOPE, for the specific detection of SARS-CoV-2 from human nasal swab samples,
revealing sensitivities in the atto-molar range.
article_number: '5033'
article_processing_charge: Yes
article_type: original
author:
- first_name: Jurre A.
full_name: Steens, Jurre A.
last_name: Steens
- first_name: Yifan
full_name: Zhu, Yifan
last_name: Zhu
- first_name: David W.
full_name: Taylor, David W.
last_name: Taylor
- first_name: Jack Peter Kelly
full_name: Bravo, Jack Peter Kelly
id: 96aecfa5-8931-11ee-af30-aa6a5d6eee0e
last_name: Bravo
orcid: 0000-0003-0456-0753
- first_name: Stijn H. P.
full_name: Prinsen, Stijn H. P.
last_name: Prinsen
- first_name: Cor D.
full_name: Schoen, Cor D.
last_name: Schoen
- first_name: Bart J. F.
full_name: Keijser, Bart J. F.
last_name: Keijser
- first_name: Michel
full_name: Ossendrijver, Michel
last_name: Ossendrijver
- first_name: L. Marije
full_name: Hofstra, L. Marije
last_name: Hofstra
- first_name: Stan J. J.
full_name: Brouns, Stan J. J.
last_name: Brouns
- first_name: Akeo
full_name: Shinkai, Akeo
last_name: Shinkai
- first_name: John
full_name: van der Oost, John
last_name: van der Oost
- first_name: Raymond H. J.
full_name: Staals, Raymond H. J.
last_name: Staals
citation:
ama: Steens JA, Zhu Y, Taylor DW, et al. SCOPE enables type III CRISPR-Cas diagnostics
using flexible targeting and stringent CARF ribonuclease activation. Nature
Communications. 2021;12. doi:10.1038/s41467-021-25337-5
apa: Steens, J. A., Zhu, Y., Taylor, D. W., Bravo, J. P. K., Prinsen, S. H. P.,
Schoen, C. D., … Staals, R. H. J. (2021). SCOPE enables type III CRISPR-Cas diagnostics
using flexible targeting and stringent CARF ribonuclease activation. Nature
Communications. Springer Nature. https://doi.org/10.1038/s41467-021-25337-5
chicago: Steens, Jurre A., Yifan Zhu, David W. Taylor, Jack Peter Kelly Bravo, Stijn
H. P. Prinsen, Cor D. Schoen, Bart J. F. Keijser, et al. “SCOPE Enables Type III
CRISPR-Cas Diagnostics Using Flexible Targeting and Stringent CARF Ribonuclease
Activation.” Nature Communications. Springer Nature, 2021. https://doi.org/10.1038/s41467-021-25337-5.
ieee: J. A. Steens et al., “SCOPE enables type III CRISPR-Cas diagnostics
using flexible targeting and stringent CARF ribonuclease activation,” Nature
Communications, vol. 12. Springer Nature, 2021.
ista: Steens JA, Zhu Y, Taylor DW, Bravo JPK, Prinsen SHP, Schoen CD, Keijser BJF,
Ossendrijver M, Hofstra LM, Brouns SJJ, Shinkai A, van der Oost J, Staals RHJ.
2021. SCOPE enables type III CRISPR-Cas diagnostics using flexible targeting and
stringent CARF ribonuclease activation. Nature Communications. 12, 5033.
mla: Steens, Jurre A., et al. “SCOPE Enables Type III CRISPR-Cas Diagnostics Using
Flexible Targeting and Stringent CARF Ribonuclease Activation.” Nature Communications,
vol. 12, 5033, Springer Nature, 2021, doi:10.1038/s41467-021-25337-5.
short: J.A. Steens, Y. Zhu, D.W. Taylor, J.P.K. Bravo, S.H.P. Prinsen, C.D. Schoen,
B.J.F. Keijser, M. Ossendrijver, L.M. Hofstra, S.J.J. Brouns, A. Shinkai, J. van
der Oost, R.H.J. Staals, Nature Communications 12 (2021).
date_created: 2024-03-20T10:42:33Z
date_published: 2021-08-19T00:00:00Z
date_updated: 2024-06-04T06:11:54Z
day: '19'
doi: 10.1038/s41467-021-25337-5
extern: '1'
external_id:
pmid:
- '34413302'
intvolume: ' 12'
keyword:
- General Physics and Astronomy
- General Biochemistry
- Genetics and Molecular Biology
- General Chemistry
- Multidisciplinary
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1038/s41467-021-25337-5
month: '08'
oa: 1
oa_version: Published Version
pmid: 1
publication: Nature Communications
publication_identifier:
issn:
- 2041-1723
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: SCOPE enables type III CRISPR-Cas diagnostics using flexible targeting and
stringent CARF ribonuclease activation
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12
year: '2021'
...
---
_id: '15140'
abstract:
- lang: eng
text: Remdesivir is a nucleoside analog approved by the US FDA for treatment of
COVID-19. Here, we present a 3.9-Å-resolution cryo-EM reconstruction of a remdesivir-stalled
RNA-dependent RNA polymerase complex, revealing full incorporation of 3 copies
of remdesivir monophosphate (RMP) and a partially incorporated fourth RMP in the
active site. The structure reveals that RMP blocks RNA translocation after incorporation
of 3 bases following RMP, resulting in delayed chain termination, which can guide
the rational design of improved antiviral drugs.
article_processing_charge: No
article_type: original
author:
- first_name: Jack Peter Kelly
full_name: Bravo, Jack Peter Kelly
id: 96aecfa5-8931-11ee-af30-aa6a5d6eee0e
last_name: Bravo
orcid: 0000-0003-0456-0753
- first_name: Tyler L.
full_name: Dangerfield, Tyler L.
last_name: Dangerfield
- first_name: David W.
full_name: Taylor, David W.
last_name: Taylor
- first_name: Kenneth A.
full_name: Johnson, Kenneth A.
last_name: Johnson
citation:
ama: Bravo JPK, Dangerfield TL, Taylor DW, Johnson KA. Remdesivir is a delayed translocation
inhibitor of SARS-CoV-2 replication. Molecular Cell. 2021;81(7):1548-1552.e4.
doi:10.1016/j.molcel.2021.01.035
apa: Bravo, J. P. K., Dangerfield, T. L., Taylor, D. W., & Johnson, K. A. (2021).
Remdesivir is a delayed translocation inhibitor of SARS-CoV-2 replication. Molecular
Cell. Elsevier. https://doi.org/10.1016/j.molcel.2021.01.035
chicago: Bravo, Jack Peter Kelly, Tyler L. Dangerfield, David W. Taylor, and Kenneth
A. Johnson. “Remdesivir Is a Delayed Translocation Inhibitor of SARS-CoV-2 Replication.”
Molecular Cell. Elsevier, 2021. https://doi.org/10.1016/j.molcel.2021.01.035.
ieee: J. P. K. Bravo, T. L. Dangerfield, D. W. Taylor, and K. A. Johnson, “Remdesivir
is a delayed translocation inhibitor of SARS-CoV-2 replication,” Molecular
Cell, vol. 81, no. 7. Elsevier, p. 1548–1552.e4, 2021.
ista: Bravo JPK, Dangerfield TL, Taylor DW, Johnson KA. 2021. Remdesivir is a delayed
translocation inhibitor of SARS-CoV-2 replication. Molecular Cell. 81(7), 1548–1552.e4.
mla: Bravo, Jack Peter Kelly, et al. “Remdesivir Is a Delayed Translocation Inhibitor
of SARS-CoV-2 Replication.” Molecular Cell, vol. 81, no. 7, Elsevier, 2021,
p. 1548–1552.e4, doi:10.1016/j.molcel.2021.01.035.
short: J.P.K. Bravo, T.L. Dangerfield, D.W. Taylor, K.A. Johnson, Molecular Cell
81 (2021) 1548–1552.e4.
date_created: 2024-03-20T10:42:53Z
date_published: 2021-04-01T00:00:00Z
date_updated: 2024-06-04T06:00:56Z
day: '01'
doi: 10.1016/j.molcel.2021.01.035
extern: '1'
external_id:
pmid:
- '33631104'
intvolume: ' 81'
issue: '7'
keyword:
- Cell Biology
- Molecular Biology
language:
- iso: eng
main_file_link:
- open_access: '1'
url: 'https://doi.org/10.1101/2020.12.14.422718 '
month: '04'
oa: 1
oa_version: Preprint
page: 1548-1552.e4
pmid: 1
publication: Molecular Cell
publication_identifier:
issn:
- 1097-2765
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Remdesivir is a delayed translocation inhibitor of SARS-CoV-2 replication
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 81
year: '2021'
...
---
_id: '15219'
abstract:
- lang: eng
text: We have carried out a search for massive white dwarfs (WDs) in the direction
of young open star clusters using the Gaia DR2 database. The aim of this survey
was (1) to provide robust data for new and previously known high-mass WDs regarding
cluster membership, (2) to highlight WDs previously included in the initial final
mass relation (IFMR) that are unlikely members of their respective clusters according
to Gaia astrometry, and (3) to select an unequivocal WD sample that could then
be compared with the host clusters' turnoff masses. All promising WD candidates
in each cluster color–magnitude diagram were followed up with spectroscopy from
Gemini in order to determine whether they were indeed WDs and derive their masses,
temperatures, and ages. In order to be considered cluster members, white dwarfs
were required to (1) have proper motions and parallaxes within 2σ, 3σ, or 4σ of
those of their potential parent cluster based on how contaminated the field was
in their region of the sky, (2) have a cooling age that was less than the cluster
age, and (3) have a mass that was broadly consistent with the IFMR. A number of
WDs included in current versions of the IFMR turned out to be nonmembers, and
a number of apparent members, based on Gaia's astrometric data alone, were rejected,
as their mass and/or cooling times were incompatible with cluster membership.
In this way, we developed a highly selected IFMR sample for high-mass WDs that,
surprisingly, contained no precursor masses significantly in excess of ∼ 6 M⊙.
article_number: '165'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Harvey B.
full_name: Richer, Harvey B.
last_name: Richer
- first_name: Ilaria
full_name: Caiazzo, Ilaria
id: 8ae5b6e7-2a03-11ee-914d-b58ed7a3b47d
last_name: Caiazzo
orcid: 0000-0002-4770-5388
- first_name: Helen
full_name: Du, Helen
last_name: Du
- first_name: Steffani
full_name: Grondin, Steffani
last_name: Grondin
- first_name: James
full_name: Hegarty, James
last_name: Hegarty
- first_name: Jeremy
full_name: Heyl, Jeremy
last_name: Heyl
- first_name: Ronan
full_name: Kerr, Ronan
last_name: Kerr
- first_name: David R.
full_name: Miller, David R.
last_name: Miller
- first_name: Sarah
full_name: Thiele, Sarah
last_name: Thiele
citation:
ama: Richer HB, Caiazzo I, Du H, et al. Massive white dwarfs in young star clusters.
The Astrophysical Journal. 2021;912(2). doi:10.3847/1538-4357/abdeb7
apa: Richer, H. B., Caiazzo, I., Du, H., Grondin, S., Hegarty, J., Heyl, J., … Thiele,
S. (2021). Massive white dwarfs in young star clusters. The Astrophysical Journal.
American Astronomical Society. https://doi.org/10.3847/1538-4357/abdeb7
chicago: Richer, Harvey B., Ilaria Caiazzo, Helen Du, Steffani Grondin, James Hegarty,
Jeremy Heyl, Ronan Kerr, David R. Miller, and Sarah Thiele. “Massive White Dwarfs
in Young Star Clusters.” The Astrophysical Journal. American Astronomical
Society, 2021. https://doi.org/10.3847/1538-4357/abdeb7.
ieee: H. B. Richer et al., “Massive white dwarfs in young star clusters,”
The Astrophysical Journal, vol. 912, no. 2. American Astronomical Society,
2021.
ista: Richer HB, Caiazzo I, Du H, Grondin S, Hegarty J, Heyl J, Kerr R, Miller DR,
Thiele S. 2021. Massive white dwarfs in young star clusters. The Astrophysical
Journal. 912(2), 165.
mla: Richer, Harvey B., et al. “Massive White Dwarfs in Young Star Clusters.” The
Astrophysical Journal, vol. 912, no. 2, 165, American Astronomical Society,
2021, doi:10.3847/1538-4357/abdeb7.
short: H.B. Richer, I. Caiazzo, H. Du, S. Grondin, J. Hegarty, J. Heyl, R. Kerr,
D.R. Miller, S. Thiele, The Astrophysical Journal 912 (2021).
date_created: 2024-03-26T10:33:23Z
date_published: 2021-05-17T00:00:00Z
date_updated: 2024-04-03T14:11:17Z
day: '17'
doi: 10.3847/1538-4357/abdeb7
extern: '1'
external_id:
arxiv:
- '2101.08300'
intvolume: ' 912'
issue: '2'
keyword:
- Space and Planetary Science
- Astronomy and Astrophysics
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2101.08300
month: '05'
oa: 1
oa_version: Preprint
publication: The Astrophysical Journal
publication_identifier:
eissn:
- 1538-4357
issn:
- 0004-637X
publication_status: published
publisher: American Astronomical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Massive white dwarfs in young star clusters
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 912
year: '2021'
...
---
_id: '15264'
abstract:
- lang: eng
text: Signaling by the B cell antigen receptor (BCR) initiates actin remodeling.
The assembly of branched actin networks that are nucleated by the Arp2/3 complex
exert outward force on the plasma membrane, allowing B cells to form membrane
protrusions that can scan the surface of antigen-presenting cells (APCs). The
resulting Arp2/3 complex-dependent actin retrograde flow promotes the centripetal
movement and progressive coalescence of BCR microclusters, which amplifies BCR
signaling. Glia maturation factor γ (GMFγ) is an actin disassembly-protein that
releases Arp2/3 complex-nucleated actin filaments from actin networks. By doing
so, GMFγ could either oppose the actions of the Arp2/3 complex or support Arp2/3
complex-nucleated actin polymerization by contributing to the recycling of actin
monomers and Arp2/3 complexes. We now show that reducing the levels of GMFγ in
human B cell lines via transfection with a specific siRNA impairs the ability
of B cells to spread on antigen-coated surfaces, decreases the velocity of actin
retrograde flow, diminishes the coalescence of BCR microclusters into a central
cluster at the B cell-APC contact site, and decreases APC-induced BCR signaling.
These effects of depleting GMFγ are similar to what occurs when the Arp2/3 complex
is inhibited. This suggests that GMFγ cooperates with the Arp2/3 complex to support
BCR-induced actin remodeling and amplify BCR signaling at the immune synapse.
article_number: '647063'
article_processing_charge: No
article_type: original
author:
- first_name: Nikola
full_name: Deretic, Nikola
last_name: Deretic
- first_name: Madison
full_name: Bolger-Munro, Madison
id: 516F03FA-93A3-11EA-A7C5-D6BE3DDC885E
last_name: Bolger-Munro
orcid: 0000-0002-8176-4824
- first_name: Kate
full_name: Choi, Kate
last_name: Choi
- first_name: Libin
full_name: Abraham, Libin
last_name: Abraham
- first_name: Michael R.
full_name: Gold, Michael R.
last_name: Gold
citation:
ama: Deretic N, Bolger-Munro M, Choi K, Abraham L, Gold MR. The actin-disassembly
protein glia maturation factor γ enhances actin remodeling and B cell antigen
receptor signaling at the immune synapse. Frontiers in Cell and Developmental
Biology. 2021;9. doi:10.3389/fcell.2021.647063
apa: Deretic, N., Bolger-Munro, M., Choi, K., Abraham, L., & Gold, M. R. (2021).
The actin-disassembly protein glia maturation factor γ enhances actin remodeling
and B cell antigen receptor signaling at the immune synapse. Frontiers in Cell
and Developmental Biology. Frontiers Media. https://doi.org/10.3389/fcell.2021.647063
chicago: Deretic, Nikola, Madison Bolger-Munro, Kate Choi, Libin Abraham, and Michael
R. Gold. “The Actin-Disassembly Protein Glia Maturation Factor γ Enhances Actin
Remodeling and B Cell Antigen Receptor Signaling at the Immune Synapse.” Frontiers
in Cell and Developmental Biology. Frontiers Media, 2021. https://doi.org/10.3389/fcell.2021.647063.
ieee: N. Deretic, M. Bolger-Munro, K. Choi, L. Abraham, and M. R. Gold, “The actin-disassembly
protein glia maturation factor γ enhances actin remodeling and B cell antigen
receptor signaling at the immune synapse,” Frontiers in Cell and Developmental
Biology, vol. 9. Frontiers Media, 2021.
ista: Deretic N, Bolger-Munro M, Choi K, Abraham L, Gold MR. 2021. The actin-disassembly
protein glia maturation factor γ enhances actin remodeling and B cell antigen
receptor signaling at the immune synapse. Frontiers in Cell and Developmental
Biology. 9, 647063.
mla: Deretic, Nikola, et al. “The Actin-Disassembly Protein Glia Maturation Factor
γ Enhances Actin Remodeling and B Cell Antigen Receptor Signaling at the Immune
Synapse.” Frontiers in Cell and Developmental Biology, vol. 9, 647063,
Frontiers Media, 2021, doi:10.3389/fcell.2021.647063.
short: N. Deretic, M. Bolger-Munro, K. Choi, L. Abraham, M.R. Gold, Frontiers in
Cell and Developmental Biology 9 (2021).
date_created: 2024-04-03T07:34:08Z
date_published: 2021-07-01T00:00:00Z
date_updated: 2024-04-03T14:10:25Z
day: '01'
ddc:
- '570'
department:
- _id: CaHe
doi: 10.3389/fcell.2021.647063
external_id:
pmid:
- '34336818'
file:
- access_level: open_access
checksum: f6330b5c6718d6780383c0300fd4ef12
content_type: application/pdf
creator: dernst
date_created: 2024-04-03T14:08:05Z
date_updated: 2024-04-03T14:08:05Z
file_id: '15291'
file_name: 2021_Frontiers_Deretic.pdf
file_size: 7430029
relation: main_file
success: 1
file_date_updated: 2024-04-03T14:08:05Z
has_accepted_license: '1'
intvolume: ' 9'
keyword:
- Cell Biology
- Developmental Biology
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
pmid: 1
publication: Frontiers in Cell and Developmental Biology
publication_identifier:
issn:
- 2296-634X
publication_status: published
publisher: Frontiers Media
quality_controlled: '1'
scopus_import: '1'
status: public
title: The actin-disassembly protein glia maturation factor γ enhances actin remodeling
and B cell antigen receptor signaling at the immune synapse
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9
year: '2021'
...
---
_id: '15275'
abstract:
- lang: eng
text: In 1916, Schur introduced the Ramsey number r(3; m), which is the minimum
integer n > 1 such that for any m-coloring of the edges of the complete graph
Kn, there is a monochromatic copy of K3. He showed that r(3; m) ≤ O(m!), and a
simple construction demonstrates that r(3; m) ≥ 2Ω(m). An old conjecture of Erdős
states that r(3; m) = 2Θ(m). In this note, we prove the conjecture for m-colorings
with bounded VC-dimension, that is, for m-colorings with the property that the
set system induced by the neighborhoods of the vertices with respect to each color
class has bounded VC-dimension.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
full_name: Fox, Jacob
last_name: Fox
- first_name: János
full_name: Pach, János
id: E62E3130-B088-11EA-B919-BF823C25FEA4
last_name: Pach
- first_name: Andrew
full_name: Suk, Andrew
last_name: Suk
citation:
ama: Fox J, Pach J, Suk A. Bounded VC-dimension implies the Schur-Erdős conjecture.
Combinatorica. 2021;41(6):803-813. doi:10.1007/s00493-021-4530-9
apa: Fox, J., Pach, J., & Suk, A. (2021). Bounded VC-dimension implies the Schur-Erdős
conjecture. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-021-4530-9
chicago: Fox, Jacob, János Pach, and Andrew Suk. “Bounded VC-Dimension Implies the
Schur-Erdős Conjecture.” Combinatorica. Springer Nature, 2021. https://doi.org/10.1007/s00493-021-4530-9.
ieee: J. Fox, J. Pach, and A. Suk, “Bounded VC-dimension implies the Schur-Erdős
conjecture,” Combinatorica, vol. 41, no. 6. Springer Nature, pp. 803–813,
2021.
ista: Fox J, Pach J, Suk A. 2021. Bounded VC-dimension implies the Schur-Erdős conjecture.
Combinatorica. 41(6), 803–813.
mla: Fox, Jacob, et al. “Bounded VC-Dimension Implies the Schur-Erdős Conjecture.”
Combinatorica, vol. 41, no. 6, Springer Nature, 2021, pp. 803–13, doi:10.1007/s00493-021-4530-9.
short: J. Fox, J. Pach, A. Suk, Combinatorica 41 (2021) 803–813.
date_created: 2024-04-03T07:59:57Z
date_published: 2021-11-20T00:00:00Z
date_updated: 2024-04-09T10:40:08Z
day: '20'
department:
- _id: HeEd
doi: 10.1007/s00493-021-4530-9
external_id:
arxiv:
- '1912.02342'
intvolume: ' 41'
issue: '6'
keyword:
- Computational Mathematics
- Discrete Mathematics and Combinatorics
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1912.02342
month: '11'
oa: 1
oa_version: Preprint
page: 803-813
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Bounded VC-dimension implies the Schur-Erdős conjecture
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 41
year: '2021'
...
---
OA_place: repository
OA_type: green
_id: '20619'
abstract:
- lang: eng
text: The first author’s previous work established Solomon’s WDVV-type relations
for Welschinger’s invariant curve counts in real symplectic fourfolds by lifting
geometric relations over possibly unorientable morphisms. We apply her framework
to obtain WDVV-style relations for the disk invariants of real symplectic sixfolds
with some symmetry, in particular confirming Alcolado’s prediction for P^3 and
extending it to other spaces. These relations reduce the computation of Welschinger’s
invariants of many real symplectic sixfolds to invariants in small degrees and
provide lower bounds for counts of real rational curves with positive-dimensional
insertions in some cases. In the case of P^3, our lower bounds fit perfectly with
Kollár’s vanishing results.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Xujia
full_name: Chen, Xujia
id: 968ad14a-fd86-11ee-a420-ea29715511a3
last_name: Chen
- first_name: Aleksey
full_name: Zinger, Aleksey
last_name: Zinger
citation:
ama: Chen X, Zinger A. WDVV-type relations for disk Gromov–Witten invariants in
dimension 6. Mathematische Annalen. 2021;379(3-4):1231-1313. doi:10.1007/s00208-020-02130-1
apa: Chen, X., & Zinger, A. (2021). WDVV-type relations for disk Gromov–Witten
invariants in dimension 6. Mathematische Annalen. Springer Nature. https://doi.org/10.1007/s00208-020-02130-1
chicago: Chen, Xujia, and Aleksey Zinger. “WDVV-Type Relations for Disk Gromov–Witten
Invariants in Dimension 6.” Mathematische Annalen. Springer Nature, 2021.
https://doi.org/10.1007/s00208-020-02130-1.
ieee: X. Chen and A. Zinger, “WDVV-type relations for disk Gromov–Witten invariants
in dimension 6,” Mathematische Annalen, vol. 379, no. 3–4. Springer Nature,
pp. 1231–1313, 2021.
ista: Chen X, Zinger A. 2021. WDVV-type relations for disk Gromov–Witten invariants
in dimension 6. Mathematische Annalen. 379(3–4), 1231–1313.
mla: Chen, Xujia, and Aleksey Zinger. “WDVV-Type Relations for Disk Gromov–Witten
Invariants in Dimension 6.” Mathematische Annalen, vol. 379, no. 3–4, Springer
Nature, 2021, pp. 1231–313, doi:10.1007/s00208-020-02130-1.
short: X. Chen, A. Zinger, Mathematische Annalen 379 (2021) 1231–1313.
date_created: 2025-11-10T08:41:40Z
date_published: 2021-01-25T00:00:00Z
date_updated: 2025-11-10T15:11:29Z
day: '25'
doi: 10.1007/s00208-020-02130-1
extern: '1'
external_id:
arxiv:
- '1904.04254'
intvolume: ' 379'
issue: 3-4
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1904.04254
month: '01'
oa: 1
oa_version: Preprint
page: 1231-1313
publication: Mathematische Annalen
publication_identifier:
eissn:
- 1432-1807
issn:
- 0025-5831
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: WDVV-type relations for disk Gromov–Witten invariants in dimension 6
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 379
year: '2021'
...
---
_id: '10000'
abstract:
- lang: eng
text: Inhibition or targeted deletion of histone deacetylase 3 (HDAC3) is neuroprotective
in a variety neurodegenerative conditions, including retinal ganglion cells (RGCs)
after acute optic nerve damage. Consistent with this, induced HDAC3 expression
in cultured cells shows selective toxicity to neurons. Despite an established
role for HDAC3 in neuronal pathology, little is known regarding the mechanism
of this pathology.
acknowledgement: 'The authors thank Joel Dietz for maintaining the mice used in this
study, Satoshi Kinoshita and the Translational Research Initiative in Pathology
Laboratory at the University of Wisconsin-Madison for cutting retinal sections analyzed
in this study, and Mark Banghart for statistical review of the data analysis. Supported
by National Eye Institute Grants R01 EY012223 (RWN), R01 EY030123 (RWN), R01 EY029809
(LWG), R01 EY029809 (LWG) and a Vision Research CORE grant P30 EY016665, NRSA grant
T32 GM081061, by an unrestricted research grant from Research to Prevent Blindness,
Inc., and by a University of Wisconsin-Madison Vilas Life Cycle award and the Frederick
A. Davis Research Chair (RWN). '
article_number: '14'
article_processing_charge: Yes
article_type: original
author:
- first_name: Heather M.
full_name: Schmitt, Heather M.
last_name: Schmitt
- first_name: Rachel L.
full_name: Fehrman, Rachel L.
last_name: Fehrman
- first_name: Margaret E
full_name: Maes, Margaret E
id: 3838F452-F248-11E8-B48F-1D18A9856A87
last_name: Maes
orcid: 0000-0001-9642-1085
- first_name: Huan
full_name: Yang, Huan
last_name: Yang
- first_name: Lian Wang
full_name: Guo, Lian Wang
last_name: Guo
- first_name: Cassandra L.
full_name: Schlamp, Cassandra L.
last_name: Schlamp
- first_name: Heather R.
full_name: Pelzel, Heather R.
last_name: Pelzel
- first_name: Robert W.
full_name: Nickells, Robert W.
last_name: Nickells
citation:
ama: Schmitt HM, Fehrman RL, Maes ME, et al. Increased susceptibility and intrinsic
apoptotic signaling in neurons by induced HDAC3 expression. Investigative Ophthalmology
and Visual Science. 2021;62(10). doi:10.1167/IOVS.62.10.14
apa: Schmitt, H. M., Fehrman, R. L., Maes, M. E., Yang, H., Guo, L. W., Schlamp,
C. L., … Nickells, R. W. (2021). Increased susceptibility and intrinsic apoptotic
signaling in neurons by induced HDAC3 expression. Investigative Ophthalmology
and Visual Science. Association for Research in Vision and Ophthalmology.
https://doi.org/10.1167/IOVS.62.10.14
chicago: Schmitt, Heather M., Rachel L. Fehrman, Margaret E Maes, Huan Yang, Lian
Wang Guo, Cassandra L. Schlamp, Heather R. Pelzel, and Robert W. Nickells. “Increased
Susceptibility and Intrinsic Apoptotic Signaling in Neurons by Induced HDAC3 Expression.”
Investigative Ophthalmology and Visual Science. Association for Research
in Vision and Ophthalmology, 2021. https://doi.org/10.1167/IOVS.62.10.14.
ieee: H. M. Schmitt et al., “Increased susceptibility and intrinsic apoptotic
signaling in neurons by induced HDAC3 expression,” Investigative Ophthalmology
and Visual Science, vol. 62, no. 10. Association for Research in Vision and
Ophthalmology, 2021.
ista: Schmitt HM, Fehrman RL, Maes ME, Yang H, Guo LW, Schlamp CL, Pelzel HR, Nickells
RW. 2021. Increased susceptibility and intrinsic apoptotic signaling in neurons
by induced HDAC3 expression. Investigative Ophthalmology and Visual Science. 62(10),
14.
mla: Schmitt, Heather M., et al. “Increased Susceptibility and Intrinsic Apoptotic
Signaling in Neurons by Induced HDAC3 Expression.” Investigative Ophthalmology
and Visual Science, vol. 62, no. 10, 14, Association for Research in Vision
and Ophthalmology, 2021, doi:10.1167/IOVS.62.10.14.
short: H.M. Schmitt, R.L. Fehrman, M.E. Maes, H. Yang, L.W. Guo, C.L. Schlamp, H.R.
Pelzel, R.W. Nickells, Investigative Ophthalmology and Visual Science 62 (2021).
date_created: 2021-09-12T22:01:23Z
date_published: 2021-08-16T00:00:00Z
date_updated: 2023-08-14T06:35:17Z
day: '16'
ddc:
- '570'
department:
- _id: SaSi
doi: 10.1167/IOVS.62.10.14
external_id:
isi:
- '000695230000014'
pmid:
- '34398198'
file:
- access_level: open_access
checksum: c430967746f653aa1ae84ee617f62b73
content_type: application/pdf
creator: dernst
date_created: 2022-05-13T07:40:15Z
date_updated: 2022-05-13T07:40:15Z
file_id: '11369'
file_name: 2021_IOVS_Schmitt.pdf
file_size: 19707796
relation: main_file
success: 1
file_date_updated: 2022-05-13T07:40:15Z
has_accepted_license: '1'
intvolume: ' 62'
isi: 1
issue: '10'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
pmid: 1
publication: Investigative Ophthalmology and Visual Science
publication_identifier:
eissn:
- 1552-5783
issn:
- 0146-0404
publication_status: published
publisher: Association for Research in Vision and Ophthalmology
quality_controlled: '1'
scopus_import: '1'
status: public
title: Increased susceptibility and intrinsic apoptotic signaling in neurons by induced
HDAC3 expression
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 62
year: '2021'
...
---
_id: '10002'
abstract:
- lang: eng
text: 'We present a faster symbolic algorithm for the following central problem
in probabilistic verification: Compute the maximal end-component (MEC) decomposition
of Markov decision processes (MDPs). This problem generalizes the SCC decomposition
problem of graphs and closed recurrent sets of Markov chains. The model of symbolic
algorithms is widely used in formal verification and model-checking, where access
to the input model is restricted to only symbolic operations (e.g., basic set
operations and computation of one-step neighborhood). For an input MDP with n vertices
and m edges, the classical symbolic algorithm from the 1990s for the MEC decomposition
requires O(n2) symbolic operations and O(1) symbolic space. The only other
symbolic algorithm for the MEC decomposition requires O(nm−−√) symbolic operations
and O(m−−√) symbolic space. A main open question is whether the worst-case O(n2) bound
for symbolic operations can be beaten. We present a symbolic algorithm that requires O˜(n1.5) symbolic
operations and O˜(n−−√) symbolic space. Moreover, the parametrization of our
algorithm provides a trade-off between symbolic operations and symbolic space:
for all 0<ϵ≤1/2 the symbolic algorithm requires O˜(n2−ϵ) symbolic operations
and O˜(nϵ) symbolic space ( O˜ hides poly-logarithmic factors). Using our techniques
we present faster algorithms for computing the almost-sure winning regions of ω
-regular objectives for MDPs. We consider the canonical parity objectives for ω
-regular objectives, and for parity objectives with d -priorities we present
an algorithm that computes the almost-sure winning region with O˜(n2−ϵ) symbolic
operations and O˜(nϵ) symbolic space, for all 0<ϵ≤1/2 .'
acknowledgement: The authors are grateful to the anonymous referees for their valuable
comments. A. S. is fully supported by the Vienna Science and Technology Fund (WWTF)
through project ICT15–003. K. C. is supported by the Austrian Science Fund (FWF)
NFN Grant No S11407-N23 (RiSE/SHiNE) and by the ERC CoG 863818 (ForM-SMArt). For
M. H. the research leading to these results has received funding from the European
Research Council under the European Unions Seventh Framework Programme (FP/2007–2013)
/ ERC Grant Agreement no. 340506.
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Wolfgang
full_name: Dvorak, Wolfgang
last_name: Dvorak
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Alexander
full_name: Svozil, Alexander
last_name: Svozil
citation:
ama: 'Chatterjee K, Dvorak W, Henzinger M, Svozil A. Symbolic time and space tradeoffs
for probabilistic verification. In: Proceedings of the 36th Annual ACM/IEEE
Symposium on Logic in Computer Science. Institute of Electrical and Electronics
Engineers; 2021:1-13. doi:10.1109/LICS52264.2021.9470739'
apa: 'Chatterjee, K., Dvorak, W., Henzinger, M., & Svozil, A. (2021). Symbolic
time and space tradeoffs for probabilistic verification. In Proceedings of
the 36th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 1–13).
Rome, Italy: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/LICS52264.2021.9470739'
chicago: Chatterjee, Krishnendu, Wolfgang Dvorak, Monika Henzinger, and Alexander
Svozil. “Symbolic Time and Space Tradeoffs for Probabilistic Verification.” In
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science,
1–13. Institute of Electrical and Electronics Engineers, 2021. https://doi.org/10.1109/LICS52264.2021.9470739.
ieee: K. Chatterjee, W. Dvorak, M. Henzinger, and A. Svozil, “Symbolic time and
space tradeoffs for probabilistic verification,” in Proceedings of the 36th
Annual ACM/IEEE Symposium on Logic in Computer Science, Rome, Italy, 2021,
pp. 1–13.
ista: 'Chatterjee K, Dvorak W, Henzinger M, Svozil A. 2021. Symbolic time and space
tradeoffs for probabilistic verification. Proceedings of the 36th Annual ACM/IEEE
Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 1–13.'
mla: Chatterjee, Krishnendu, et al. “Symbolic Time and Space Tradeoffs for Probabilistic
Verification.” Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in
Computer Science, Institute of Electrical and Electronics Engineers, 2021,
pp. 1–13, doi:10.1109/LICS52264.2021.9470739.
short: K. Chatterjee, W. Dvorak, M. Henzinger, A. Svozil, in:, Proceedings of the
36th Annual ACM/IEEE Symposium on Logic in Computer Science, Institute of Electrical
and Electronics Engineers, 2021, pp. 1–13.
conference:
end_date: 2021-07-02
location: Rome, Italy
name: 'LICS: Logic in Computer Science'
start_date: 2021-06-29
date_created: 2021-09-12T22:01:24Z
date_published: 2021-07-07T00:00:00Z
date_updated: 2025-07-10T11:15:45Z
day: '07'
department:
- _id: KrCh
doi: 10.1109/LICS52264.2021.9470739
ec_funded: 1
external_id:
arxiv:
- '2104.07466'
isi:
- '000947350400089'
isi: 1
keyword:
- Computer science
- Computational modeling
- Markov processes
- Probabilistic logic
- Formal verification
- Game Theory
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2104.07466
month: '07'
oa: 1
oa_version: Preprint
page: 1-13
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer
Science
publication_identifier:
eisbn:
- 978-1-6654-4895-6
isbn:
- 978-1-6654-4896-3
issn:
- 1043-6871
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Symbolic time and space tradeoffs for probabilistic verification
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '10004'
abstract:
- lang: eng
text: 'Markov chains are the de facto finite-state model for stochastic dynamical
systems, and Markov decision processes (MDPs) extend Markov chains by incorporating
non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization
criterion is the maximal expected total reward where the MDP stops after T steps,
which can be computed by a simple dynamic programming algorithm. We consider a
natural generalization of the problem where the stopping times can be chosen according
to a probability distribution, such that the expected stopping time is T, to optimize
the expected total reward. Quite surprisingly we establish inter-reducibility
of the expected stopping-time problem for Markov chains with the Positivity problem
(which is related to the well-known Skolem problem), for which establishing either
decidability or undecidability would be a major breakthrough. Given the hardness
of the exact problem, we consider the approximate version of the problem: we show
that it can be solved in exponential time for Markov chains and in exponential
space for MDPs.'
acknowledgement: We are grateful to the anonymous reviewers of LICS 2021 and of a
previous version of this paper for insightful comments that helped improving the
presentation. This research was partially supported by the grant ERC CoG 863818
(ForM-SMArt).
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: 'Chatterjee K, Doyen L. Stochastic processes with expected stopping time. In:
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science.
Institute of Electrical and Electronics Engineers; 2021:1-13. doi:10.1109/LICS52264.2021.9470595'
apa: 'Chatterjee, K., & Doyen, L. (2021). Stochastic processes with expected
stopping time. In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
in Computer Science (pp. 1–13). Rome, Italy: Institute of Electrical and Electronics
Engineers. https://doi.org/10.1109/LICS52264.2021.9470595'
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected
Stopping Time.” In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
in Computer Science, 1–13. Institute of Electrical and Electronics Engineers,
2021. https://doi.org/10.1109/LICS52264.2021.9470595.
ieee: K. Chatterjee and L. Doyen, “Stochastic processes with expected stopping time,”
in Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science,
Rome, Italy, 2021, pp. 1–13.
ista: 'Chatterjee K, Doyen L. 2021. Stochastic processes with expected stopping
time. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science.
LICS: Logic in Computer Science, 1–13.'
mla: Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected
Stopping Time.” Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
in Computer Science, Institute of Electrical and Electronics Engineers, 2021,
pp. 1–13, doi:10.1109/LICS52264.2021.9470595.
short: K. Chatterjee, L. Doyen, in:, Proceedings of the 36th Annual ACM/IEEE Symposium
on Logic in Computer Science, Institute of Electrical and Electronics Engineers,
2021, pp. 1–13.
conference:
end_date: 2021-07-02
location: Rome, Italy
name: 'LICS: Logic in Computer Science'
start_date: 2021-06-29
date_created: 2021-09-12T22:01:25Z
date_published: 2021-07-07T00:00:00Z
date_updated: 2025-09-08T14:54:13Z
day: '07'
department:
- _id: KrCh
doi: 10.1109/LICS52264.2021.9470595
ec_funded: 1
external_id:
arxiv:
- '2104.07278'
isi:
- '000947350400036'
isi: 1
keyword:
- Computer science
- Heuristic algorithms
- Memory management
- Automata
- Markov processes
- Probability distribution
- Complexity theory
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2104.07278
month: '07'
oa: 1
oa_version: Preprint
page: 1-13
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer
Science
publication_identifier:
eisbn:
- 978-1-6654-4895-6
isbn:
- 978-1-6654-4896-3
issn:
- 1043-6871
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
related_material:
record:
- id: '18630'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Stochastic processes with expected stopping time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
OA_place: publisher
_id: '10007'
abstract:
- lang: eng
text: The present thesis is concerned with the derivation of weak-strong uniqueness
principles for curvature driven interface evolution problems not satisfying a
comparison principle. The specific examples being treated are two-phase Navier-Stokes
flow with surface tension, modeling the evolution of two incompressible, viscous
and immiscible fluids separated by a sharp interface, and multiphase mean curvature
flow, which serves as an idealized model for the motion of grain boundaries in
an annealing polycrystalline material. Our main results - obtained in joint works
with Julian Fischer, Tim Laux and Theresa M. Simon - state that prior to the formation
of geometric singularities due to topology changes, the weak solution concept
of Abels (Interfaces Free Bound. 9, 2007) to two-phase Navier-Stokes flow with
surface tension and the weak solution concept of Laux and Otto (Calc. Var. Partial
Differential Equations 55, 2016) to multiphase mean curvature flow (for networks
in R^2 or double bubbles in R^3) represents the unique solution to these interface
evolution problems within the class of classical solutions, respectively. To the
best of the author's knowledge, for interface evolution problems not admitting
a geometric comparison principle the derivation of a weak-strong uniqueness principle
represented an open problem, so that the works contained in the present thesis
constitute the first positive results in this direction. The key ingredient of
our approach consists of the introduction of a novel concept of relative entropies
for a class of curvature driven interface evolution problems, for which the associated
energy contains an interfacial contribution being proportional to the surface
area of the evolving (network of) interface(s). The interfacial part of the relative
entropy gives sufficient control on the interface error between a weak and a classical
solution, and its time evolution can be computed, at least in principle, for any
energy dissipating weak solution concept. A resulting stability estimate for the
relative entropy essentially entails the above mentioned weak-strong uniqueness
principles. The present thesis contains a detailed introduction to our relative
entropy approach, which in particular highlights potential applications to other
problems in curvature driven interface evolution not treated in this thesis.
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Sebastian
full_name: Hensel, Sebastian
id: 4D23B7DA-F248-11E8-B48F-1D18A9856A87
last_name: Hensel
orcid: 0000-0001-7252-8072
citation:
ama: 'Hensel S. Curvature driven interface evolution: Uniqueness properties of weak
solution concepts. 2021. doi:10.15479/at:ista:10007'
apa: 'Hensel, S. (2021). Curvature driven interface evolution: Uniqueness properties
of weak solution concepts. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:10007'
chicago: 'Hensel, Sebastian. “Curvature Driven Interface Evolution: Uniqueness Properties
of Weak Solution Concepts.” Institute of Science and Technology Austria, 2021.
https://doi.org/10.15479/at:ista:10007.'
ieee: 'S. Hensel, “Curvature driven interface evolution: Uniqueness properties of
weak solution concepts,” Institute of Science and Technology Austria, 2021.'
ista: 'Hensel S. 2021. Curvature driven interface evolution: Uniqueness properties
of weak solution concepts. Institute of Science and Technology Austria.'
mla: 'Hensel, Sebastian. Curvature Driven Interface Evolution: Uniqueness Properties
of Weak Solution Concepts. Institute of Science and Technology Austria, 2021,
doi:10.15479/at:ista:10007.'
short: 'S. Hensel, Curvature Driven Interface Evolution: Uniqueness Properties of
Weak Solution Concepts, Institute of Science and Technology Austria, 2021.'
corr_author: '1'
date_created: 2021-09-13T11:12:34Z
date_published: 2021-09-14T00:00:00Z
date_updated: 2026-04-08T07:01:01Z
day: '14'
ddc:
- '515'
degree_awarded: PhD
department:
- _id: GradSch
- _id: JuFi
doi: 10.15479/at:ista:10007
ec_funded: 1
file:
- access_level: closed
checksum: c8475faaf0b680b4971f638f1db16347
content_type: application/x-zip-compressed
creator: shensel
date_created: 2021-09-13T11:03:24Z
date_updated: 2021-09-15T14:37:30Z
file_id: '10008'
file_name: thesis_final_Hensel.zip
file_size: 15022154
relation: source_file
- access_level: open_access
checksum: 1a609937aa5275452822f45f2da17f07
content_type: application/pdf
creator: shensel
date_created: 2021-09-13T14:18:56Z
date_updated: 2021-09-14T09:52:47Z
file_id: '10014'
file_name: thesis_final_Hensel.pdf
file_size: 6583638
relation: main_file
file_date_updated: 2021-09-15T14:37:30Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '300'
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 0aa76401-070f-11eb-9043-b5bb049fa26d
call_identifier: H2020
grant_number: '948819'
name: Bridging Scales in Random Materials
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '10012'
relation: part_of_dissertation
status: public
- id: '10013'
relation: part_of_dissertation
status: public
- id: '7489'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Julian L
full_name: Fischer, Julian L
id: 2C12A0B0-F248-11E8-B48F-1D18A9856A87
last_name: Fischer
orcid: 0000-0002-0479-558X
title: 'Curvature driven interface evolution: Uniqueness properties of weak solution
concepts'
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2021'
...
---
OA_place: publisher
_id: '10030'
abstract:
- lang: eng
text: "This PhD thesis is primarily focused on the study of discrete transport problems,
introduced for the first time in the seminal works of Maas [Maa11] and Mielke
[Mie11] on finite state Markov chains and reaction-diffusion equations, respectively.
More in detail, my research focuses on the study of transport costs on graphs,
in particular the convergence and the stability of such problems in the discrete-to-continuum
limit. This thesis also includes some results concerning\r\nnon-commutative optimal
transport. The first chapter of this thesis consists of a general introduction
to the optimal transport problems, both in the discrete, the continuous, and the
non-commutative setting. Chapters 2 and 3 present the content of two works, obtained
in collaboration with Peter Gladbach, Eva Kopfer, and Jan Maas, where we have
been able to show the convergence of discrete transport costs on periodic graphs
to suitable continuous ones, which can be described by means of a homogenisation
result. We first focus on the particular case of quadratic costs on the real line
and then extending the result to more general costs in arbitrary dimension. Our
results are the first complete characterisation of limits of transport costs on
periodic graphs in arbitrary dimension which do not rely on any additional symmetry.
In Chapter 4 we turn our attention to one of the intriguing connection between
evolution equations and optimal transport, represented by the theory of gradient
flows. We show that discrete gradient flow structures associated to a finite volume
approximation of a certain class of diffusive equations (Fokker–Planck) is stable
in the limit of vanishing meshes, reproving the convergence of the scheme via
the method of evolutionary Γ-convergence and exploiting a more variational point
of view on the problem. This is based on a collaboration with Dominik Forkert
and Jan Maas. Chapter 5 represents a change of perspective, moving away from the
discrete world and reaching the non-commutative one. As in the discrete case,
we discuss how classical tools coming from the commutative optimal transport can
be translated into the setting of density matrices. In particular, in this final
chapter we present a non-commutative version of the Schrödinger problem (or entropic
regularised optimal transport problem) and discuss existence and characterisation
of minimisers, a duality result, and present a non-commutative version of the
well-known Sinkhorn algorithm to compute the above mentioned optimisers. This
is based on a joint work with Dario Feliciangeli and Augusto Gerolin. Finally,
Appendix A and B contain some additional material and discussions, with particular
attention to Harnack inequalities and the regularity of flows on discrete spaces."
acknowledged_ssus:
- _id: M-Shop
- _id: NanoFab
acknowledgement: The author gratefully acknowledges support by the Austrian Science
Fund (FWF), grants No W1245.
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Lorenzo
full_name: Portinale, Lorenzo
id: 30AD2CBC-F248-11E8-B48F-1D18A9856A87
last_name: Portinale
citation:
ama: Portinale L. Discrete-to-continuum limits of transport problems and gradient
flows in the space of measures. 2021. doi:10.15479/at:ista:10030
apa: Portinale, L. (2021). Discrete-to-continuum limits of transport problems
and gradient flows in the space of measures. Institute of Science and Technology
Austria. https://doi.org/10.15479/at:ista:10030
chicago: Portinale, Lorenzo. “Discrete-to-Continuum Limits of Transport Problems
and Gradient Flows in the Space of Measures.” Institute of Science and Technology
Austria, 2021. https://doi.org/10.15479/at:ista:10030.
ieee: L. Portinale, “Discrete-to-continuum limits of transport problems and gradient
flows in the space of measures,” Institute of Science and Technology Austria,
2021.
ista: Portinale L. 2021. Discrete-to-continuum limits of transport problems and
gradient flows in the space of measures. Institute of Science and Technology Austria.
mla: Portinale, Lorenzo. Discrete-to-Continuum Limits of Transport Problems and
Gradient Flows in the Space of Measures. Institute of Science and Technology
Austria, 2021, doi:10.15479/at:ista:10030.
short: L. Portinale, Discrete-to-Continuum Limits of Transport Problems and Gradient
Flows in the Space of Measures, Institute of Science and Technology Austria, 2021.
corr_author: '1'
date_created: 2021-09-21T09:14:15Z
date_published: 2021-09-22T00:00:00Z
date_updated: 2026-04-08T07:00:04Z
day: '22'
ddc:
- '515'
degree_awarded: PhD
department:
- _id: GradSch
- _id: JaMa
doi: 10.15479/at:ista:10030
file:
- access_level: closed
checksum: 8cd60dcb8762e8f21867e21e8001e183
content_type: application/x-zip-compressed
creator: cchlebak
date_created: 2021-09-21T09:17:34Z
date_updated: 2022-03-10T12:14:42Z
file_id: '10032'
file_name: tex_and_pictures.zip
file_size: 3876668
relation: source_file
- access_level: open_access
checksum: 9789e9d967c853c1503ec7f307170279
content_type: application/pdf
creator: cchlebak
date_created: 2021-09-27T11:14:31Z
date_updated: 2021-09-27T11:14:31Z
file_id: '10047'
file_name: thesis_portinale_Final (1).pdf
file_size: 2532673
relation: main_file
file_date_updated: 2022-03-10T12:14:42Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 260788DE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: W1245
name: Dissipation and dispersion in nonlinear partial differential equations
- _id: fc31cba2-9c52-11eb-aca3-ff467d239cd2
grant_number: F6504
name: Taming Complexity in Partial Differential Systems
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '9792'
relation: part_of_dissertation
status: public
- id: '10022'
relation: part_of_dissertation
status: public
- id: '7573'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Jan
full_name: Maas, Jan
id: 4C5696CE-F248-11E8-B48F-1D18A9856A87
last_name: Maas
orcid: 0000-0002-0845-1338
title: Discrete-to-continuum limits of transport problems and gradient flows in the
space of measures
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2021'
...
---
_id: '10033'
abstract:
- lang: eng
text: The ⊗*-monoidal structure on the category of sheaves on the Ran space is not
pro-nilpotent in the sense of [3]. However, under some connectivity assumptions,
we prove that Koszul duality induces an equivalence of categories and that this
equivalence behaves nicely with respect to Verdier duality on the Ran space and
integrating along the Ran space, i.e. taking factorization homology. Based on
ideas sketched in [4], we show that these results also offer a simpler alternative
to one of the two main steps in the proof of the Atiyah-Bott formula given in
[7] and [5].
acknowledgement: 'The author would like to express his gratitude to D. Gaitsgory,
without whose tireless guidance and encouragement in pursuing this problem, this
work would not have been possible. The author is grateful to his advisor B.C. Ngô
for many years of patient guidance and support. This paper is revised while the
author is a postdoc in Hausel group at IST Austria. We thank him and the group for
providing a wonderful research environment. The author also gratefully acknowledges
the support of the Lise Meitner fellowship “Algebro-Geometric Applications of Factorization
Homology,” Austrian Science Fund (FWF): M 2751.'
article_number: '107992'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Quoc P
full_name: Ho, Quoc P
id: 3DD82E3C-F248-11E8-B48F-1D18A9856A87
last_name: Ho
orcid: 0000-0001-6889-1418
citation:
ama: Ho QP. The Atiyah-Bott formula and connectivity in chiral Koszul duality. Advances
in Mathematics. 2021;392. doi:10.1016/j.aim.2021.107992
apa: Ho, Q. P. (2021). The Atiyah-Bott formula and connectivity in chiral Koszul
duality. Advances in Mathematics. Elsevier. https://doi.org/10.1016/j.aim.2021.107992
chicago: Ho, Quoc P. “The Atiyah-Bott Formula and Connectivity in Chiral Koszul
Duality.” Advances in Mathematics. Elsevier, 2021. https://doi.org/10.1016/j.aim.2021.107992.
ieee: Q. P. Ho, “The Atiyah-Bott formula and connectivity in chiral Koszul duality,”
Advances in Mathematics, vol. 392. Elsevier, 2021.
ista: Ho QP. 2021. The Atiyah-Bott formula and connectivity in chiral Koszul duality.
Advances in Mathematics. 392, 107992.
mla: Ho, Quoc P. “The Atiyah-Bott Formula and Connectivity in Chiral Koszul Duality.”
Advances in Mathematics, vol. 392, 107992, Elsevier, 2021, doi:10.1016/j.aim.2021.107992.
short: Q.P. Ho, Advances in Mathematics 392 (2021).
corr_author: '1'
date_created: 2021-09-21T15:58:59Z
date_published: 2021-09-21T00:00:00Z
date_updated: 2025-04-14T09:09:35Z
day: '21'
ddc:
- '514'
department:
- _id: TaHa
doi: 10.1016/j.aim.2021.107992
external_id:
arxiv:
- '1610.00212'
isi:
- '000707040300031'
file:
- access_level: open_access
checksum: f3c0086d41af11db31c00014efb38072
content_type: application/pdf
creator: qho
date_created: 2021-09-21T15:58:52Z
date_updated: 2021-09-21T15:58:52Z
file_id: '10034'
file_name: 1-s2.0-S000187082100431X-main.pdf
file_size: 840635
relation: main_file
file_date_updated: 2021-09-21T15:58:52Z
has_accepted_license: '1'
intvolume: ' 392'
isi: 1
keyword:
- Chiral algebras
- Chiral homology
- Factorization algebras
- Koszul duality
- Ran space
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 26B96266-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02751
name: Algebro-Geometric Applications of Factorization Homology
publication: Advances in Mathematics
publication_identifier:
eissn:
- 1090-2082
issn:
- 0001-8708
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Atiyah-Bott formula and connectivity in chiral Koszul duality
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 392
year: '2021'
...
---
_id: '10041'
abstract:
- lang: eng
text: Yao’s garbling scheme is one of the most fundamental cryptographic constructions.
Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security
in the selective setting where the adversary chooses the challenge inputs before
seeing the garbled circuit assuming secure symmetric-key encryption (and hence
one-way functions). This was followed by results, both positive and negative,
concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto
2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility
argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s
scheme (where the output mapping is sent in the online phase, together with the
garbled input) that circumvents this negative result, and proved that it is adaptively
secure, at least for shallow circuits. In particular, they showed that for the
class of circuits of depth δ , the loss in security is at most exponential in δ
. The above results all concern the simulation-based notion of security. In this
work, we show that the upper bound of Jafargholi and Wichs is basically optimal
in a strong sense. As our main result, we show that there exists a family of Boolean
circuits, one for each depth δ∈N , such that any black-box reduction proving
the adaptive indistinguishability of the natural adaptation of Yao’s scheme from
any symmetric-key encryption has to lose a factor that is exponential in δ√
. Since indistinguishability is a weaker notion than simulation, our bound also
applies to adaptive simulation. To establish our results, we build on the recent
approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction
with oracle separations to prove fine-grained lower bounds on loss in cryptographic
security.
acknowledgement: We would like to thank the anonymous reviewers of Crypto’21 whose
detailed comments helped us considerably improve the presentation of the paper.
alternative_title:
- LCNS
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. Limits on the Adaptive Security
of Yao’s Garbling. In: 41st Annual International Cryptology Conference, Part
II . Vol 12826. Cham: Springer Nature; 2021:486-515. doi:10.1007/978-3-030-84245-1_17'
apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Wichs, D. (2021). Limits
on the Adaptive Security of Yao’s Garbling. In 41st Annual International Cryptology
Conference, Part II (Vol. 12826, pp. 486–515). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-84245-1_17'
chicago: 'Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Daniel
Wichs. “Limits on the Adaptive Security of Yao’s Garbling.” In 41st Annual
International Cryptology Conference, Part II , 12826:486–515. Cham: Springer
Nature, 2021. https://doi.org/10.1007/978-3-030-84245-1_17.'
ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and D. Wichs, “Limits on the
Adaptive Security of Yao’s Garbling,” in 41st Annual International Cryptology
Conference, Part II , Virtual, 2021, vol. 12826, pp. 486–515.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. 2021. Limits on the Adaptive
Security of Yao’s Garbling. 41st Annual International Cryptology Conference, Part
II . CRYPTO: Annual International Cryptology Conference, LCNS, vol. 12826, 486–515.'
mla: Kamath Hosdurg, Chethan, et al. “Limits on the Adaptive Security of Yao’s Garbling.”
41st Annual International Cryptology Conference, Part II , vol. 12826,
Springer Nature, 2021, pp. 486–515, doi:10.1007/978-3-030-84245-1_17.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, D. Wichs, in:, 41st Annual International
Cryptology Conference, Part II , Springer Nature, Cham, 2021, pp. 486–515.
conference:
end_date: 2021-08-20
location: Virtual
name: 'CRYPTO: Annual International Cryptology Conference'
start_date: 2021-08-16
date_created: 2021-09-23T14:06:15Z
date_published: 2021-08-11T00:00:00Z
date_updated: 2026-04-08T07:01:43Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-030-84245-1_17
ec_funded: 1
external_id:
isi:
- '000696697800017'
intvolume: ' 12826'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/945
month: '08'
oa: 1
oa_version: Preprint
page: 486-515
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: '41st Annual International Cryptology Conference, Part II '
publication_identifier:
eisbn:
- 978-3-030-84245-1
eissn:
- 1611-3349
isbn:
- 978-3-030-84244-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10035'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Limits on the Adaptive Security of Yao’s Garbling
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 12826
year: '2021'
...
---
_id: '10052'
abstract:
- lang: eng
text: "A deterministic finite automaton (DFA) \U0001D49C is composite if its language
L(\U0001D49C) can be decomposed into an intersection ⋂_{i = 1}^k L(\U0001D49C_i)
of languages of smaller DFAs. Otherwise, \U0001D49C is prime. This notion of primality
was introduced by Kupferman and Mosheiff in 2013, and while they proved that we
can decide whether a DFA is composite, the precise complexity of this problem
is still open, with a doubly-exponential gap between the upper and lower bounds.
In this work, we focus on permutation DFAs, i.e., those for which the transition
monoid is a group. We provide an NP algorithm to decide whether a permutation
DFA is composite, and show that the difficulty of this problem comes from the
number of non-accepting states of the instance: we give a fixed-parameter tractable
algorithm with the number of rejecting states as the parameter. Moreover, we investigate
the class of commutative permutation DFAs. Their structural properties allow us
to decide compositionality in NL, and even in LOGSPACE if the alphabet size is
fixed. Despite this low complexity, we show that complex behaviors still arise
in this class: we provide a family of composite DFAs each requiring polynomially
many factors with respect to its size. We also consider the variant of the problem
that asks whether a DFA is k-factor composite, that is, decomposable into k smaller
DFAs, for some given integer k ∈ ℕ. We show that, for commutative permutation
DFAs, restricting the number of factors makes the decision computationally harder,
and yields a problem with tight bounds: it is NP-complete. Finally, we show that
in general, this problem is in PSPACE, and it is in LOGSPACE for DFAs with a singleton
alphabet."
acknowledgement: "Ismaël Jecker: Marie Skłodowska-Curie Grant Agreement No. 754411.
Nicolas Mazzocchi: BOSCO project PGC2018-102210-B-I00 (MCIU/AEI/FEDER, UE), BLOQUESCM
project S2018/TCS-4339, and MINECO grant RYC-2016-20281.\r\nPetra Wolf : DFG project
FE 560/9-1.\r\n"
alternative_title:
- LIPIcs
article_number: '18'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ismael R
full_name: Jecker, Ismael R
id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
last_name: Jecker
- first_name: Nicolas
full_name: Mazzocchi, Nicolas
last_name: Mazzocchi
- first_name: Petra
full_name: Wolf, Petra
last_name: Wolf
citation:
ama: 'Jecker IR, Mazzocchi N, Wolf P. Decomposing permutation automata. In: 32nd
International Conference on Concurrency Theory. Vol 203. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.CONCUR.2021.18'
apa: 'Jecker, I. R., Mazzocchi, N., & Wolf, P. (2021). Decomposing permutation
automata. In 32nd International Conference on Concurrency Theory (Vol.
203). Paris, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2021.18'
chicago: Jecker, Ismael R, Nicolas Mazzocchi, and Petra Wolf. “Decomposing Permutation
Automata.” In 32nd International Conference on Concurrency Theory, Vol.
203. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.CONCUR.2021.18.
ieee: I. R. Jecker, N. Mazzocchi, and P. Wolf, “Decomposing permutation automata,”
in 32nd International Conference on Concurrency Theory, Paris, France,
2021, vol. 203.
ista: 'Jecker IR, Mazzocchi N, Wolf P. 2021. Decomposing permutation automata. 32nd
International Conference on Concurrency Theory. CONCUR: Conference on Concurrency
Theory, LIPIcs, vol. 203, 18.'
mla: Jecker, Ismael R., et al. “Decomposing Permutation Automata.” 32nd International
Conference on Concurrency Theory, vol. 203, 18, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2021, doi:10.4230/LIPIcs.CONCUR.2021.18.
short: I.R. Jecker, N. Mazzocchi, P. Wolf, in:, 32nd International Conference on
Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
conference:
end_date: 2021-08-27
location: Paris, France
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2021-08-23
date_created: 2021-09-27T14:33:14Z
date_published: 2021-08-13T00:00:00Z
date_updated: 2025-05-14T10:55:28Z
day: '13'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.CONCUR.2021.18
ec_funded: 1
external_id:
arxiv:
- '2107.04683'
file:
- access_level: open_access
checksum: 4722c81be82265cf45e78adf9db91250
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-01T11:10:53Z
date_updated: 2021-10-01T11:10:53Z
file_id: '10064'
file_name: 2021_CONCUR_Jecker.pdf
file_size: 1003552
relation: main_file
success: 1
file_date_updated: 2021-10-01T11:10:53Z
has_accepted_license: '1'
intvolume: ' 203'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 32nd International Conference on Concurrency Theory
publication_identifier:
isbn:
- 978-3-9597-7203-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Decomposing permutation automata
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 203
year: '2021'
...
---
_id: '10054'
abstract:
- lang: eng
text: 'Graphs and games on graphs are fundamental models for the analysis of reactive
systems, in particular, for model-checking and the synthesis of reactive systems.
The class of ω-regular languages provides a robust specification formalism for
the desired properties of reactive systems. In the classical infinitary formulation
of the liveness part of an ω-regular specification, a "good" event must happen
eventually without any bound between the good events. A stronger notion of liveness
is bounded liveness, which requires that good events happen within d transitions.
Given a graph or a game graph with n vertices, m edges, and a bounded liveness
objective, the previous best-known algorithmic bounds are as follows: (i) O(dm)
for graphs, which in the worst-case is O(n³); and (ii) O(n² d²) for games on graphs.
Our main contributions improve these long-standing algorithmic bounds. For graphs
we present: (i) a randomized algorithm with one-sided error with running time
O(n^{2.5} log n) for the bounded liveness objectives; and (ii) a deterministic
linear-time algorithm for the complement of bounded liveness objectives. For games
on graphs, we present an O(n² d) time algorithm for the bounded liveness objectives.'
acknowledgement: 'Krishnendu Chatterjee: Supported by the ERC CoG 863818 (ForM-SMArt).
Monika Henzinger: Supported by the Austrian Science Fund (FWF) and netIDEE SCIENCE
project P 33775-N. Sagar Sudhir Kale: Partially supported by the Vienna Science
and Technology Fund (WWTF) through project ICT15-003. Alexander Svozil: Fully supported
by the Vienna Science and Technology Fund (WWTF) through project ICT15-003.'
alternative_title:
- LIPIcs
article_number: '124'
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Sagar Sudhir
full_name: Kale, Sagar Sudhir
last_name: Kale
- first_name: Alexander
full_name: Svozil, Alexander
last_name: Svozil
citation:
ama: 'Chatterjee K, Henzinger M, Kale SS, Svozil A. Faster algorithms for bounded
liveness in graphs and game graphs. In: 48th International Colloquium on Automata,
Languages, and Programming. Vol 198. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2021. doi:10.4230/LIPIcs.ICALP.2021.124'
apa: 'Chatterjee, K., Henzinger, M., Kale, S. S., & Svozil, A. (2021). Faster
algorithms for bounded liveness in graphs and game graphs. In 48th International
Colloquium on Automata, Languages, and Programming (Vol. 198). Glasgow, Scotland:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2021.124'
chicago: Chatterjee, Krishnendu, Monika Henzinger, Sagar Sudhir Kale, and Alexander
Svozil. “Faster Algorithms for Bounded Liveness in Graphs and Game Graphs.” In
48th International Colloquium on Automata, Languages, and Programming,
Vol. 198. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.124.
ieee: K. Chatterjee, M. Henzinger, S. S. Kale, and A. Svozil, “Faster algorithms
for bounded liveness in graphs and game graphs,” in 48th International Colloquium
on Automata, Languages, and Programming, Glasgow, Scotland, 2021, vol. 198.
ista: 'Chatterjee K, Henzinger M, Kale SS, Svozil A. 2021. Faster algorithms for
bounded liveness in graphs and game graphs. 48th International Colloquium on Automata,
Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs,
vol. 198, 124.'
mla: Chatterjee, Krishnendu, et al. “Faster Algorithms for Bounded Liveness in Graphs
and Game Graphs.” 48th International Colloquium on Automata, Languages, and
Programming, vol. 198, 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2021, doi:10.4230/LIPIcs.ICALP.2021.124.
short: K. Chatterjee, M. Henzinger, S.S. Kale, A. Svozil, in:, 48th International
Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2021.
conference:
end_date: 2021-07-16
location: Glasgow, Scotland
name: 'ICALP: Automata, Languages and Programming'
start_date: 2021-07-12
corr_author: '1'
date_created: 2021-09-27T14:33:15Z
date_published: 2021-07-02T00:00:00Z
date_updated: 2025-05-14T10:55:19Z
day: '02'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.ICALP.2021.124
ec_funded: 1
file:
- access_level: open_access
checksum: 5a3fed8dbba8c088cbeac1e24cc10bc5
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-01T08:49:26Z
date_updated: 2021-10-01T08:49:26Z
file_id: '10062'
file_name: 2021_LIPIcs_Chatterjee.pdf
file_size: 854576
relation: main_file
success: 1
file_date_updated: 2021-10-01T08:49:26Z
has_accepted_license: '1'
intvolume: ' 198'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 48th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- 978-3-95977-195-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster algorithms for bounded liveness in graphs and game graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 198
year: '2021'
...
---
_id: '10055'
abstract:
- lang: eng
text: "Repeated idempotent elements are commonly used to characterise iterable behaviours
in abstract models of computation. Therefore, given a monoid M, it is natural
to ask how long a sequence of elements of M needs to be to ensure the presence
of consecutive idempotent factors. This question is formalised through the notion
of the Ramsey function R_M associated to M, obtained by mapping every k ∈ ℕ to
the minimal integer R_M(k) such that every word u ∈ M^* of length R_M(k) contains
k consecutive non-empty factors that correspond to the same idempotent element
of M. In this work, we study the behaviour of the Ramsey function R_M by investigating
the regular \U0001D49F-length of M, defined as the largest size L(M) of a submonoid
of M isomorphic to the set of natural numbers {1,2, …, L(M)} equipped with the
max operation. We show that the regular \U0001D49F-length of M determines the
degree of R_M, by proving that k^L(M) ≤ R_M(k) ≤ (k|M|⁴)^L(M). To allow applications
of this result, we provide the value of the regular \U0001D49F-length of diverse
monoids. In particular, we prove that the full monoid of n × n Boolean matrices,
which is used to express transition monoids of non-deterministic automata, has
a regular \U0001D49F-length of (n²+n+2)/2."
acknowledgement: This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No. 754411. I wish to thank Michaël Cadilhac, Emmanuel Filiot and Charles Paperman
for their valuable insights concerning Green’s relations.
alternative_title:
- LIPIcs
article_number: '44'
article_processing_charge: No
author:
- first_name: Ismael R
full_name: Jecker, Ismael R
id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
last_name: Jecker
citation:
ama: 'Jecker IR. A Ramsey theorem for finite monoids. In: 38th International
Symposium on Theoretical Aspects of Computer Science. Vol 187. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.STACS.2021.44'
apa: 'Jecker, I. R. (2021). A Ramsey theorem for finite monoids. In 38th International
Symposium on Theoretical Aspects of Computer Science (Vol. 187). Saarbrücken,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2021.44'
chicago: Jecker, Ismael R. “A Ramsey Theorem for Finite Monoids.” In 38th International
Symposium on Theoretical Aspects of Computer Science, Vol. 187. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.STACS.2021.44.
ieee: I. R. Jecker, “A Ramsey theorem for finite monoids,” in 38th International
Symposium on Theoretical Aspects of Computer Science, Saarbrücken, Germany,
2021, vol. 187.
ista: 'Jecker IR. 2021. A Ramsey theorem for finite monoids. 38th International
Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical
Aspects of Computer Science, LIPIcs, vol. 187, 44.'
mla: Jecker, Ismael R. “A Ramsey Theorem for Finite Monoids.” 38th International
Symposium on Theoretical Aspects of Computer Science, vol. 187, 44, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.STACS.2021.44.
short: I.R. Jecker, in:, 38th International Symposium on Theoretical Aspects of
Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
conference:
end_date: 2021-03-19
location: Saarbrücken, Germany
name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
start_date: 2021-03-16
date_created: 2021-09-27T14:33:15Z
date_published: 2021-03-10T00:00:00Z
date_updated: 2025-05-14T10:55:11Z
day: '10'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.STACS.2021.44
ec_funded: 1
external_id:
isi:
- '000635691700044'
file:
- access_level: open_access
checksum: 17432a05733f408de300e17e390a90e4
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-01T09:55:00Z
date_updated: 2021-10-01T09:55:00Z
file_id: '10063'
file_name: 2021_LIPIcs_Jecker.pdf
file_size: 720250
relation: main_file
success: 1
file_date_updated: 2021-10-01T09:55:00Z
has_accepted_license: '1'
intvolume: ' 187'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 38th International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
isbn:
- 978-3-9597-7180-1
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: A Ramsey theorem for finite monoids
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 187
year: '2021'
...
---
_id: '10069'
abstract:
- lang: eng
text: 'The extent to which women differ in the course of blood cell counts throughout
pregnancy, and the importance of these changes to pregnancy outcomes has not been
well defined. Here, we develop a series of statistical analyses of repeated measures
data to reveal the degree to which women differ in the course of pregnancy, predict
the changes that occur, and determine the importance of these changes for post-partum
hemorrhage (PPH) which is one of the leading causes of maternal mortality. We
present a prospective cohort of 4082 births recorded at the University Hospital,
Lausanne, Switzerland between 2009 and 2014 where full labour records could be
obtained, along with complete blood count data taken at hospital admission. We
find significant differences, at a [Formula: see text] level, among women in how
blood count values change through pregnancy for mean corpuscular hemoglobin, mean
corpuscular volume, mean platelet volume, platelet count and red cell distribution
width. We find evidence that almost all complete blood count values show trimester-specific
associations with PPH. For example, high platelet count (OR 1.20, 95% CI 1.01-1.53),
high mean platelet volume (OR 1.58, 95% CI 1.04-2.08), and high erythrocyte levels
(OR 1.36, 95% CI 1.01-1.57) in trimester 1 increased PPH, but high values in trimester
3 decreased PPH risk (OR 0.85, 0.79, 0.67 respectively). We show that differences
among women in the course of blood cell counts throughout pregnancy have an important
role in shaping pregnancy outcome and tracking blood count value changes through
pregnancy improves identification of women at increased risk of postpartum hemorrhage.
This study provides greater understanding of the complex changes in blood count
values that occur through pregnancy and provides indicators to guide the stratification
of patients into risk groups.'
acknowledgement: This project was funded by an SNSF Eccellenza Grant to MRR (PCEGP3-181181),
and by core funding from the Institute of Science and Technology Austria. We would
like to thank the participants of the study and all the midwives and doctors for
the computerized obstetrical data.
article_number: '19238'
article_processing_charge: Yes
article_type: original
author:
- first_name: Matthew Richard
full_name: Robinson, Matthew Richard
id: E5D42276-F5DA-11E9-8E24-6303E6697425
last_name: Robinson
orcid: 0000-0001-8982-8813
- first_name: Marion
full_name: Patxot, Marion
last_name: Patxot
- first_name: Miloš
full_name: Stojanov, Miloš
last_name: Stojanov
- first_name: Sabine
full_name: Blum, Sabine
last_name: Blum
- first_name: David
full_name: Baud, David
last_name: Baud
citation:
ama: Robinson MR, Patxot M, Stojanov M, Blum S, Baud D. Postpartum hemorrhage risk
is driven by changes in blood composition through pregnancy. Scientific Reports.
2021;11. doi:10.1038/s41598-021-98411-z
apa: Robinson, M. R., Patxot, M., Stojanov, M., Blum, S., & Baud, D. (2021).
Postpartum hemorrhage risk is driven by changes in blood composition through pregnancy.
Scientific Reports. Springer Nature. https://doi.org/10.1038/s41598-021-98411-z
chicago: Robinson, Matthew Richard, Marion Patxot, Miloš Stojanov, Sabine Blum,
and David Baud. “Postpartum Hemorrhage Risk Is Driven by Changes in Blood Composition
through Pregnancy.” Scientific Reports. Springer Nature, 2021. https://doi.org/10.1038/s41598-021-98411-z.
ieee: M. R. Robinson, M. Patxot, M. Stojanov, S. Blum, and D. Baud, “Postpartum
hemorrhage risk is driven by changes in blood composition through pregnancy,”
Scientific Reports, vol. 11. Springer Nature, 2021.
ista: Robinson MR, Patxot M, Stojanov M, Blum S, Baud D. 2021. Postpartum hemorrhage
risk is driven by changes in blood composition through pregnancy. Scientific Reports.
11, 19238.
mla: Robinson, Matthew Richard, et al. “Postpartum Hemorrhage Risk Is Driven by
Changes in Blood Composition through Pregnancy.” Scientific Reports, vol.
11, 19238, Springer Nature, 2021, doi:10.1038/s41598-021-98411-z.
short: M.R. Robinson, M. Patxot, M. Stojanov, S. Blum, D. Baud, Scientific Reports
11 (2021).
corr_author: '1'
date_created: 2021-10-03T22:01:21Z
date_published: 2021-09-28T00:00:00Z
date_updated: 2024-10-09T21:00:57Z
day: '28'
ddc:
- '618'
department:
- _id: MaRo
doi: 10.1038/s41598-021-98411-z
external_id:
isi:
- '000701575500083'
pmid:
- '34584125'
file:
- access_level: open_access
checksum: f002ec22f609f58e1263b79e7f79601e
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-05T14:56:48Z
date_updated: 2021-10-05T14:56:48Z
file_id: '10091'
file_name: 2021_ScientificReports_Robinson.pdf
file_size: 6970368
relation: main_file
success: 1
file_date_updated: 2021-10-05T14:56:48Z
has_accepted_license: '1'
intvolume: ' 11'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
pmid: 1
publication: Scientific Reports
publication_identifier:
eissn:
- 2045-2322
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Postpartum hemorrhage risk is driven by changes in blood composition through
pregnancy
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 11
year: '2021'
...
---
_id: '10072'
abstract:
- lang: eng
text: The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics
which can be used to establish the existence of objects that satisfy certain properties.
The breakthrough paper of Moser and Tardos and follow-up works revealed that the
LLL has intimate connections with a class of stochastic local search algorithms
for finding such desirable objects. In particular, it can be seen as a sufficient
condition for this type of algorithms to converge fast. Besides conditions for
existence of and fast convergence to desirable objects, one may naturally ask
further questions regarding properties of these algorithms. For instance, "are
they parallelizable?", "how many solutions can they output?", "what is the expected
"weight" of a solution?", etc. These questions and more have been answered for
a class of LLL-inspired algorithms called commutative. In this paper we introduce
a new, very natural and more general notion of commutativity (essentially matrix
commutativity) which allows us to show a number of new refined properties of LLL-inspired
local search algorithms with significantly simpler proofs.
acknowledgement: "Fotis Iliopoulos: This material is based upon work directly supported
by the IAS Fund for Math and indirectly supported by the National Science Foundation
Grant No. CCF-1900460. Any opinions, findings and conclusions or recommendations
expressed in this material are those of the author(s) and do not necessarily reflect
the views of the National Science Foundation. This work is also supported by the
National Science Foundation Grant No. CCF-1815328.\r\nVladimir Kolmogorov: Supported
by the European Research Council under the European Unions Seventh Framework Programme
(FP7/2007-2013)/ERC grant agreement no 616160."
alternative_title:
- LIPIcs
article_number: '31'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: David G.
full_name: Harris, David G.
last_name: Harris
- 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: 'Harris DG, Iliopoulos F, Kolmogorov V. A new notion of commutativity for the
algorithmic Lovász Local Lemma. In: Approximation, Randomization, and Combinatorial
Optimization. Algorithms and Techniques. Vol 207. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2021. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.31'
apa: 'Harris, D. G., Iliopoulos, F., & Kolmogorov, V. (2021). A new notion of
commutativity for the algorithmic Lovász Local Lemma. In Approximation, Randomization,
and Combinatorial Optimization. Algorithms and Techniques (Vol. 207). Virtual:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31'
chicago: Harris, David G., Fotis Iliopoulos, and Vladimir Kolmogorov. “A New Notion
of Commutativity for the Algorithmic Lovász Local Lemma.” In Approximation,
Randomization, and Combinatorial Optimization. Algorithms and Techniques,
Vol. 207. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31.
ieee: D. G. Harris, F. Iliopoulos, and V. Kolmogorov, “A new notion of commutativity
for the algorithmic Lovász Local Lemma,” in Approximation, Randomization, and
Combinatorial Optimization. Algorithms and Techniques, Virtual, 2021, vol.
207.
ista: 'Harris DG, Iliopoulos F, Kolmogorov V. 2021. A new notion of commutativity
for the algorithmic Lovász Local Lemma. Approximation, Randomization, and Combinatorial
Optimization. Algorithms and Techniques. APPROX/RANDOM: Approximation Algorithms
for Combinatorial Optimization Problems/ Randomization and Computation, LIPIcs,
vol. 207, 31.'
mla: Harris, David G., et al. “A New Notion of Commutativity for the Algorithmic
Lovász Local Lemma.” Approximation, Randomization, and Combinatorial Optimization.
Algorithms and Techniques, vol. 207, 31, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2021, doi:10.4230/LIPIcs.APPROX/RANDOM.2021.31.
short: D.G. Harris, F. Iliopoulos, V. Kolmogorov, in:, Approximation, Randomization,
and Combinatorial Optimization. Algorithms and Techniques, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2021.
conference:
end_date: 2021-08-18
location: Virtual
name: 'APPROX/RANDOM: Approximation Algorithms for Combinatorial Optimization Problems/
Randomization and Computation'
start_date: 2021-08-16
date_created: 2021-10-03T22:01:22Z
date_published: 2021-09-15T00:00:00Z
date_updated: 2026-02-10T09:59:59Z
day: '15'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.4230/LIPIcs.APPROX/RANDOM.2021.31
ec_funded: 1
external_id:
arxiv:
- '2008.05569'
file:
- access_level: open_access
checksum: 9d2544d53aa5b01565c6891d97a4d765
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-06T13:51:54Z
date_updated: 2021-10-06T13:51:54Z
file_id: '10098'
file_name: 2021_LIPIcs_Harris.pdf
file_size: 804472
relation: main_file
success: 1
file_date_updated: 2021-10-06T13:51:54Z
has_accepted_license: '1'
intvolume: ' 207'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques
publication_identifier:
isbn:
- 978-3-9597-7207-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '21143'
relation: later_version
status: public
scopus_import: '1'
status: public
title: A new notion of commutativity for the algorithmic Lovász Local Lemma
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 207
year: '2021'
...