---
_id: '10607'
abstract:
- lang: eng
text: The evidence linking innate immunity mechanisms and neurodegenerative diseases
is growing, but the specific mechanisms are incompletely understood. Experimental
data suggest that microglial TLR4 mediates the uptake and clearance of α-synuclein
also termed synucleinophagy. The accumulation of misfolded α-synuclein throughout
the brain is central to Parkinson's disease (PD). The distribution and progression
of the pathology is often attributed to the propagation of α-synuclein. Here,
we apply a classical α-synuclein propagation model of prodromal PD in wild type
and TLR4 deficient mice to study the role of TLR4 in the progression of the disease.
Our data suggest that TLR4 deficiency facilitates the α-synuclein seed spreading
associated with reduced lysosomal activity of microglia. Three months after seed
inoculation, more pronounced proteinase K-resistant α-synuclein inclusion pathology
is observed in mice with TLR4 deficiency. The facilitated propagation of α-synuclein
is associated with early loss of dopamine transporter (DAT) signal in the striatum
and loss of dopaminergic neurons in substantia nigra pars compacta of TLR4 deficient
mice. These new results support TLR4 signaling as a putative target for disease
modification to slow the progression of PD and related disorders.
acknowledgement: This study was supported by grants of the Austrian Science Fund (FWF)
F4414 and W1206-08. Electron microscopy was performed at the Scientific Service
Units (SSU) of IST-Austria through resources provided by the Electron Microscopy
Facility.
article_processing_charge: No
article_type: original
author:
- first_name: Serena
full_name: Venezia, Serena
last_name: Venezia
- first_name: Walter
full_name: Kaufmann, Walter
id: 3F99E422-F248-11E8-B48F-1D18A9856A87
last_name: Kaufmann
orcid: 0000-0001-9735-5315
- first_name: Gregor K.
full_name: Wenning, Gregor K.
last_name: Wenning
- first_name: Nadia
full_name: Stefanova, Nadia
last_name: Stefanova
citation:
ama: Venezia S, Kaufmann W, Wenning GK, Stefanova N. Toll-like receptor 4 deficiency
facilitates α-synuclein propagation and neurodegeneration in a mouse model of
prodromal Parkinson’s disease. Parkinsonism & Related Disorders. 2021;91:59-65.
doi:10.1016/j.parkreldis.2021.09.007
apa: Venezia, S., Kaufmann, W., Wenning, G. K., & Stefanova, N. (2021). Toll-like
receptor 4 deficiency facilitates α-synuclein propagation and neurodegeneration
in a mouse model of prodromal Parkinson’s disease. Parkinsonism & Related
Disorders. Elsevier. https://doi.org/10.1016/j.parkreldis.2021.09.007
chicago: Venezia, Serena, Walter Kaufmann, Gregor K. Wenning, and Nadia Stefanova.
“Toll-like Receptor 4 Deficiency Facilitates α-Synuclein Propagation and Neurodegeneration
in a Mouse Model of Prodromal Parkinson’s Disease.” Parkinsonism & Related
Disorders. Elsevier, 2021. https://doi.org/10.1016/j.parkreldis.2021.09.007.
ieee: S. Venezia, W. Kaufmann, G. K. Wenning, and N. Stefanova, “Toll-like receptor
4 deficiency facilitates α-synuclein propagation and neurodegeneration in a mouse
model of prodromal Parkinson’s disease,” Parkinsonism & Related Disorders,
vol. 91. Elsevier, pp. 59–65, 2021.
ista: Venezia S, Kaufmann W, Wenning GK, Stefanova N. 2021. Toll-like receptor 4
deficiency facilitates α-synuclein propagation and neurodegeneration in a mouse
model of prodromal Parkinson’s disease. Parkinsonism & Related Disorders.
91, 59–65.
mla: Venezia, Serena, et al. “Toll-like Receptor 4 Deficiency Facilitates α-Synuclein
Propagation and Neurodegeneration in a Mouse Model of Prodromal Parkinson’s Disease.”
Parkinsonism & Related Disorders, vol. 91, Elsevier, 2021, pp. 59–65,
doi:10.1016/j.parkreldis.2021.09.007.
short: S. Venezia, W. Kaufmann, G.K. Wenning, N. Stefanova, Parkinsonism & Related
Disorders 91 (2021) 59–65.
date_created: 2022-01-09T23:01:26Z
date_published: 2021-10-01T00:00:00Z
date_updated: 2023-08-17T06:36:01Z
day: '01'
ddc:
- '610'
department:
- _id: EM-Fac
doi: 10.1016/j.parkreldis.2021.09.007
external_id:
isi:
- '000701142900012'
pmid:
- '34530328'
file:
- access_level: open_access
checksum: 360681585acb51e80d17c6b213c56b55
content_type: application/pdf
creator: alisjak
date_created: 2022-01-10T13:41:40Z
date_updated: 2022-01-10T13:41:40Z
file_id: '10612'
file_name: 2021_Parkinsonism_Venezia.pdf
file_size: 6848513
relation: main_file
success: 1
file_date_updated: 2022-01-10T13:41:40Z
has_accepted_license: '1'
intvolume: ' 91'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '10'
oa: 1
oa_version: Published Version
page: 59-65
pmid: 1
publication: Parkinsonism & Related Disorders
publication_identifier:
eissn:
- 1873-5126
issn:
- 1353-8020
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Toll-like receptor 4 deficiency facilitates α-synuclein propagation and neurodegeneration
in a mouse model of prodromal Parkinson's disease
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: 91
year: '2021'
...
---
_id: '10608'
abstract:
- lang: eng
text: We consider infinite-dimensional properties in coarse geometry for hyperspaces
consisting of finite subsets of metric spaces with the Hausdorff metric. We see
that several infinite-dimensional properties are preserved by taking the hyperspace
of subsets with at most n points. On the other hand, we prove that, if a metric
space contains a sequence of long intervals coarsely, then its hyperspace of finite
subsets is not coarsely embeddable into any uniformly convex Banach space. As
a corollary, the hyperspace of finite subsets of the real line is not coarsely
embeddable into any uniformly convex Banach space. It is also shown that every
(not necessarily bounded geometry) metric space with straight finite decomposition
complexity has metric sparsification property.
acknowledgement: We would like to thank the referees for their careful reading and
the comments that improved our work. The third named author would like to thank
the Division of Mathematics, Physics and Earth Sciences of the Graduate School of
Science and Engineering of Ehime University and the second named author for hosting
his visit in June 2018. Open access funding provided by Institute of Science and
Technology (IST Austria).
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Thomas
full_name: Weighill, Thomas
last_name: Weighill
- first_name: Takamitsu
full_name: Yamauchi, Takamitsu
last_name: Yamauchi
- first_name: Nicolò
full_name: Zava, Nicolò
id: c8b3499c-7a77-11eb-b046-aa368cbbf2ad
last_name: Zava
citation:
ama: Weighill T, Yamauchi T, Zava N. Coarse infinite-dimensionality of hyperspaces
of finite subsets. European Journal of Mathematics. 2021. doi:10.1007/s40879-021-00515-3
apa: Weighill, T., Yamauchi, T., & Zava, N. (2021). Coarse infinite-dimensionality
of hyperspaces of finite subsets. European Journal of Mathematics. Springer
Nature. https://doi.org/10.1007/s40879-021-00515-3
chicago: Weighill, Thomas, Takamitsu Yamauchi, and Nicolò Zava. “Coarse Infinite-Dimensionality
of Hyperspaces of Finite Subsets.” European Journal of Mathematics. Springer
Nature, 2021. https://doi.org/10.1007/s40879-021-00515-3.
ieee: T. Weighill, T. Yamauchi, and N. Zava, “Coarse infinite-dimensionality of
hyperspaces of finite subsets,” European Journal of Mathematics. Springer
Nature, 2021.
ista: Weighill T, Yamauchi T, Zava N. 2021. Coarse infinite-dimensionality of hyperspaces
of finite subsets. European Journal of Mathematics.
mla: Weighill, Thomas, et al. “Coarse Infinite-Dimensionality of Hyperspaces of
Finite Subsets.” European Journal of Mathematics, Springer Nature, 2021,
doi:10.1007/s40879-021-00515-3.
short: T. Weighill, T. Yamauchi, N. Zava, European Journal of Mathematics (2021).
date_created: 2022-01-09T23:01:27Z
date_published: 2021-12-30T00:00:00Z
date_updated: 2022-01-10T08:36:55Z
day: '30'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.1007/s40879-021-00515-3
file:
- access_level: open_access
checksum: c435dcfa1ad3aadc5cdd7366bc7f4e98
content_type: application/pdf
creator: cchlebak
date_created: 2022-01-10T08:33:22Z
date_updated: 2022-01-10T08:33:22Z
file_id: '10610'
file_name: 2021_EuJournalMath_Weighill.pdf
file_size: 384908
relation: main_file
success: 1
file_date_updated: 2022-01-10T08:33:22Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: European Journal of Mathematics
publication_identifier:
eissn:
- 2199-6768
issn:
- 2199-675X
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Coarse infinite-dimensionality of hyperspaces of finite subsets
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '10609'
abstract:
- lang: eng
text: "We study Multi-party computation (MPC) in the setting of subversion, where
the adversary tampers with the machines of honest parties. Our goal is to construct
actively secure MPC protocols where parties are corrupted adaptively by an adversary
(as in the standard adaptive security setting), and in addition, honest parties’
machines are compromised.\r\nThe idea of reverse firewalls (RF) was introduced
at EUROCRYPT’15 by Mironov and Stephens-Davidowitz as an approach to protecting
protocols against corruption of honest parties’ devices. Intuitively, an RF for
a party P is an external entity that sits between P and the outside world
and whose scope is to sanitize P ’s incoming and outgoing messages in the face
of subversion of their computer. Mironov and Stephens-Davidowitz constructed a
protocol for passively-secure two-party computation. At CRYPTO’20, Chakraborty,
Dziembowski and Nielsen constructed a protocol for secure computation with firewalls
that improved on this result, both by extending it to multi-party computation
protocol, and considering active security in the presence of static corruptions.
In this paper, we initiate the study of RF for MPC in the adaptive setting. We
put forward a definition for adaptively secure MPC in the reverse firewall setting,
explore relationships among the security notions, and then construct reverse firewalls
for MPC in this stronger setting of adaptive security. We also resolve the open
question of Chakraborty, Dziembowski and Nielsen by removing the need for a trusted
setup in constructing RF for MPC. Towards this end, we construct reverse firewalls
for adaptively secure augmented coin tossing and adaptively secure zero-knowledge
protocols and obtain a constant round adaptively secure MPC protocol in the reverse
firewall setting without setup. Along the way, we propose a new multi-party adaptively
secure coin tossing protocol in the plain model, that is of independent interest."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Chaya
full_name: Ganesh, Chaya
last_name: Ganesh
- first_name: Mahak
full_name: Pancholi, Mahak
last_name: Pancholi
- first_name: Pratik
full_name: Sarkar, Pratik
last_name: Sarkar
citation:
ama: 'Chakraborty S, Ganesh C, Pancholi M, Sarkar P. Reverse firewalls for adaptively
secure MPC without setup. In: 27th International Conference on the Theory and
Application of Cryptology and Information Security. Vol 13091. Springer Nature;
2021:335-364. doi:10.1007/978-3-030-92075-3_12'
apa: 'Chakraborty, S., Ganesh, C., Pancholi, M., & Sarkar, P. (2021). Reverse
firewalls for adaptively secure MPC without setup. In 27th International Conference
on the Theory and Application of Cryptology and Information Security (Vol.
13091, pp. 335–364). Virtual, Singapore: Springer Nature. https://doi.org/10.1007/978-3-030-92075-3_12'
chicago: Chakraborty, Suvradip, Chaya Ganesh, Mahak Pancholi, and Pratik Sarkar.
“Reverse Firewalls for Adaptively Secure MPC without Setup.” In 27th International
Conference on the Theory and Application of Cryptology and Information Security,
13091:335–64. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-92075-3_12.
ieee: S. Chakraborty, C. Ganesh, M. Pancholi, and P. Sarkar, “Reverse firewalls
for adaptively secure MPC without setup,” in 27th International Conference
on the Theory and Application of Cryptology and Information Security, Virtual,
Singapore, 2021, vol. 13091, pp. 335–364.
ista: 'Chakraborty S, Ganesh C, Pancholi M, Sarkar P. 2021. Reverse firewalls for
adaptively secure MPC without setup. 27th International Conference on the Theory
and Application of Cryptology and Information Security. ASIACRYPT: International
Conference on Cryptology in Asia, LNCS, vol. 13091, 335–364.'
mla: Chakraborty, Suvradip, et al. “Reverse Firewalls for Adaptively Secure MPC
without Setup.” 27th International Conference on the Theory and Application
of Cryptology and Information Security, vol. 13091, Springer Nature, 2021,
pp. 335–64, doi:10.1007/978-3-030-92075-3_12.
short: S. Chakraborty, C. Ganesh, M. Pancholi, P. Sarkar, in:, 27th International
Conference on the Theory and Application of Cryptology and Information Security,
Springer Nature, 2021, pp. 335–364.
conference:
end_date: 2021-12-10
location: Virtual, Singapore
name: 'ASIACRYPT: International Conference on Cryptology in Asia'
start_date: 2021-12-06
date_created: 2022-01-09T23:01:27Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2023-08-17T06:34:41Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-030-92075-3_12
ec_funded: 1
external_id:
isi:
- '000927876200012'
intvolume: ' 13091'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1262
month: '12'
oa: 1
oa_version: Preprint
page: 335-364
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 27th International Conference on the Theory and Application of Cryptology
and Information Security
publication_identifier:
eisbn:
- 978-3-030-92075-3
eissn:
- 1611-3349
isbn:
- 978-3-030-92074-6
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reverse firewalls for adaptively secure MPC without setup
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13091
year: '2021'
...
---
_id: '10613'
abstract:
- lang: eng
text: Motivated by the recent preprint [\emph{arXiv:2004.08412}] by Ayala, Carinci,
and Redig, we first provide a general framework for the study of scaling limits
of higher-order fields. Then, by considering the same class of infinite interacting
particle systems as in [\emph{arXiv:2004.08412}], namely symmetric simple exclusion
and inclusion processes in the d-dimensional Euclidean lattice, we prove the hydrodynamic
limit, and convergence for the equilibrium fluctuations, of higher-order fields.
In particular, the limit fields exhibit a tensor structure. Our fluctuation result
differs from that in [\emph{arXiv:2004.08412}], since we considered-dimensional
Euclidean lattice, we prove the hydrodynamic limit, and convergence for the equilibrium
fluctuations, of higher-order fields. In particular, the limit fields exhibit
a tensor structure. Our fluctuation result differs from that in [\emph{arXiv:2004.08412}],
since we consider a different notion of higher-order fluctuation fields.
acknowledgement: "F.S. would like to thank Mario Ayala and Frank Redig for useful
discussions. J.P.C. acknowledges partial financial support from the US National
Science Foundation (DMS-1855604). F.S. was financially supported by the European
Union’s Horizon 2020 research and innovation programme under the Marie-Skłodowska-Curie
grant agreement No. 754411.\r\n"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Joe P.
full_name: Chen, Joe P.
last_name: Chen
- first_name: Federico
full_name: Sau, Federico
id: E1836206-9F16-11E9-8814-AEFDE5697425
last_name: Sau
citation:
ama: Chen JP, Sau F. Higher-order hydrodynamics and equilibrium fluctuations of
interacting particle systems. Markov Processes And Related Fields. 2021;27(3):339-380.
apa: Chen, J. P., & Sau, F. (2021). Higher-order hydrodynamics and equilibrium
fluctuations of interacting particle systems. Markov Processes And Related
Fields. Polymat Publishing.
chicago: Chen, Joe P., and Federico Sau. “Higher-Order Hydrodynamics and Equilibrium
Fluctuations of Interacting Particle Systems.” Markov Processes And Related
Fields. Polymat Publishing, 2021.
ieee: J. P. Chen and F. Sau, “Higher-order hydrodynamics and equilibrium fluctuations
of interacting particle systems,” Markov Processes And Related Fields,
vol. 27, no. 3. Polymat Publishing, pp. 339–380, 2021.
ista: Chen JP, Sau F. 2021. Higher-order hydrodynamics and equilibrium fluctuations
of interacting particle systems. Markov Processes And Related Fields. 27(3), 339–380.
mla: Chen, Joe P., and Federico Sau. “Higher-Order Hydrodynamics and Equilibrium
Fluctuations of Interacting Particle Systems.” Markov Processes And Related
Fields, vol. 27, no. 3, Polymat Publishing, 2021, pp. 339–80.
short: J.P. Chen, F. Sau, Markov Processes And Related Fields 27 (2021) 339–380.
date_created: 2022-01-10T14:02:31Z
date_published: 2021-03-16T00:00:00Z
date_updated: 2022-01-10T15:29:08Z
day: '16'
department:
- _id: JaMa
ec_funded: 1
external_id:
arxiv:
- '2008.13403'
intvolume: ' 27'
issue: '3'
keyword:
- interacting particle systems
- higher-order fields
- hydrodynamic limit
- equilibrium fluctuations
- duality
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2008.13403
month: '03'
oa: 1
oa_version: Preprint
page: 339-380
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Markov Processes And Related Fields
publication_identifier:
issn:
- 1024-2953
publication_status: published
publisher: Polymat Publishing
quality_controlled: '1'
related_material:
link:
- description: Link to Abstract on publisher's website
relation: other
url: http://math-mprf.org/journal/articles/id1614/
- description: Referred to in Abstract
relation: used_for_analysis_in
url: https://arxiv.org/abs/2004.08412
status: public
title: Higher-order hydrodynamics and equilibrium fluctuations of interacting particle
systems
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 27
year: '2021'
...
---
_id: '10616'
abstract:
- lang: eng
text: Electrons in moiré flat band systems can spontaneously break time-reversal
symmetry, giving rise to a quantized anomalous Hall effect. In this study, we
use a superconducting quantum interference device to image stray magnetic fields
in twisted bilayer graphene aligned to hexagonal boron nitride. We find a magnetization
of several Bohr magnetons per charge carrier, demonstrating that the magnetism
is primarily orbital in nature. Our measurements reveal a large change in the
magnetization as the chemical potential is swept across the quantum anomalous
Hall gap, consistent with the expected contribution of chiral edge states to the
magnetization of an orbital Chern insulator. Mapping the spatial evolution of
field-driven magnetic reversal, we find a series of reproducible micrometer-scale
domains pinned to structural disorder.
acknowledgement: 'We thank A. H. Macdonald, J. Zhu, M. Zaletel, and D. Xiao for discussions
of the results and E. Lachman for comments on the manuscript. Funding: The work
was primarily funded by the US Department of Energy under DE-SC0020043, with additional
support for instrumentation development supported by the Army Research Office under
grant W911NF-16-1-0361. K.W. and T.T. acknowledge support from the Elemental Strategy
Initiative conducted by MEXT, Japan, grant JPMXP0112101001; JSPS KAKENHI grant JP20H00354
and CREST grant JPMJCR15F3, JST. C.L.T. acknowledges support from the Hertz Foundation
and from the National Science Foundation Graduate Research Fellowship Program under
grant 1650114. This project is funded in part by the Gordon and Betty Moore Foundation’s
EPiQS Initiative, grant GBMF9471 to A.F.Y.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: C. L.
full_name: Tschirhart, C. L.
last_name: Tschirhart
- first_name: M.
full_name: Serlin, M.
last_name: Serlin
- first_name: Hryhoriy
full_name: Polshyn, Hryhoriy
id: edfc7cb1-526e-11ec-b05a-e6ecc27e4e48
last_name: Polshyn
orcid: 0000-0001-8223-8896
- first_name: A.
full_name: Shragai, A.
last_name: Shragai
- first_name: Z.
full_name: Xia, Z.
last_name: Xia
- first_name: J.
full_name: Zhu, J.
last_name: Zhu
- first_name: Y.
full_name: Zhang, Y.
last_name: Zhang
- first_name: K.
full_name: Watanabe, K.
last_name: Watanabe
- first_name: T.
full_name: Taniguchi, T.
last_name: Taniguchi
- first_name: M. E.
full_name: Huber, M. E.
last_name: Huber
- first_name: A. F.
full_name: Young, A. F.
last_name: Young
citation:
ama: Tschirhart CL, Serlin M, Polshyn H, et al. Imaging orbital ferromagnetism in
a moiré Chern insulator. Science. 2021;372(6548):1323-1327. doi:10.1126/science.abd3190
apa: Tschirhart, C. L., Serlin, M., Polshyn, H., Shragai, A., Xia, Z., Zhu, J.,
… Young, A. F. (2021). Imaging orbital ferromagnetism in a moiré Chern insulator.
Science. American Association for the Advancement of Science. https://doi.org/10.1126/science.abd3190
chicago: Tschirhart, C. L., M. Serlin, Hryhoriy Polshyn, A. Shragai, Z. Xia, J.
Zhu, Y. Zhang, et al. “Imaging Orbital Ferromagnetism in a Moiré Chern Insulator.”
Science. American Association for the Advancement of Science, 2021. https://doi.org/10.1126/science.abd3190.
ieee: C. L. Tschirhart et al., “Imaging orbital ferromagnetism in a moiré
Chern insulator,” Science, vol. 372, no. 6548. American Association for
the Advancement of Science, pp. 1323–1327, 2021.
ista: Tschirhart CL, Serlin M, Polshyn H, Shragai A, Xia Z, Zhu J, Zhang Y, Watanabe
K, Taniguchi T, Huber ME, Young AF. 2021. Imaging orbital ferromagnetism in a
moiré Chern insulator. Science. 372(6548), 1323–1327.
mla: Tschirhart, C. L., et al. “Imaging Orbital Ferromagnetism in a Moiré Chern
Insulator.” Science, vol. 372, no. 6548, American Association for the Advancement
of Science, 2021, pp. 1323–27, doi:10.1126/science.abd3190.
short: C.L. Tschirhart, M. Serlin, H. Polshyn, A. Shragai, Z. Xia, J. Zhu, Y. Zhang,
K. Watanabe, T. Taniguchi, M.E. Huber, A.F. Young, Science 372 (2021) 1323–1327.
date_created: 2022-01-13T12:17:45Z
date_published: 2021-05-27T00:00:00Z
date_updated: 2022-01-13T14:11:36Z
day: '27'
doi: 10.1126/science.abd3190
extern: '1'
external_id:
arxiv:
- '2006.08053'
pmid:
- '34045322'
intvolume: ' 372'
issue: '6548'
keyword:
- multidisciplinary
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2006.08053
month: '05'
oa: 1
oa_version: Preprint
page: 1323-1327
pmid: 1
publication: Science
publication_identifier:
eissn:
- 1095-9203
issn:
- 0036-8075
publication_status: published
publisher: American Association for the Advancement of Science
quality_controlled: '1'
scopus_import: '1'
status: public
title: Imaging orbital ferromagnetism in a moiré Chern insulator
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 372
year: '2021'
...
---
_id: '10617'
abstract:
- lang: eng
text: When a flat band is partially filled with electrons, strong Coulomb interactions
between them may lead to the emergence of topological gapped states with quantized
Hall conductivity. Such emergent topological states have been found in partially
filled Landau levels1 and Hofstadter bands2,3; however, in both cases, a large
magnetic field is required to produce the underlying flat band. The recent observation
of quantum anomalous Hall effects in narrow-band moiré materials4,5,6,7 has led
to the theoretical prediction that such phases could be realized at zero magnetic
field8,9,10,11,12. Here we report the observation of insulators with Chern number
C = 1 in the zero-magnetic-field limit at half-integer filling of the moiré superlattice
unit cell in twisted monolayer–bilayer graphene7,13,14,15. Chern insulators in
a half-filled band suggest the spontaneous doubling of the superlattice unit cell2,3,16,
and our calculations find a ground state of the topological charge density wave
at half-filling of the underlying band. The discovery of these topological phases
at fractional superlattice filling enables the further pursuit of zero-magnetic-field
phases that have fractional statistics that exist either as elementary excitations
or bound to lattice dislocations.
acknowledgement: We are grateful to J. Zhu for fruitful discussions. A.F.Y. acknowledges
support from the Office of Naval Research under award N00014-20-1-2609, and the
Gordon and Betty Moore Foundation under award GBMF9471. M.P.Z. acknowledges support
from the ARO under MURI W911NF-16-1-0361. K.W. and T.T. acknowledge support from
the Elemental Strategy Initiative conducted by the MEXT, Japan, via grant no. JPMXP0112101001;
JSPS KAKENHI grant no. JP20H00354; and the CREST(JPMJCR15F3), JST. A.V. was supported
by a Simons Investigator Award. P.L. was supported by the Department of Defense
(DoD) through the National Defense Science and Engineering Graduate Fellowship (NDSEG)
Program.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Hryhoriy
full_name: Polshyn, Hryhoriy
id: edfc7cb1-526e-11ec-b05a-e6ecc27e4e48
last_name: Polshyn
orcid: 0000-0001-8223-8896
- first_name: Y.
full_name: Zhang, Y.
last_name: Zhang
- first_name: M. A.
full_name: Kumar, M. A.
last_name: Kumar
- first_name: T.
full_name: Soejima, T.
last_name: Soejima
- first_name: P.
full_name: Ledwith, P.
last_name: Ledwith
- first_name: K.
full_name: Watanabe, K.
last_name: Watanabe
- first_name: T.
full_name: Taniguchi, T.
last_name: Taniguchi
- first_name: A.
full_name: Vishwanath, A.
last_name: Vishwanath
- first_name: M. P.
full_name: Zaletel, M. P.
last_name: Zaletel
- first_name: A. F.
full_name: Young, A. F.
last_name: Young
citation:
ama: Polshyn H, Zhang Y, Kumar MA, et al. Topological charge density waves at half-integer
filling of a moiré superlattice. Nature Physics. 2021. doi:10.1038/s41567-021-01418-6
apa: Polshyn, H., Zhang, Y., Kumar, M. A., Soejima, T., Ledwith, P., Watanabe, K.,
… Young, A. F. (2021). Topological charge density waves at half-integer filling
of a moiré superlattice. Nature Physics. Springer Nature. https://doi.org/10.1038/s41567-021-01418-6
chicago: Polshyn, Hryhoriy, Y. Zhang, M. A. Kumar, T. Soejima, P. Ledwith, K. Watanabe,
T. Taniguchi, A. Vishwanath, M. P. Zaletel, and A. F. Young. “Topological Charge
Density Waves at Half-Integer Filling of a Moiré Superlattice.” Nature Physics.
Springer Nature, 2021. https://doi.org/10.1038/s41567-021-01418-6.
ieee: H. Polshyn et al., “Topological charge density waves at half-integer
filling of a moiré superlattice,” Nature Physics. Springer Nature, 2021.
ista: Polshyn H, Zhang Y, Kumar MA, Soejima T, Ledwith P, Watanabe K, Taniguchi
T, Vishwanath A, Zaletel MP, Young AF. 2021. Topological charge density waves
at half-integer filling of a moiré superlattice. Nature Physics.
mla: Polshyn, Hryhoriy, et al. “Topological Charge Density Waves at Half-Integer
Filling of a Moiré Superlattice.” Nature Physics, Springer Nature, 2021,
doi:10.1038/s41567-021-01418-6.
short: H. Polshyn, Y. Zhang, M.A. Kumar, T. Soejima, P. Ledwith, K. Watanabe, T.
Taniguchi, A. Vishwanath, M.P. Zaletel, A.F. Young, Nature Physics (2021).
date_created: 2022-01-13T12:30:47Z
date_published: 2021-12-09T00:00:00Z
date_updated: 2022-01-13T14:11:31Z
day: '09'
doi: 10.1038/s41567-021-01418-6
extern: '1'
external_id:
arxiv:
- '2104.01178'
keyword:
- general physics
- astronomy
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2104.01178
month: '12'
oa: 1
oa_version: Preprint
publication: Nature Physics
publication_identifier:
eissn:
- 1745-2481
issn:
- 1745-2473
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Topological charge density waves at half-integer filling of a moiré superlattice
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '10628'
abstract:
- lang: eng
text: The surface states of 3D topological insulators in general have negligible
quantum oscillations (QOs) when the chemical potential is tuned to the Dirac points.
In contrast, we find that topological Kondo insulators (TKIs) can support surface
states with an arbitrarily large Fermi surface (FS) when the chemical potential
is pinned to the Dirac point. We illustrate that these FSs give rise to finite-frequency
QOs, which can become comparable to the extremal area of the unhybridized bulk
bands. We show that this occurs when the crystal symmetry is lowered from cubic
to tetragonal in a minimal two-orbital model. We label such surface modes as 'shadow
surface states'. Moreover, we show that the sufficient next-nearest neighbor out-of-plane
hybridization leading to shadow surface states can be self-consistently stabilized
for tetragonal TKIs. Consequently, shadow surface states provide an important
example of high-frequency QOs beyond the context of cubic TKIs.
acknowledgement: PG acknowledges support from National Science Foundation Awards No.
DMR-1824265 for this work. AG acknowledges support from the European Union's Horizon
2020 research and innovation program under the Marie Skłodowska-Curie Grant Agreement
No. 754411. EMN is supported by ASU startup grant. OE is in part supported by NSF-DMR-1904716.
article_number: '123042'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Areg
full_name: Ghazaryan, Areg
id: 4AF46FD6-F248-11E8-B48F-1D18A9856A87
last_name: Ghazaryan
orcid: 0000-0001-9666-3543
- first_name: Emilian M.
full_name: Nica, Emilian M.
last_name: Nica
- first_name: Onur
full_name: Erten, Onur
last_name: Erten
- first_name: Pouyan
full_name: Ghaemi, Pouyan
last_name: Ghaemi
citation:
ama: Ghazaryan A, Nica EM, Erten O, Ghaemi P. Shadow surface states in topological
Kondo insulators. New Journal of Physics. 2021;23(12). doi:10.1088/1367-2630/ac4124
apa: Ghazaryan, A., Nica, E. M., Erten, O., & Ghaemi, P. (2021). Shadow surface
states in topological Kondo insulators. New Journal of Physics. IOP Publishing.
https://doi.org/10.1088/1367-2630/ac4124
chicago: Ghazaryan, Areg, Emilian M. Nica, Onur Erten, and Pouyan Ghaemi. “Shadow
Surface States in Topological Kondo Insulators.” New Journal of Physics.
IOP Publishing, 2021. https://doi.org/10.1088/1367-2630/ac4124.
ieee: A. Ghazaryan, E. M. Nica, O. Erten, and P. Ghaemi, “Shadow surface states
in topological Kondo insulators,” New Journal of Physics, vol. 23, no.
12. IOP Publishing, 2021.
ista: Ghazaryan A, Nica EM, Erten O, Ghaemi P. 2021. Shadow surface states in topological
Kondo insulators. New Journal of Physics. 23(12), 123042.
mla: Ghazaryan, Areg, et al. “Shadow Surface States in Topological Kondo Insulators.”
New Journal of Physics, vol. 23, no. 12, 123042, IOP Publishing, 2021,
doi:10.1088/1367-2630/ac4124.
short: A. Ghazaryan, E.M. Nica, O. Erten, P. Ghaemi, New Journal of Physics 23 (2021).
date_created: 2022-01-16T23:01:28Z
date_published: 2021-12-23T00:00:00Z
date_updated: 2023-08-17T06:54:54Z
day: '23'
ddc:
- '530'
department:
- _id: MiLe
doi: 10.1088/1367-2630/ac4124
ec_funded: 1
external_id:
arxiv:
- '2012.11625'
isi:
- '000734063700001'
file:
- access_level: open_access
checksum: 0c3cb6816242fa8afd1cc87a5fe77821
content_type: application/pdf
creator: cchlebak
date_created: 2022-01-17T10:01:58Z
date_updated: 2022-01-17T10:01:58Z
file_id: '10632'
file_name: 2021_NewJourPhys_Ghazaryan.pdf
file_size: 2533102
relation: main_file
success: 1
file_date_updated: 2022-01-17T10:01:58Z
has_accepted_license: '1'
intvolume: ' 23'
isi: 1
issue: '12'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: New Journal of Physics
publication_identifier:
issn:
- 1367-2630
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
scopus_import: '1'
status: public
title: Shadow surface states in topological Kondo insulators
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: 23
year: '2021'
...
---
_id: '10629'
abstract:
- lang: eng
text: "Product graphs arise naturally in formal verification and program analysis.
For example, the analysis of two concurrent threads requires the product of two
component control-flow graphs, and for language inclusion of deterministic automata
the product of two automata is constructed. In many cases, the component graphs
have constant treewidth, e.g., when the input contains control-flow graphs of
programs. We consider the algorithmic analysis of products of two constant-treewidth
graphs with respect to three classic specification languages, namely, (a) algebraic
properties, (b) mean-payoff properties, and (c) initial credit for energy properties.\r\nOur
main contributions are as follows. Consider a graph G that is the product of two
constant-treewidth graphs of size n each. First, given an idempotent semiring,
we present an algorithm that computes the semiring transitive closure of G in
time Õ(n⁴). Since the output has size Θ(n⁴), our algorithm is optimal (up to
polylog factors). Second, given a mean-payoff objective, we present an O(n³)-time
algorithm for deciding whether the value of a starting state is non-negative,
improving the previously known O(n⁴) bound. Third, given an initial credit for
energy objective, we present an O(n⁵)-time algorithm for computing the minimum
initial credit for all nodes of G, improving the previously known O(n⁸) bound.
At the heart of our approach lies an algorithm for the efficient construction
of strongly-balanced tree decompositions of constant-treewidth graphs. Given a
constant-treewidth graph G' of n nodes and a positive integer λ, our algorithm
constructs a binary tree decomposition of G' of width O(λ) with the property that
the size of each subtree decreases geometrically with rate (1/2 + 2^{-λ})."
alternative_title:
- LIPIcs
article_number: '42'
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: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: 'Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Quantitative verification on
product graphs of small treewidth. In: 41st IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science. Vol 213. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.FSTTCS.2021.42'
apa: 'Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2021). Quantitative
verification on product graphs of small treewidth. In 41st IARCS Annual Conference
on Foundations of Software Technology and Theoretical Computer Science (Vol.
213). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2021.42'
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.
“Quantitative Verification on Product Graphs of Small Treewidth.” In 41st IARCS
Annual Conference on Foundations of Software Technology and Theoretical Computer
Science, Vol. 213. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.42.
ieee: K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, “Quantitative verification
on product graphs of small treewidth,” in 41st IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science, Virtual, 2021, vol.
213.
ista: 'Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2021. Quantitative verification
on product graphs of small treewidth. 41st IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of
Software Technology and Theoretical Computer Science, LIPIcs, vol. 213, 42.'
mla: Chatterjee, Krishnendu, et al. “Quantitative Verification on Product Graphs
of Small Treewidth.” 41st IARCS Annual Conference on Foundations of Software
Technology and Theoretical Computer Science, vol. 213, 42, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.FSTTCS.2021.42.
short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, in:, 41st IARCS Annual Conference
on Foundations of Software Technology and Theoretical Computer Science, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
conference:
end_date: 2021-12-17
location: Virtual
name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2021-12-15
date_created: 2022-01-16T23:01:28Z
date_published: 2021-11-29T00:00:00Z
date_updated: 2022-01-17T10:39:40Z
day: '29'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.FSTTCS.2021.42
file:
- access_level: open_access
checksum: 71141acdeffa9056f24d6dbef952d254
content_type: application/pdf
creator: cchlebak
date_created: 2022-01-17T10:36:08Z
date_updated: 2022-01-17T10:36:08Z
file_id: '10633'
file_name: 2021_LIPIcs_Chatterjee.pdf
file_size: 891566
relation: main_file
success: 1
file_date_updated: 2022-01-17T10:36:08Z
has_accepted_license: '1'
intvolume: ' 213'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
publication: 41st IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science
publication_identifier:
isbn:
- 978-3-9597-7215-0
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Quantitative verification on product graphs of small treewidth
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 213
year: '2021'
...
---
_id: '10630'
abstract:
- lang: eng
text: In the Intersection Non-emptiness problem, we are given a list of finite automata
A_1, A_2,… , A_m over a common alphabet Σ as input, and the goal is to determine
whether some string w ∈ Σ^* lies in the intersection of the languages accepted
by the automata in the list. We analyze the complexity of the Intersection Non-emptiness
problem under the promise that all input automata accept a language in some level
of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy.
Automata accepting languages from the lowest levels of these hierarchies arise
naturally in the context of model checking. We identify a dichotomy in the dot-depth
hierarchy by showing that the problem is already NP-complete when all input automata
accept languages of the levels B_0 or B_{1/2} and already PSPACE-hard when all
automata accept a language from the level B_1. Conversely, we identify a tetrachotomy
in the Straubing-Thérien hierarchy. More precisely, we show that the problem is
in AC^0 when restricted to level L_0; complete for L or NL, depending on the input
representation, when restricted to languages in the level L_{1/2}; NP-complete
when the input is given as DFAs accepting a language in L_1 or L_{3/2}; and finally,
PSPACE-complete when the input automata accept languages in level L_2 or higher.
Moreover, we show that the proof technique used to show containment in NP for
DFAs accepting languages in L_1 or L_{3/2} does not generalize to the context
of NFAs. To prove this, we identify a family of languages that provide an exponential
separation between the state complexity of general NFAs and that of partially
ordered NFAs. To the best of our knowledge, this is the first superpolynomial
separation between these two models of computation.
acknowledgement: "We like to thank Lukas Fleischer and Michael Wehar for our discussions.
This work started at the Schloss Dagstuhl Event 20483 Moderne Aspekte der Komplexitätstheorie
in der Automatentheorie https://www.dagstuhl.de/20483.\r\n"
alternative_title:
- LIPIcs
article_number: '34'
article_processing_charge: No
arxiv: 1
author:
- first_name: Emmanuel
full_name: Arrighi, Emmanuel
last_name: Arrighi
- first_name: Henning
full_name: Fernau, Henning
last_name: Fernau
- first_name: Stefan
full_name: Hoffmann, Stefan
last_name: Hoffmann
- first_name: Markus
full_name: Holzer, Markus
last_name: Holzer
- first_name: Ismael R
full_name: Jecker, Ismael R
id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
last_name: Jecker
- first_name: Mateus
full_name: De Oliveira Oliveira, Mateus
last_name: De Oliveira Oliveira
- first_name: Petra
full_name: Wolf, Petra
last_name: Wolf
citation:
ama: 'Arrighi E, Fernau H, Hoffmann S, et al. On the complexity of intersection
non-emptiness for star-free language classes. In: 41st IARCS Annual Conference
on Foundations of Software Technology and Theoretical Computer Science. Vol
213. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.FSTTCS.2021.34'
apa: 'Arrighi, E., Fernau, H., Hoffmann, S., Holzer, M., Jecker, I. R., De Oliveira
Oliveira, M., & Wolf, P. (2021). On the complexity of intersection non-emptiness
for star-free language classes. In 41st IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science (Vol. 213). Virtual:
Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2021.34'
chicago: Arrighi, Emmanuel, Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismael
R Jecker, Mateus De Oliveira Oliveira, and Petra Wolf. “On the Complexity of Intersection
Non-Emptiness for Star-Free Language Classes.” In 41st IARCS Annual Conference
on Foundations of Software Technology and Theoretical Computer Science, Vol.
213. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.FSTTCS.2021.34.
ieee: E. Arrighi et al., “On the complexity of intersection non-emptiness
for star-free language classes,” in 41st IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science, Virtual, 2021, vol.
213.
ista: 'Arrighi E, Fernau H, Hoffmann S, Holzer M, Jecker IR, De Oliveira Oliveira
M, Wolf P. 2021. On the complexity of intersection non-emptiness for star-free
language classes. 41st IARCS Annual Conference on Foundations of Software Technology
and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and
Theoretical Computer Science, LIPIcs, vol. 213, 34.'
mla: Arrighi, Emmanuel, et al. “On the Complexity of Intersection Non-Emptiness
for Star-Free Language Classes.” 41st IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science, vol. 213, 34, Schloss
Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.FSTTCS.2021.34.
short: E. Arrighi, H. Fernau, S. Hoffmann, M. Holzer, I.R. Jecker, M. De Oliveira
Oliveira, P. Wolf, in:, 41st IARCS Annual Conference on Foundations of Software
Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz Zentrum
für Informatik, 2021.
conference:
end_date: 2021-12-17
location: Virtual
name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2021-12-15
date_created: 2022-01-16T23:01:29Z
date_published: 2021-11-29T00:00:00Z
date_updated: 2022-01-17T10:56:19Z
day: '29'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.FSTTCS.2021.34
ec_funded: 1
external_id:
arxiv:
- '2110.01279'
file:
- access_level: open_access
checksum: d5a82ba893c3bc5da5914edbb3efb92b
content_type: application/pdf
creator: cchlebak
date_created: 2022-01-17T10:49:03Z
date_updated: 2022-01-17T10:49:03Z
file_id: '10634'
file_name: 2021_LIPIcs_Arrighi.pdf
file_size: 844224
relation: main_file
success: 1
file_date_updated: 2022-01-17T10:49:03Z
has_accepted_license: '1'
intvolume: ' 213'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 41st IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science
publication_identifier:
isbn:
- 978-3-9597-7215-0
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the complexity of intersection non-emptiness for star-free language classes
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 213
year: '2021'
...
---
_id: '10631'
abstract:
- lang: eng
text: We combine experimental and theoretical approaches to explore excited rotational
states of molecules embedded in helium nanodroplets using CS2 and I2 as examples.
Laser-induced nonadiabatic molecular alignment is employed to measure spectral
lines for rotational states extending beyond those initially populated at the
0.37 K droplet temperature. We construct a simple quantum-mechanical model, based
on a linear rotor coupled to a single-mode bosonic bath, to determine the rotational
energy structure in its entirety. The calculated and measured spectral lines are
in good agreement. We show that the effect of the surrounding superfluid on molecular
rotation can be rationalized by a single quantity, the angular momentum, transferred
from the molecule to the droplet.
acknowledgement: I.C. acknowledges the support by the European Union’s Horizon 2020
research and innovation programme under the Marie Sklodowska-Curie Grant Agreement
No. 665385. G.B. acknowledges support from the Austrian Science Fund (FWF), under
project No. M2461-N27. M.L. acknowledges support by the Austrian Science Fund (FWF),
under project No. P29902-N27, and by the European Research Council (ERC) Starting
Grant No. 801770 (ANGULON). H.S acknowledges support from the European Research
Council-AdG (Project No. 320459, DropletControl) and from The Villum Foundation
through a Villum Investigator grant no. 25886.
article_number: L061303
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Igor
full_name: Cherepanov, Igor
id: 339C7E5A-F248-11E8-B48F-1D18A9856A87
last_name: Cherepanov
- first_name: Giacomo
full_name: Bighin, Giacomo
id: 4CA96FD4-F248-11E8-B48F-1D18A9856A87
last_name: Bighin
orcid: 0000-0001-8823-9777
- first_name: Constant A.
full_name: Schouder, Constant A.
last_name: Schouder
- first_name: Adam S.
full_name: Chatterley, Adam S.
last_name: Chatterley
- first_name: Simon H.
full_name: Albrechtsen, Simon H.
last_name: Albrechtsen
- first_name: Alberto Viñas
full_name: Muñoz, Alberto Viñas
last_name: Muñoz
- first_name: Lars
full_name: Christiansen, Lars
last_name: Christiansen
- first_name: Henrik
full_name: Stapelfeldt, Henrik
last_name: Stapelfeldt
- first_name: Mikhail
full_name: Lemeshko, Mikhail
id: 37CB05FA-F248-11E8-B48F-1D18A9856A87
last_name: Lemeshko
orcid: 0000-0002-6990-7802
citation:
ama: Cherepanov I, Bighin G, Schouder CA, et al. Excited rotational states of molecules
in a superfluid. Physical Review A. 2021;104(6). doi:10.1103/PhysRevA.104.L061303
apa: Cherepanov, I., Bighin, G., Schouder, C. A., Chatterley, A. S., Albrechtsen,
S. H., Muñoz, A. V., … Lemeshko, M. (2021). Excited rotational states of molecules
in a superfluid. Physical Review A. American Physical Society. https://doi.org/10.1103/PhysRevA.104.L061303
chicago: Cherepanov, Igor, Giacomo Bighin, Constant A. Schouder, Adam S. Chatterley,
Simon H. Albrechtsen, Alberto Viñas Muñoz, Lars Christiansen, Henrik Stapelfeldt,
and Mikhail Lemeshko. “Excited Rotational States of Molecules in a Superfluid.”
Physical Review A. American Physical Society, 2021. https://doi.org/10.1103/PhysRevA.104.L061303.
ieee: I. Cherepanov et al., “Excited rotational states of molecules in a
superfluid,” Physical Review A, vol. 104, no. 6. American Physical Society,
2021.
ista: Cherepanov I, Bighin G, Schouder CA, Chatterley AS, Albrechtsen SH, Muñoz
AV, Christiansen L, Stapelfeldt H, Lemeshko M. 2021. Excited rotational states
of molecules in a superfluid. Physical Review A. 104(6), L061303.
mla: Cherepanov, Igor, et al. “Excited Rotational States of Molecules in a Superfluid.”
Physical Review A, vol. 104, no. 6, L061303, American Physical Society,
2021, doi:10.1103/PhysRevA.104.L061303.
short: I. Cherepanov, G. Bighin, C.A. Schouder, A.S. Chatterley, S.H. Albrechtsen,
A.V. Muñoz, L. Christiansen, H. Stapelfeldt, M. Lemeshko, Physical Review A 104
(2021).
date_created: 2022-01-16T23:01:29Z
date_published: 2021-12-30T00:00:00Z
date_updated: 2024-08-07T07:16:52Z
day: '30'
department:
- _id: MiLe
doi: 10.1103/PhysRevA.104.L061303
ec_funded: 1
external_id:
arxiv:
- '2107.00468'
isi:
- '000739618300001'
intvolume: ' 104'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://128.84.4.18/abs/2107.00468
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 26031614-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P29902
name: Quantum rotations in the presence of a many-body environment
- _id: 2688CF98-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '801770'
name: 'Angulon: physics and applications of a new quasiparticle'
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 26986C82-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02641
name: A path-integral approach to composite impurities
publication: Physical Review A
publication_identifier:
eissn:
- 2469-9934
issn:
- 2469-9926
publication_status: published
publisher: American Physical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Excited rotational states of molecules in a superfluid
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 104
year: '2021'
...
---
_id: '10635'
abstract:
- lang: eng
text: The brain efficiently performs nonlinear computations through its intricate
networks of spiking neurons, but how this is done remains elusive. While nonlinear
computations can be implemented successfully in spiking neural networks, this
requires supervised training and the resulting connectivity can be hard to interpret.
In contrast, the required connectivity for any computation in the form of a linear
dynamical system can be directly derived and understood with the spike coding
network (SCN) framework. These networks also have biologically realistic activity
patterns and are highly robust to cell death. Here we extend the SCN framework
to directly implement any polynomial dynamical system, without the need for training.
This results in networks requiring a mix of synapse types (fast, slow, and multiplicative),
which we term multiplicative spike coding networks (mSCNs). Using mSCNs, we demonstrate
how to directly derive the required connectivity for several nonlinear dynamical
systems. We also show how to carry out higher-order polynomials with coupled networks
that use only pair-wise multiplicative synapses, and provide expected numbers
of connections for each synapse type. Overall, our work demonstrates a novel method
for implementing nonlinear computations in spiking neural networks, while keeping
the attractive features of standard SCNs (robustness, realistic activity patterns,
and interpretable connectivity). Finally, we discuss the biological plausibility
of our approach, and how the high accuracy and robustness of the approach may
be of interest for neuromorphic computing.
acknowledgement: "A preprint version of this article has been peer-reviewed and recommended
by Peer Community In Neuroscience (DOI link to the recommendation: https://doi.org/10.24072/pci.cneuro.100003).\r\nWe
thank Christian Machens and Nuno Calaim for useful discussions on the project. This
report\r\ncame out of a collaboration started at the CAJAL Advanced Neuroscience
Training Programme in\r\nComputational Neuroscience in Lisbon, Portugal, during
the 2019 summer. The authors would\r\nlike to thank the participants, TAs, lecturers,
and organizers of the summer school. SWK was\r\nsupported by the Simons Collaboration
on the Global Brain (543009). WFP was supported by\r\nFCT (032077). MN was supported
by European Union Horizon 2020 (665385).\r\n"
article_number: e68
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Michele
full_name: Nardin, Michele
id: 30BD0376-F248-11E8-B48F-1D18A9856A87
last_name: Nardin
orcid: 0000-0001-8849-6570
- first_name: James W.
full_name: Phillips, James W.
last_name: Phillips
- first_name: William F.
full_name: Podlaski, William F.
last_name: Podlaski
- first_name: Sander W.
full_name: Keemink, Sander W.
last_name: Keemink
citation:
ama: Nardin M, Phillips JW, Podlaski WF, Keemink SW. Nonlinear computations in spiking
neural networks through multiplicative synapses. Peer Community Journal.
2021;1. doi:10.24072/pcjournal.69
apa: Nardin, M., Phillips, J. W., Podlaski, W. F., & Keemink, S. W. (2021).
Nonlinear computations in spiking neural networks through multiplicative synapses.
Peer Community Journal. Centre Mersenne ; Peer Community In. https://doi.org/10.24072/pcjournal.69
chicago: Nardin, Michele, James W. Phillips, William F. Podlaski, and Sander W.
Keemink. “Nonlinear Computations in Spiking Neural Networks through Multiplicative
Synapses.” Peer Community Journal. Centre Mersenne ; Peer Community In,
2021. https://doi.org/10.24072/pcjournal.69.
ieee: M. Nardin, J. W. Phillips, W. F. Podlaski, and S. W. Keemink, “Nonlinear computations
in spiking neural networks through multiplicative synapses,” Peer Community
Journal, vol. 1. Centre Mersenne ; Peer Community In, 2021.
ista: Nardin M, Phillips JW, Podlaski WF, Keemink SW. 2021. Nonlinear computations
in spiking neural networks through multiplicative synapses. Peer Community Journal.
1, e68.
mla: Nardin, Michele, et al. “Nonlinear Computations in Spiking Neural Networks
through Multiplicative Synapses.” Peer Community Journal, vol. 1, e68,
Centre Mersenne ; Peer Community In, 2021, doi:10.24072/pcjournal.69.
short: M. Nardin, J.W. Phillips, W.F. Podlaski, S.W. Keemink, Peer Community Journal
1 (2021).
date_created: 2022-01-17T11:12:40Z
date_published: 2021-12-15T00:00:00Z
date_updated: 2022-01-17T13:30:01Z
day: '15'
ddc:
- '519'
department:
- _id: GradSch
- _id: JoCs
doi: 10.24072/pcjournal.69
ec_funded: 1
external_id:
arxiv:
- '2009.03857'
file:
- access_level: open_access
checksum: cd9af6b331918608f2e3d1c7940cbf4f
content_type: application/pdf
creator: mnardin
date_created: 2022-01-17T11:15:26Z
date_updated: 2022-01-17T11:15:26Z
file_id: '10636'
file_name: 10_24072_pcjournal_69.pdf
file_size: 3311494
relation: main_file
success: 1
file_date_updated: 2022-01-17T11:15:26Z
has_accepted_license: '1'
intvolume: ' 1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: Peer Community Journal
publication_identifier:
eissn:
- 2804-3871
publication_status: published
publisher: Centre Mersenne ; Peer Community In
quality_controlled: '1'
status: public
title: Nonlinear computations in spiking neural networks through multiplicative synapses
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 1
year: '2021'
...
---
_id: '10644'
abstract:
- lang: eng
text: The purpose of this application note is to demonstrate a working example of
a superconducting qubit measurement in a Bluefors cryostat using the Keysight
quantum control hardware. Our motivation is twofold. First, we provide pre-qualification
data that the Bluefors cryostat, including filtering and wiring, can support long-lived
qubits. Second, we demonstrate that the Keysight system (controlled using Labber)
provides a straightforward solution to perform these characterization measurements.
This document is intended as a brief guide for starting an experimental platform
for testing superconducting qubits. The setup described here is an immediate jumping
off point for a suite of applications including testing quantum logical gates,
quantum optics with microwaves, or even using the qubit itself as a sensitive
probe of local electromagnetic fields. Qubit measurements rely on high performance
of both the physical sample environment and the measurement electronics. An overview
of the cryogenic system is shown in Figure 1, and an overview of the integration
between the electronics and cryostat (including wiring details) is shown in Figure
2.
alternative_title:
- Bluefors Blog
article_processing_charge: No
author:
- first_name: Russell
full_name: Lake, Russell
last_name: Lake
- first_name: Slawomir
full_name: Simbierowicz, Slawomir
last_name: Simbierowicz
- first_name: Philip
full_name: Krantz, Philip
last_name: Krantz
- first_name: Farid
full_name: Hassani, Farid
id: 2AED110C-F248-11E8-B48F-1D18A9856A87
last_name: Hassani
- first_name: Johannes M
full_name: Fink, Johannes M
id: 4B591CBA-F248-11E8-B48F-1D18A9856A87
last_name: Fink
orcid: 0000-0001-8112-028X
citation:
ama: 'Lake R, Simbierowicz S, Krantz P, Hassani F, Fink JM. The Bluefors Dilution
Refrigerator as an Integrated Quantum Measurement System. Helsinki, Finland:
Bluefors Oy; 2021.'
apa: 'Lake, R., Simbierowicz, S., Krantz, P., Hassani, F., & Fink, J. M. (2021).
The Bluefors dilution refrigerator as an integrated quantum measurement system.
Helsinki, Finland: Bluefors Oy.'
chicago: 'Lake, Russell, Slawomir Simbierowicz, Philip Krantz, Farid Hassani, and
Johannes M Fink. The Bluefors Dilution Refrigerator as an Integrated Quantum
Measurement System. Helsinki, Finland: Bluefors Oy, 2021.'
ieee: 'R. Lake, S. Simbierowicz, P. Krantz, F. Hassani, and J. M. Fink, The Bluefors
dilution refrigerator as an integrated quantum measurement system. Helsinki,
Finland: Bluefors Oy, 2021.'
ista: 'Lake R, Simbierowicz S, Krantz P, Hassani F, Fink JM. 2021. The Bluefors
dilution refrigerator as an integrated quantum measurement system, Helsinki, Finland:
Bluefors Oy, 9p.'
mla: Lake, Russell, et al. The Bluefors Dilution Refrigerator as an Integrated
Quantum Measurement System. Bluefors Oy, 2021.
short: R. Lake, S. Simbierowicz, P. Krantz, F. Hassani, J.M. Fink, The Bluefors
Dilution Refrigerator as an Integrated Quantum Measurement System, Bluefors Oy,
Helsinki, Finland, 2021.
date_created: 2022-01-19T08:29:57Z
date_published: 2021-04-20T00:00:00Z
date_updated: 2022-01-19T09:11:33Z
day: '20'
department:
- _id: JoFi
keyword:
- Application note
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://bluefors.com/blog/integrated-quantum-measurement-system/
month: '04'
oa: 1
oa_version: Published Version
page: '9'
place: Helsinki, Finland
publication_status: published
publisher: Bluefors Oy
quality_controlled: '1'
status: public
title: The Bluefors dilution refrigerator as an integrated quantum measurement system
type: other_academic_publication
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '10645'
abstract:
- lang: eng
text: "Superconducting qubits have emerged as a highly versatile and useful platform
for quantum technological applications [1]. Bluefors and Zurich Instruments have
supported the growth of this field from the 2010s onwards by providing well-engineered
and reliable measurement infrastructure [2]– [6]. Having a long and stable qubit
lifetime is a critical system property. Therefore, considerable effort has already
gone into measuring qubit energy-relaxation timescales and their fluctuations,
see Refs. [7]–[10] among others. Accurately extracting the statistics of a quantum
device requires users to perform time consuming measurements. One measurement
challenge is that the detection of the state-dependent\r\nresponse of a superconducting
resonator due to a dispersively-coupled qubit requires an inherently low signal
level. Consequently, measurements must be performed using a microwave probe that
contains only a few microwave photons. Improving the signal-to-noise ratio (SNR)
by using near-quantum limited parametric amplifiers as well as the use of optimized
signal processing enabled by efficient room temperature instrumentation help to
reduce measurement time. An empirical observation for fixed frequency transmons
from recent literature is that as the energy-relaxation time \U0001D447\U0001D4471
increases, so do its natural temporal fluctuations [7], [10]. This necessitates
many repeated measurements to understand the statistics (see for example, Ref.
[10]). In addition, as state-of-the-art qubits increase in lifetime, longer\r\nmeasurement
times are expected to obtain accurate statistics. As described below, the scaling
of the widths of the qubit energy-relaxation distributions also reveal clues about
the origin of the energy-relaxation."
alternative_title:
- Bluefors Blog
article_processing_charge: No
author:
- first_name: Slawomir
full_name: Simbierowicz, Slawomir
last_name: Simbierowicz
- first_name: Chunyan
full_name: Shi, Chunyan
last_name: Shi
- first_name: Michele
full_name: Collodo, Michele
last_name: Collodo
- first_name: Moritz
full_name: Kirste, Moritz
last_name: Kirste
- first_name: Farid
full_name: Hassani, Farid
id: 2AED110C-F248-11E8-B48F-1D18A9856A87
last_name: Hassani
- first_name: Johannes M
full_name: Fink, Johannes M
id: 4B591CBA-F248-11E8-B48F-1D18A9856A87
last_name: Fink
orcid: 0000-0001-8112-028X
- first_name: Jonas
full_name: Bylander, Jonas
last_name: Bylander
- first_name: Daniel
full_name: Perez Lozano, Daniel
last_name: Perez Lozano
- first_name: Russell
full_name: Lake, Russell
last_name: Lake
citation:
ama: 'Simbierowicz S, Shi C, Collodo M, et al. Qubit Energy-Relaxation Statistics
in the Bluefors Quantum Measurement System. Helsinki, Finland: Bluefors Oy;
2021.'
apa: 'Simbierowicz, S., Shi, C., Collodo, M., Kirste, M., Hassani, F., Fink, J.
M., … Lake, R. (2021). Qubit energy-relaxation statistics in the Bluefors quantum
measurement system. Helsinki, Finland: Bluefors Oy.'
chicago: 'Simbierowicz, Slawomir, Chunyan Shi, Michele Collodo, Moritz Kirste, Farid
Hassani, Johannes M Fink, Jonas Bylander, Daniel Perez Lozano, and Russell Lake.
Qubit Energy-Relaxation Statistics in the Bluefors Quantum Measurement System.
Helsinki, Finland: Bluefors Oy, 2021.'
ieee: 'S. Simbierowicz et al., Qubit energy-relaxation statistics in the
Bluefors quantum measurement system. Helsinki, Finland: Bluefors Oy, 2021.'
ista: 'Simbierowicz S, Shi C, Collodo M, Kirste M, Hassani F, Fink JM, Bylander
J, Perez Lozano D, Lake R. 2021. Qubit energy-relaxation statistics in the Bluefors
quantum measurement system, Helsinki, Finland: Bluefors Oy, 8p.'
mla: Simbierowicz, Slawomir, et al. Qubit Energy-Relaxation Statistics in the
Bluefors Quantum Measurement System. Bluefors Oy, 2021.
short: S. Simbierowicz, C. Shi, M. Collodo, M. Kirste, F. Hassani, J.M. Fink, J.
Bylander, D. Perez Lozano, R. Lake, Qubit Energy-Relaxation Statistics in the
Bluefors Quantum Measurement System, Bluefors Oy, Helsinki, Finland, 2021.
date_created: 2022-01-19T08:41:14Z
date_published: 2021-06-03T00:00:00Z
date_updated: 2022-01-19T09:11:39Z
day: '03'
department:
- _id: JoFi
keyword:
- Application note
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://bluefors.com/blog/application-note-qubit-energy-relaxation-statistics-bluefors-quantum-measurement-system/
month: '06'
oa: 1
oa_version: Published Version
page: '8'
place: Helsinki, Finland
publication_status: published
publisher: Bluefors Oy
quality_controlled: '1'
status: public
title: Qubit energy-relaxation statistics in the Bluefors quantum measurement system
type: other_academic_publication
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '10649'
abstract:
- lang: eng
text: Harnessing the properties of vortices in superconductors is crucial for fundamental
science and technological applications; thus, it has been an ongoing goal to locally
probe and control vortices. Here, we use a scanning probe technique that enables
studies of vortex dynamics in superconducting systems by leveraging the resonant
behavior of a raster-scanned, magnetic-tipped cantilever. This experimental setup
allows us to image and control vortices, as well as extract key energy scales
of the vortex interactions. Applying this technique to lattices of superconductor
island arrays on a metal, we obtain a variety of striking spatial patterns that
encode information about the energy landscape for vortices in the system. We interpret
these patterns in terms of local vortex dynamics and extract the relative strengths
of the characteristic energy scales in the system, such as the vortex-magnetic
field and vortex-vortex interaction strengths, as well as the vortex chemical
potential. We also demonstrate that the relative strengths of the interactions
can be tuned and show how these interactions shift with an applied bias. The high
degree of tunability and local nature of such vortex imaging and control not only
enable new understanding of vortex interactions, but also have potential applications
in more complex systems such as those relevant to quantum computing.
acknowledgement: This work was supported by the Department of Energy (DOE) Basic Energy
Sciences under Grant No. DE-SC0012649 and the National Science Foundation (NSF)
under Grant No. DMR 17-10437. V.C. was supported by the Gordon and Betty Moore Foundation
EPiQS Initiative through Grant No. GBMF4305. N.M. also acknowledges support from
DOE-EFRC under Grant No. DE-SC0021238 for analysis/manuscript preparation. This
research was carried out in part in the Materials Research Laboratory Central Research
Facilities, University of Illinois.
article_number: '224526'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Tyler R.
full_name: Naibert, Tyler R.
last_name: Naibert
- first_name: Hryhoriy
full_name: Polshyn, Hryhoriy
id: edfc7cb1-526e-11ec-b05a-e6ecc27e4e48
last_name: Polshyn
orcid: 0000-0001-8223-8896
- first_name: Rita
full_name: Garrido-Menacho, Rita
last_name: Garrido-Menacho
- first_name: Malcolm
full_name: Durkin, Malcolm
last_name: Durkin
- first_name: Brian
full_name: Wolin, Brian
last_name: Wolin
- first_name: Victor
full_name: Chua, Victor
last_name: Chua
- first_name: Ian
full_name: Mondragon-Shem, Ian
last_name: Mondragon-Shem
- first_name: Taylor
full_name: Hughes, Taylor
last_name: Hughes
- first_name: Nadya
full_name: Mason, Nadya
last_name: Mason
- first_name: Raffi
full_name: Budakian, Raffi
last_name: Budakian
citation:
ama: Naibert TR, Polshyn H, Garrido-Menacho R, et al. Imaging and controlling vortex
dynamics in mesoscopic superconductor-normal-metal-superconductor arrays. Physical
Review B. 2021;103(22). doi:10.1103/physrevb.103.224526
apa: Naibert, T. R., Polshyn, H., Garrido-Menacho, R., Durkin, M., Wolin, B., Chua,
V., … Budakian, R. (2021). Imaging and controlling vortex dynamics in mesoscopic
superconductor-normal-metal-superconductor arrays. Physical Review B. American
Physical Society. https://doi.org/10.1103/physrevb.103.224526
chicago: Naibert, Tyler R., Hryhoriy Polshyn, Rita Garrido-Menacho, Malcolm Durkin,
Brian Wolin, Victor Chua, Ian Mondragon-Shem, Taylor Hughes, Nadya Mason, and
Raffi Budakian. “Imaging and Controlling Vortex Dynamics in Mesoscopic Superconductor-Normal-Metal-Superconductor
Arrays.” Physical Review B. American Physical Society, 2021. https://doi.org/10.1103/physrevb.103.224526.
ieee: T. R. Naibert et al., “Imaging and controlling vortex dynamics in mesoscopic
superconductor-normal-metal-superconductor arrays,” Physical Review B,
vol. 103, no. 22. American Physical Society, 2021.
ista: Naibert TR, Polshyn H, Garrido-Menacho R, Durkin M, Wolin B, Chua V, Mondragon-Shem
I, Hughes T, Mason N, Budakian R. 2021. Imaging and controlling vortex dynamics
in mesoscopic superconductor-normal-metal-superconductor arrays. Physical Review
B. 103(22), 224526.
mla: Naibert, Tyler R., et al. “Imaging and Controlling Vortex Dynamics in Mesoscopic
Superconductor-Normal-Metal-Superconductor Arrays.” Physical Review B,
vol. 103, no. 22, 224526, American Physical Society, 2021, doi:10.1103/physrevb.103.224526.
short: T.R. Naibert, H. Polshyn, R. Garrido-Menacho, M. Durkin, B. Wolin, V. Chua,
I. Mondragon-Shem, T. Hughes, N. Mason, R. Budakian, Physical Review B 103 (2021).
date_created: 2022-01-20T09:39:40Z
date_published: 2021-06-24T00:00:00Z
date_updated: 2022-01-24T08:25:18Z
day: '24'
doi: 10.1103/physrevb.103.224526
extern: '1'
external_id:
arxiv:
- '1705.08956'
intvolume: ' 103'
issue: '22'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1705.08956
month: '06'
oa: 1
oa_version: Preprint
publication: Physical Review B
publication_identifier:
eissn:
- 2469-9969
issn:
- 2469-9950
publication_status: published
publisher: American Physical Society
quality_controlled: '1'
status: public
title: Imaging and controlling vortex dynamics in mesoscopic superconductor-normal-metal-superconductor
arrays
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 103
year: '2021'
...
---
_id: '10651'
abstract:
- lang: eng
text: Electrons in the moiré flat bands of magic angle twisted bilayer graphene
aligned to hexagonal boron nitride can break time reversal symmetry and open an
interaction-driven, topological gap. The resulting magnetic order and associated
quantized anomalous Hall effect have properties that diverge substantially from
quantized anomalous Hall effects observed in other systems. I will present transport
data and scanning probe magnetometry data acquired using a nanoSQUID-on-tip microscope.
A quantitative analysis of the magnitude of the magnetization of the Chern magnet
shows that the magnetic moment per moiré unit cell substantially exceeds 1 μB
and grows rapidly in the topological gap, consistent with an orbital origin for
the magnetic order. We find that the Barkhausen jumps observed in transport measurements
can be mapped directly to microscopic motion of ferromagnetic domain walls. These
domain walls are strongly pinned to disorder in the device and are reproducible
across thermal cycles, suggesting coupling between the magnetic degrees of freedom
and structural inhomogeneity.
acknowledgement: I acknowledge and appreciate support from the Hertz Foundation and
from the National Science Foundation Graduate Research Fellowship Program under
grant 1650114.
alternative_title:
- Bulletin of the American Physical Society
article_number: L42.00012
article_processing_charge: No
author:
- first_name: Charles
full_name: Tschirhart, Charles
last_name: Tschirhart
- first_name: Marec
full_name: Serlin, Marec
last_name: Serlin
- first_name: Hryhoriy
full_name: Polshyn, Hryhoriy
id: edfc7cb1-526e-11ec-b05a-e6ecc27e4e48
last_name: Polshyn
orcid: 0000-0001-8223-8896
- first_name: Avi G.
full_name: Shragai, Avi G.
last_name: Shragai
- first_name: Zhengchao
full_name: Xia, Zhengchao
last_name: Xia
- first_name: Jiacheng
full_name: Zhu, Jiacheng
last_name: Zhu
- first_name: Yuxuan
full_name: Zhang, Yuxuan
last_name: Zhang
- first_name: Kenji
full_name: Watanabe, Kenji
last_name: Watanabe
- first_name: Takashi
full_name: Taniguchi, Takashi
last_name: Taniguchi
- first_name: Martin E.
full_name: Huber, Martin E.
last_name: Huber
- first_name: Andrea
full_name: Young, Andrea
last_name: Young
citation:
ama: 'Tschirhart C, Serlin M, Polshyn H, et al. Probing orbital Chern ferromagnet
phase in twisted bilayer graphene. In: APS March Meeting 2021. Vol 66.
American Physical Society; 2021.'
apa: 'Tschirhart, C., Serlin, M., Polshyn, H., Shragai, A. G., Xia, Z., Zhu, J.,
… Young, A. (2021). Probing orbital Chern ferromagnet phase in twisted bilayer
graphene. In APS March Meeting 2021 (Vol. 66). Virtual, United States:
American Physical Society.'
chicago: Tschirhart, Charles, Marec Serlin, Hryhoriy Polshyn, Avi G. Shragai, Zhengchao
Xia, Jiacheng Zhu, Yuxuan Zhang, et al. “Probing Orbital Chern Ferromagnet Phase
in Twisted Bilayer Graphene.” In APS March Meeting 2021, Vol. 66. American
Physical Society, 2021.
ieee: C. Tschirhart et al., “Probing orbital Chern ferromagnet phase in twisted
bilayer graphene,” in APS March Meeting 2021, Virtual, United States, 2021,
vol. 66, no. 1.
ista: 'Tschirhart C, Serlin M, Polshyn H, Shragai AG, Xia Z, Zhu J, Zhang Y, Watanabe
K, Taniguchi T, Huber ME, Young A. 2021. Probing orbital Chern ferromagnet phase
in twisted bilayer graphene. APS March Meeting 2021. APS: American Physical Society,
Bulletin of the American Physical Society, vol. 66, L42.00012.'
mla: Tschirhart, Charles, et al. “Probing Orbital Chern Ferromagnet Phase in Twisted
Bilayer Graphene.” APS March Meeting 2021, vol. 66, no. 1, L42.00012, American
Physical Society, 2021.
short: C. Tschirhart, M. Serlin, H. Polshyn, A.G. Shragai, Z. Xia, J. Zhu, Y. Zhang,
K. Watanabe, T. Taniguchi, M.E. Huber, A. Young, in:, APS March Meeting 2021,
American Physical Society, 2021.
conference:
end_date: 2021-03-19
location: Virtual, United States
name: 'APS: American Physical Society'
start_date: 2021-03-15
date_created: 2022-01-20T15:43:16Z
date_published: 2021-03-01T00:00:00Z
date_updated: 2022-01-27T09:37:51Z
day: '01'
extern: '1'
intvolume: ' 66'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://meetings.aps.org/Meeting/MAR21/Session/L42.12
month: '03'
oa: 1
oa_version: None
publication: APS March Meeting 2021
publication_identifier:
issn:
- 0003-0503
publication_status: published
publisher: American Physical Society
quality_controlled: '1'
status: public
title: Probing orbital Chern ferromagnet phase in twisted bilayer graphene
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 66
year: '2021'
...
---
_id: '10655'
abstract:
- lang: eng
text: "Adeno-associated viruses (AAVs) are widely used to deliver genetic material
in vivo to distinct cell types such as neurons or glial cells, allowing for targeted
manipulation. Transduction of microglia is mostly excluded from this strategy,
likely due to the cells’ heterogeneous state upon environmental changes, which
makes AAV design challenging. Here, we established the retina as a model system
for microglial AAV validation and optimization. First, we show that AAV2/6 transduced
microglia in both synaptic layers, where layer preference corresponds to the intravitreal
or subretinal delivery method. Surprisingly, we observed significantly enhanced
microglial transduction during photoreceptor degeneration. Thus, we modified the
AAV6 capsid to reduce heparin binding by introducing four point mutations (K531E,
R576Q, K493S, and K459S), resulting in increased microglial transduction in the
outer plexiform layer. Finally, to improve microglial-specific transduction, we
validated a Cre-dependent transgene delivery cassette for use in combination with
the Cx3cr1CreERT2 mouse line. Together, our results provide a foundation for future
studies optimizing AAV-mediated microglia transduction and highlight that environmental
conditions influence microglial transduction efficiency.\r\n"
acknowledged_ssus:
- _id: Bio
- _id: LifeSc
- _id: PreCl
acknowledgement: This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement no. 715571). The research was supported by the Scientific Service
Units (SSU) of IST Austria through resources provided by the Bioimaging Facility,
the Life Science Facility, and the Pre-Clinical Facility, namely Sonja Haslinger
and Michael Schunn for their animal colony management and support. We would also
like to thank Chakrabarty Lab for sharing the plasmids for AAV2/6 production. Finally,
we would like to thank the Siegert team members for discussion about the manuscript.
article_processing_charge: Yes
article_type: original
author:
- 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: Gabriele M.
full_name: Wögenstein, Gabriele M.
last_name: Wögenstein
- first_name: Gloria
full_name: Colombo, Gloria
id: 3483CF6C-F248-11E8-B48F-1D18A9856A87
last_name: Colombo
orcid: 0000-0001-9434-8902
- first_name: Raquel
full_name: Casado Polanco, Raquel
id: 15240fc1-dbcd-11ea-9d1d-ac5a786425fd
last_name: Casado Polanco
orcid: 0000-0001-8293-4568
- first_name: Sandra
full_name: Siegert, Sandra
id: 36ACD32E-F248-11E8-B48F-1D18A9856A87
last_name: Siegert
orcid: 0000-0001-8635-0877
citation:
ama: Maes ME, Wögenstein GM, Colombo G, Casado Polanco R, Siegert S. Optimizing
AAV2/6 microglial targeting identified enhanced efficiency in the photoreceptor
degenerative environment. Molecular Therapy - Methods and Clinical Development.
2021;23:210-224. doi:10.1016/j.omtm.2021.09.006
apa: Maes, M. E., Wögenstein, G. M., Colombo, G., Casado Polanco, R., & Siegert,
S. (2021). Optimizing AAV2/6 microglial targeting identified enhanced efficiency
in the photoreceptor degenerative environment. Molecular Therapy - Methods
and Clinical Development. Elsevier. https://doi.org/10.1016/j.omtm.2021.09.006
chicago: Maes, Margaret E, Gabriele M. Wögenstein, Gloria Colombo, Raquel Casado
Polanco, and Sandra Siegert. “Optimizing AAV2/6 Microglial Targeting Identified
Enhanced Efficiency in the Photoreceptor Degenerative Environment.” Molecular
Therapy - Methods and Clinical Development. Elsevier, 2021. https://doi.org/10.1016/j.omtm.2021.09.006.
ieee: M. E. Maes, G. M. Wögenstein, G. Colombo, R. Casado Polanco, and S. Siegert,
“Optimizing AAV2/6 microglial targeting identified enhanced efficiency in the
photoreceptor degenerative environment,” Molecular Therapy - Methods and Clinical
Development, vol. 23. Elsevier, pp. 210–224, 2021.
ista: Maes ME, Wögenstein GM, Colombo G, Casado Polanco R, Siegert S. 2021. Optimizing
AAV2/6 microglial targeting identified enhanced efficiency in the photoreceptor
degenerative environment. Molecular Therapy - Methods and Clinical Development.
23, 210–224.
mla: Maes, Margaret E., et al. “Optimizing AAV2/6 Microglial Targeting Identified
Enhanced Efficiency in the Photoreceptor Degenerative Environment.” Molecular
Therapy - Methods and Clinical Development, vol. 23, Elsevier, 2021, pp. 210–24,
doi:10.1016/j.omtm.2021.09.006.
short: M.E. Maes, G.M. Wögenstein, G. Colombo, R. Casado Polanco, S. Siegert, Molecular
Therapy - Methods and Clinical Development 23 (2021) 210–224.
date_created: 2022-01-23T23:01:28Z
date_published: 2021-12-10T00:00:00Z
date_updated: 2023-11-16T13:12:03Z
day: '10'
ddc:
- '570'
department:
- _id: SaSi
- _id: SiHi
doi: 10.1016/j.omtm.2021.09.006
ec_funded: 1
external_id:
isi:
- '000748748500019'
file:
- access_level: open_access
checksum: 77dc540e8011c5475031bdf6ccef20a6
content_type: application/pdf
creator: cchlebak
date_created: 2022-01-24T07:43:09Z
date_updated: 2022-01-24T07:43:09Z
file_id: '10657'
file_name: 2021_MolTherMethodsClinDev_Maes.pdf
file_size: 4794147
relation: main_file
success: 1
file_date_updated: 2022-01-24T07:43:09Z
has_accepted_license: '1'
intvolume: ' 23'
isi: 1
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 210-224
project:
- _id: 25D4A630-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '715571'
name: Microglia action towards neuronal circuit formation and function in health
and disease
publication: Molecular Therapy - Methods and Clinical Development
publication_identifier:
eissn:
- 2329-0501
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimizing AAV2/6 microglial targeting identified enhanced efficiency in the
photoreceptor degenerative environment
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2021'
...
---
_id: '11814'
abstract:
- lang: eng
text: "Differentially private algorithms protect individuals in data analysis scenarios
by ensuring that there is only a weak correlation between the existence of the
user in the data and the result of the analysis. Dynamic graph algorithms maintain
the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph
where nodes or edges are inserted or deleted over time. They output the value
of the solution after each update operation, i.e., continuously. We study (event-level
and user-level) differentially private algorithms for graph problems under continual
observation, i.e., differentially private dynamic graph algorithms. We present
event-level private algorithms for partially dynamic counting-based problems such
as triangle count that improve the additive error by a polynomial factor (in the
length T of the update sequence) on the state of the art, resulting in the first
algorithms with additive error polylogarithmic in T.\r\nWe also give ε-differentially
private and partially dynamic algorithms for minimum spanning tree, minimum cut,
densest subgraph, and maximum matching. The additive error of our improved MST
algorithm is O(W log^{3/2}T / ε), where W is the maximum weight of any edge, which,
as we show, is tight up to a (√{log T} / ε)-factor. For the other problems, we
present a partially-dynamic algorithm with multiplicative error (1+β) for any
constant β > 0 and additive error O(W log(nW) log(T) / (ε β)). Finally, we show
that the additive error for a broad class of dynamic graph algorithms with user-level
privacy must be linear in the value of the output solution’s range."
alternative_title:
- LIPIcs
article_number: '42'
article_processing_charge: No
arxiv: 1
author:
- first_name: Hendrik
full_name: Fichtenberger, Hendrik
last_name: Fichtenberger
- 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: Wolfgang
full_name: Ost, Wolfgang
last_name: Ost
citation:
ama: 'Fichtenberger H, Henzinger MH, Ost W. Differentially private algorithms for
graphs under continual observation. In: 29th Annual European Symposium on Algorithms.
Vol 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.ESA.2021.42'
apa: 'Fichtenberger, H., Henzinger, M. H., & Ost, W. (2021). Differentially
private algorithms for graphs under continual observation. In 29th Annual European
Symposium on Algorithms (Vol. 204). Lisbon, Portual: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2021.42'
chicago: Fichtenberger, Hendrik, Monika H Henzinger, and Wolfgang Ost. “Differentially
Private Algorithms for Graphs under Continual Observation.” In 29th Annual
European Symposium on Algorithms, Vol. 204. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ESA.2021.42.
ieee: H. Fichtenberger, M. H. Henzinger, and W. Ost, “Differentially private algorithms
for graphs under continual observation,” in 29th Annual European Symposium
on Algorithms, Lisbon, Portual, 2021, vol. 204.
ista: 'Fichtenberger H, Henzinger MH, Ost W. 2021. Differentially private algorithms
for graphs under continual observation. 29th Annual European Symposium on Algorithms.
ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 204, 42.'
mla: Fichtenberger, Hendrik, et al. “Differentially Private Algorithms for Graphs
under Continual Observation.” 29th Annual European Symposium on Algorithms,
vol. 204, 42, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.ESA.2021.42.
short: H. Fichtenberger, M.H. Henzinger, W. Ost, in:, 29th Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
conference:
end_date: 2021-09-08
location: Lisbon, Portual
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2021-09-06
date_created: 2022-08-12T07:04:44Z
date_published: 2021-08-31T00:00:00Z
date_updated: 2023-02-14T08:28:56Z
day: '31'
doi: 10.4230/LIPIcs.ESA.2021.42
extern: '1'
external_id:
arxiv:
- '2106.14756'
intvolume: ' 204'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.ESA.2021.42
month: '08'
oa: 1
oa_version: Published Version
publication: 29th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959772044'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Differentially private algorithms for graphs under continual observation
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 204
year: '2021'
...
---
_id: '11886'
abstract:
- lang: eng
text: "We present a deterministic (1+\U0001D45C(1))-approximation (\U0001D45B1/2+\U0001D45C(1)+\U0001D4371+\U0001D45C(1))-time
algorithm for solving the single-source shortest paths problem on distributed
weighted networks (the \\sf CONGEST model); here \U0001D45B is the number of nodes
in the network, \U0001D437 is its (hop) diameter, and edge weights are positive
integers from 1 to poly(\U0001D45B). This is the first nontrivial deterministic
algorithm for this problem. It also improves (i) the running time of the randomized
(1+\U0001D45C(1))-approximation \U0001D442̃ (\U0001D45B√\U0001D4371/4+\U0001D437)-time
algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565--573] by a factor
of as large as \U0001D45B1/8, and (ii) the \U0001D442(\U0001D716−1log\U0001D716−1)-approximation
factor of Lenzen and Patt-Shamir's \U0001D442̃ (\U0001D45B1/2+\U0001D716+\U0001D437)-time
algorithm [in Proceedings of STOC, 2013, pp. 381--390] within the same running
time. (Throughout, we use \U0001D442̃ (⋅) to hide polylogarithmic factors in \U0001D45B.)
Our running time matches the known time lower bound of Ω(\U0001D45B/log\U0001D45B‾‾‾‾‾‾‾√+\U0001D437)
[M. Elkin, SIAM J. Comput., 36 (2006), pp. 433--456], thus essentially settling
the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT
News, 35 (2004), pp. 40--57]. It also implies a (2+\U0001D45C(1))-approximation
(\U0001D45B1/2+\U0001D45C(1)+\U0001D4371+\U0001D45C(1))-time algorithm for approximating
a network's weighted diameter which almost matches the lower bound by Holzer and
Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform.,
Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques
which might be of independent interest and useful in other settings: (i) a deterministic
process that replaces the “hitting set argument” commonly used for shortest paths
computation in various settings, and (ii) a simple, deterministic construction
of an (\U0001D45B\U0001D45C(1),\U0001D45C(1))-hop set of size \U0001D45B1+\U0001D45C(1).
We combine these techniques with many distributed algorithmic techniques, some
of which are from problems that are not directly related to shortest paths, e.g.,
ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete
Math., 1 (1988), pp. 434--446], source detection [C. Lenzen and D. Peleg, in Proceedings
of PODC, 2013, pp. 375--382], and partial distance estimation [C. Lenzen and B.
Patt-Shamir, in Proceedings of PODC, 2015, pp. 153--162]. Our hop set construction
also leads to single-source shortest paths algorithms in two other settings: (i)
a (1+\U0001D45C(1))-approximation \U0001D45B\U0001D45C(1)-time algorithm on congested
cliques, and (ii) a (1+\U0001D45C(1))-approximation \U0001D45B\U0001D45C(1)-pass
\U0001D45B1+\U0001D45C(1)-space streaming algorithm. The first result answers
an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565--573].
The second result partially answers an open problem raised by McGregor in 2006
[List of Open Problems in Sublinear Algorithms: Problem 14]."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- 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: Sebastian
full_name: Krinninger, Sebastian
last_name: Krinninger
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: Henzinger MH, Krinninger S, Nanongkai D. A deterministic almost-tight distributed
algorithm for approximating single-source shortest paths. SIAM Journal on Computing.
2021;50(3):STOC16-98-STOC16-137. doi:10.1137/16m1097808
apa: Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2021). A deterministic
almost-tight distributed algorithm for approximating single-source shortest paths.
SIAM Journal on Computing. Society for Industrial & Applied Mathematics.
https://doi.org/10.1137/16m1097808
chicago: Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic
Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.”
SIAM Journal on Computing. Society for Industrial & Applied Mathematics,
2021. https://doi.org/10.1137/16m1097808.
ieee: M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight
distributed algorithm for approximating single-source shortest paths,” SIAM
Journal on Computing, vol. 50, no. 3. Society for Industrial & Applied
Mathematics, pp. STOC16-98-STOC16-137, 2021.
ista: Henzinger MH, Krinninger S, Nanongkai D. 2021. A deterministic almost-tight
distributed algorithm for approximating single-source shortest paths. SIAM Journal
on Computing. 50(3), STOC16-98-STOC16-137.
mla: Henzinger, Monika H., et al. “A Deterministic Almost-Tight Distributed Algorithm
for Approximating Single-Source Shortest Paths.” SIAM Journal on Computing,
vol. 50, no. 3, Society for Industrial & Applied Mathematics, 2021, pp. STOC16-98-STOC16-137,
doi:10.1137/16m1097808.
short: M.H. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 50
(2021) STOC16-98-STOC16-137.
date_created: 2022-08-17T07:54:45Z
date_published: 2021-05-01T00:00:00Z
date_updated: 2023-02-17T14:12:49Z
day: '01'
doi: 10.1137/16m1097808
extern: '1'
external_id:
arxiv:
- '1504.07056'
intvolume: ' 50'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1504.07056
month: '05'
oa: 1
oa_version: Preprint
page: STOC16-98-STOC16-137
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: A deterministic almost-tight distributed algorithm for approximating single-source
shortest paths
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 50
year: '2021'
...
---
_id: '11919'
abstract:
- lang: eng
text: "Maintaining and updating shortest paths information in a graph is a fundamental
problem with many applications. As computations on dense graphs can be prohibitively
expensive, and it is preferable to perform the computations on a sparse skeleton
of the given graph that roughly preserves the shortest paths information. Spanners
and emulators serve this purpose. Unfortunately, very little is known about dynamically
maintaining sparse spanners and emulators as the graph is modified by a sequence
of edge insertions and deletions. This paper develops fast dynamic algorithms
for spanner and emulator maintenance and provides evidence from fine-grained complexity
that these algorithms are tight. For unweighted undirected m-edge n-node graphs
we obtain the following results.\r\n\r\nUnder the popular OMv conjecture, there
can be no decremental or incremental algorithm that maintains an n1+o(1) edge
(purely additive) +nδ-emulator for any δ < 1/2 with arbitrary polynomial preprocessing
time and total update time m1+o(1). Also, under the Combinatorial k-Clique hypothesis,
any fully dynamic combinatorial algorithm that maintains an n1+o(1) edge (1 +
∊, no(1))-spanner or emulator for small ∊ must either have preprocessing time
mn1–o(1) or amortized update time m1–o(1). Both of our conditional lower bounds
are tight.\r\n\r\nAs the above fully dynamic lower bound only applies to combinatorial
algorithms, we also develop an algebraic spanner algorithm that improves over
the m1–o(1) update time for dense graphs. For any constant ∊ ∊ (0, 1], there is
a fully dynamic algorithm with worst-case update time O(n1.529) that whp maintains
an n1+o(1) edge (1 + ∊, no(1))-spanner.\r\n\r\nOur new algebraic techniques allow
us to also obtain a new fully dynamic algorithm for All-Pairs Shortest Paths (APSP)
that can perform both edge updates and can report shortest paths in worst-case
time O(n1.9), which are correct whp. This is the first path-reporting fully dynamic
APSP algorithm with a truly subquadratic query time that beats O(n2.5) update
time. It works against an oblivious adversary.\r\n\r\nFinally, we give two applications
of our new dynamic spanner algorithms: (1) a fully dynamic (1 + ∊)-approximate
APSP algorithm with update time O(n1.529) that can report approximate shortest
paths in n1+o(1) time per query; previous subquadratic update/query algorithms
could only report the distance, but not obtain the paths; (2) a fully dynamic
algorithm for near-2-approximate Steiner tree maintenance with both terminal and
edge updates."
article_processing_charge: No
arxiv: 1
author:
- first_name: Thiago
full_name: Bergamaschi, Thiago
last_name: Bergamaschi
- 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: Maximilian Probst
full_name: Gutenberg, Maximilian Probst
last_name: Gutenberg
- first_name: Virginia Vassilevska
full_name: Williams, Virginia Vassilevska
last_name: Williams
- first_name: Nicole
full_name: Wein, Nicole
last_name: Wein
citation:
ama: 'Bergamaschi T, Henzinger MH, Gutenberg MP, Williams VV, Wein N. New techniques
and fine-grained hardness for dynamic near-additive spanners. In: 32nd Annual
ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied
Mathematics; 2021:1836-1855. doi:10.1137/1.9781611976465.110'
apa: 'Bergamaschi, T., Henzinger, M. H., Gutenberg, M. P., Williams, V. V., &
Wein, N. (2021). New techniques and fine-grained hardness for dynamic near-additive
spanners. In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (pp.
1836–1855). Alexandria, VA, United States: Society for Industrial and Applied
Mathematics. https://doi.org/10.1137/1.9781611976465.110'
chicago: Bergamaschi, Thiago, Monika H Henzinger, Maximilian Probst Gutenberg, Virginia
Vassilevska Williams, and Nicole Wein. “New Techniques and Fine-Grained Hardness
for Dynamic near-Additive Spanners.” In 32nd Annual ACM-SIAM Symposium on Discrete
Algorithms, 1836–55. Society for Industrial and Applied Mathematics, 2021.
https://doi.org/10.1137/1.9781611976465.110.
ieee: T. Bergamaschi, M. H. Henzinger, M. P. Gutenberg, V. V. Williams, and N. Wein,
“New techniques and fine-grained hardness for dynamic near-additive spanners,”
in 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA,
United States, 2021, pp. 1836–1855.
ista: 'Bergamaschi T, Henzinger MH, Gutenberg MP, Williams VV, Wein N. 2021. New
techniques and fine-grained hardness for dynamic near-additive spanners. 32nd
Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete
Algorithms, 1836–1855.'
mla: Bergamaschi, Thiago, et al. “New Techniques and Fine-Grained Hardness for Dynamic
near-Additive Spanners.” 32nd Annual ACM-SIAM Symposium on Discrete Algorithms,
Society for Industrial and Applied Mathematics, 2021, pp. 1836–55, doi:10.1137/1.9781611976465.110.
short: T. Bergamaschi, M.H. Henzinger, M.P. Gutenberg, V.V. Williams, N. Wein, in:,
32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial
and Applied Mathematics, 2021, pp. 1836–1855.
conference:
end_date: 2021-01-13
location: Alexandria, VA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2021-01-10
date_created: 2022-08-18T07:37:36Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2023-02-17T11:28:46Z
day: '01'
doi: 10.1137/1.9781611976465.110
extern: '1'
external_id:
arxiv:
- '2010.10134'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2010.10134
month: '01'
oa: 1
oa_version: Preprint
page: 1836-1855
publication: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- 978-1-61197-646-5
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: New techniques and fine-grained hardness for dynamic near-additive spanners
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '11920'
abstract:
- lang: eng
text: 'In the dynamic minimum set cover problem, a challenge is to minimize the
update time while guaranteeing close to the optimal min(O(log n), f) approximation
factor. (Throughout, m, n, f, and C are parameters denoting the maximum number
of sets, number of elements, frequency, and the cost range.) In the high-frequency
range, when f = Ω(log n), this was achieved by a deterministic O(log n)-approximation
algorithm with O(f log n) amortized update time [Gupta et al. STOC''17]. In the
low-frequency range, the line of work by Gupta et al. [STOC''17], Abboud et al.
[STOC''19], and Bhattacharya et al. [ICALP''15, IPCO''17, FOCS''19] led to a deterministic
(1 + ∊) f-approximation algorithm with O(f log(Cn)/∊2) amortized update time.
In this paper we improve the latter update time and provide the first bounds that
subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms.
We obtain: (1) (1 + ∊) f-approximation ratio in O(f log2(Cn)/∊3) worst-case update
time: No non-trivial worst-case update time was previously known for dynamic set
cover. Our bound subsumes and improves by a logarithmic factor the O(log3 n/poly(∊))
worst-case update time for unweighted dynamic vertex cover (i.e., when f = 2 and
C = 1) by Bhattacharya et al. [SODA''17]. (2) (1 + ∊) f-approximation ratio in
O ((f2/∊3) + (f/∊2) log C) amortized update time: This result improves the previous
O(f log (Cn)/∊2) update time bound for most values of f in the low-frequency range,
i.e. whenever f = o(log n). It is the first that is independent of m and n. It
subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA''19]
for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). These results
are achieved by leveraging the approximate complementary slackness and background
schedulers techniques. These techniques were used in the local update scheme for
dynamic vertex cover. Our main technical contribution is to adapt these techniques
within the global update scheme of Bhattacharya et al. [FOCS''19] for the dynamic
set cover problem.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- 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: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
- first_name: Xiaowei
full_name: Wu, Xiaowei
last_name: Wu
citation:
ama: 'Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. Dynamic set cover: Improved
amortized and worst-case update time. In: 32nd Annual ACM-SIAM Symposium on
Discrete Algorithms. Society for Industrial and Applied Mathematics; 2021:2537-2549.
doi:10.1137/1.9781611976465.150'
apa: 'Bhattacharya, S., Henzinger, M. H., Nanongkai, D., & Wu, X. (2021). Dynamic
set cover: Improved amortized and worst-case update time. In 32nd Annual ACM-SIAM
Symposium on Discrete Algorithms (pp. 2537–2549). Alexandria, VA, United States:
Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611976465.150'
chicago: 'Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Xiaowei
Wu. “Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.” In 32nd
Annual ACM-SIAM Symposium on Discrete Algorithms, 2537–49. Society for Industrial
and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976465.150.'
ieee: 'S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and X. Wu, “Dynamic set cover:
Improved amortized and worst-case update time,” in 32nd Annual ACM-SIAM Symposium
on Discrete Algorithms, Alexandria, VA, United States, 2021, pp. 2537–2549.'
ista: 'Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. 2021. Dynamic set cover:
Improved amortized and worst-case update time. 32nd Annual ACM-SIAM Symposium
on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2537–2549.'
mla: 'Bhattacharya, Sayan, et al. “Dynamic Set Cover: Improved Amortized and Worst-Case
Update Time.” 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society
for Industrial and Applied Mathematics, 2021, pp. 2537–49, doi:10.1137/1.9781611976465.150.'
short: S. Bhattacharya, M.H. Henzinger, D. Nanongkai, X. Wu, in:, 32nd Annual ACM-SIAM
Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,
2021, pp. 2537–2549.
conference:
end_date: 2021-01-13
location: Alexandria, VA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2021-01-10
date_created: 2022-08-18T07:46:54Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2023-02-17T11:31:22Z
day: '01'
doi: 10.1137/1.9781611976465.150
extern: '1'
external_id:
arxiv:
- '2002.11171'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2002.11171
month: '01'
oa: 1
oa_version: Preprint
page: 2537-2549
publication: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- 978-1-61197-646-5
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Dynamic set cover: Improved amortized and worst-case update time'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...