---
_id: '1162'
abstract:
- lang: eng
text: Selected universal experimental properties of high-temperature superconducting
(HTS) cuprates have been singled out in the last decade. One of the pivotal challenges
in this field is the designation of a consistent interpretation framework within
which we can describe quantitatively the universal features of those systems.
Here we analyze in a detailed manner the principal experimental data and compare
them quantitatively with the approach based on a single-band model of strongly
correlated electrons supplemented with strong antiferromagnetic (super)exchange
interaction (the so-called t−J−U model). The model rationale is provided by estimating
its microscopic parameters on the basis of the three-band approach for the Cu-O
plane. We use our original full Gutzwiller wave-function solution by going beyond
the renormalized mean-field theory (RMFT) in a systematic manner. Our approach
reproduces very well the observed hole doping (δ) dependence of the kinetic-energy
gain in the superconducting phase, one of the principal non-Bardeen-Cooper-Schrieffer
features of the cuprates. The calculated Fermi velocity in the nodal direction
is practically δ-independent and its universal value agrees very well with that
determined experimentally. Also, a weak doping dependence of the Fermi wave vector
leads to an almost constant value of the effective mass in a pure superconducting
phase which is both observed in experiment and reproduced within our approach.
An assessment of the currently used models (t−J, Hubbard) is carried out and the
results of the canonical RMFT as a zeroth-order solution are provided for comparison
to illustrate the necessity of the introduced higher-order contributions.
article_number: '024506'
article_processing_charge: No
arxiv: 1
author:
- first_name: Jozef
full_name: Spałek, Jozef
last_name: Spałek
- first_name: Michał
full_name: Zegrodnik, Michał
last_name: Zegrodnik
- first_name: Jan
full_name: Kaczmarczyk, Jan
id: 46C405DE-F248-11E8-B48F-1D18A9856A87
last_name: Kaczmarczyk
orcid: 0000-0002-1629-3675
citation:
ama: Spałek J, Zegrodnik M, Kaczmarczyk J. Universal properties of high temperature
superconductors from real space pairing t-J-U model and its quantitative comparison
with experiment. Physical Review B - Condensed Matter and Materials Physics.
2017;95(2). doi:10.1103/PhysRevB.95.024506
apa: Spałek, J., Zegrodnik, M., & Kaczmarczyk, J. (2017). Universal properties
of high temperature superconductors from real space pairing t-J-U model and its
quantitative comparison with experiment. Physical Review B - Condensed Matter
and Materials Physics. American Physical Society. https://doi.org/10.1103/PhysRevB.95.024506
chicago: Spałek, Jozef, Michał Zegrodnik, and Jan Kaczmarczyk. “Universal Properties
of High Temperature Superconductors from Real Space Pairing T-J-U Model and Its
Quantitative Comparison with Experiment.” Physical Review B - Condensed Matter
and Materials Physics. American Physical Society, 2017. https://doi.org/10.1103/PhysRevB.95.024506.
ieee: J. Spałek, M. Zegrodnik, and J. Kaczmarczyk, “Universal properties of high
temperature superconductors from real space pairing t-J-U model and its quantitative
comparison with experiment,” Physical Review B - Condensed Matter and Materials
Physics, vol. 95, no. 2. American Physical Society, 2017.
ista: Spałek J, Zegrodnik M, Kaczmarczyk J. 2017. Universal properties of high temperature
superconductors from real space pairing t-J-U model and its quantitative comparison
with experiment. Physical Review B - Condensed Matter and Materials Physics. 95(2),
024506.
mla: Spałek, Jozef, et al. “Universal Properties of High Temperature Superconductors
from Real Space Pairing T-J-U Model and Its Quantitative Comparison with Experiment.”
Physical Review B - Condensed Matter and Materials Physics, vol. 95, no.
2, 024506, American Physical Society, 2017, doi:10.1103/PhysRevB.95.024506.
short: J. Spałek, M. Zegrodnik, J. Kaczmarczyk, Physical Review B - Condensed Matter
and Materials Physics 95 (2017).
date_created: 2018-12-11T11:50:29Z
date_published: 2017-01-13T00:00:00Z
date_updated: 2025-06-04T08:39:41Z
day: '13'
department:
- _id: MiLe
doi: 10.1103/PhysRevB.95.024506
ec_funded: 1
external_id:
arxiv:
- '1606.03247'
isi:
- '000391852800006'
intvolume: ' 95'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1606.03247
month: '01'
oa: 1
oa_version: Submitted Version
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Physical Review B - Condensed Matter and Materials Physics
publication_identifier:
issn:
- 2469-9950
publication_status: published
publisher: American Physical Society
publist_id: '6195'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Universal properties of high temperature superconductors from real space pairing
t-J-U model and its quantitative comparison with experiment
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 95
year: '2017'
...
---
_id: '11633'
abstract:
- lang: eng
text: Our understanding of stars through asteroseismic data analysis is limited
by our ability to take advantage of the huge amount of observed stars provided
by space missions such as CoRoT, Kepler , K2, and soon TESS and PLATO. Global
seismic pipelines provide global stellar parameters such as mass and radius using
the mean seismic parameters, as well as the effective temperature. These pipelines
are commonly used automatically on thousands of stars observed by K2 for 3 months
(and soon TESS for at least ∼ 1 month). However, pipelines are not immune from
misidentifying noise peaks and stellar oscillations. Therefore, new validation
techniques are required to assess the quality of these results. We present a new
metric called FliPer (Flicker in Power), which takes into account the average
variability at all measured time scales. The proper calibration of FliPer enables
us to obtain good estimations of global stellar parameters such as surface gravity
that are robust against the influence of noise peaks and hence are an excellent
way to find faults in asteroseismic pipelines.
article_number: '1711.02890'
article_processing_charge: No
arxiv: 1
author:
- first_name: Lisa Annabelle
full_name: Bugnet, Lisa Annabelle
id: d9edb345-f866-11ec-9b37-d119b5234501
last_name: Bugnet
orcid: 0000-0003-0142-4000
- first_name: R. A.
full_name: Garcia, R. A.
last_name: Garcia
- first_name: G. R.
full_name: Davies, G. R.
last_name: Davies
- first_name: S.
full_name: Mathur, S.
last_name: Mathur
- first_name: E.
full_name: Corsaro, E.
last_name: Corsaro
citation:
ama: 'Bugnet LA, Garcia RA, Davies GR, Mathur S, Corsaro E. FliPer: Checking the
reliability of global seismic parameters from automatic pipelines. arXiv.
doi:10.48550/arXiv.1711.02890'
apa: 'Bugnet, L. A., Garcia, R. A., Davies, G. R., Mathur, S., & Corsaro, E.
(n.d.). FliPer: Checking the reliability of global seismic parameters from automatic
pipelines. arXiv. https://doi.org/10.48550/arXiv.1711.02890'
chicago: 'Bugnet, Lisa Annabelle, R. A. Garcia, G. R. Davies, S. Mathur, and E.
Corsaro. “FliPer: Checking the Reliability of Global Seismic Parameters from Automatic
Pipelines.” ArXiv, n.d. https://doi.org/10.48550/arXiv.1711.02890.'
ieee: 'L. A. Bugnet, R. A. Garcia, G. R. Davies, S. Mathur, and E. Corsaro, “FliPer:
Checking the reliability of global seismic parameters from automatic pipelines,”
arXiv. .'
ista: 'Bugnet LA, Garcia RA, Davies GR, Mathur S, Corsaro E. FliPer: Checking the
reliability of global seismic parameters from automatic pipelines. arXiv, 1711.02890.'
mla: 'Bugnet, Lisa Annabelle, et al. “FliPer: Checking the Reliability of Global
Seismic Parameters from Automatic Pipelines.” ArXiv, 1711.02890, doi:10.48550/arXiv.1711.02890.'
short: L.A. Bugnet, R.A. Garcia, G.R. Davies, S. Mathur, E. Corsaro, ArXiv (n.d.).
date_created: 2022-07-21T07:13:13Z
date_published: 2017-11-08T00:00:00Z
date_updated: 2022-08-22T08:45:42Z
day: '08'
doi: 10.48550/arXiv.1711.02890
extern: '1'
external_id:
arxiv:
- '1711.02890'
keyword:
- asteroseismology - methods
- data analysis - stars
- oscillations
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1711.02890
month: '11'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: submitted
status: public
title: 'FliPer: Checking the reliability of global seismic parameters from automatic
pipelines'
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '11651'
abstract:
- lang: eng
text: Diffusions and related random walk procedures are of central importance in
many areas of machine learning, data analysis, and applied mathematics. Because
they spread mass agnostically at each step in an iterative manner, they can sometimes
spread mass “too aggressively,” thereby failing to find the “right” clusters.
We introduce a novel Capacity Releasing Diffusion (CRD) Process, which is both
faster and stays more local than the classical spectral diffusion process. As
an application, we use our CRD Process to develop an improved local algorithm
for graph clustering. Our local graph clustering method can find local clusters
in a model of clustering where one begins the CRD Process in a cluster whose vertices
are connected better internally than externally by an O(log2n) factor, where n
is the number of nodes in the cluster. Thus, our CRD Process is the first local
graph clustering algorithm that is not subject to the well-known quadratic Cheeger
barrier. Our result requires a certain smoothness condition, which we expect to
be an artifact of our analysis. Our empirical evaluation demonstrates improved
results, in particular for realistic social graphs where there are moderately
good—but not very good—clusters.
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Di
full_name: Wang, Di
last_name: Wang
- first_name: Kimon
full_name: Fountoulakis, Kimon
last_name: Fountoulakis
- 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: Michael W.
full_name: Mahoney, Michael W.
last_name: Mahoney
- first_name: ' Satish'
full_name: Rao , Satish
last_name: 'Rao '
citation:
ama: 'Wang D, Fountoulakis K, Henzinger M, Mahoney MW, Rao Satish. Capacity releasing
diffusion for speed and locality. In: Proceedings of the 34th International
Conference on Machine Learning. Vol 70. ML Research Press; 2017:3598-3607.'
apa: 'Wang, D., Fountoulakis, K., Henzinger, M., Mahoney, M. W., & Rao , Satish.
(2017). Capacity releasing diffusion for speed and locality. In Proceedings
of the 34th International Conference on Machine Learning (Vol. 70, pp. 3598–3607).
Sydney, Australia: ML Research Press.'
chicago: Wang, Di, Kimon Fountoulakis, Monika Henzinger, Michael W. Mahoney, and Satish
Rao . “Capacity Releasing Diffusion for Speed and Locality.” In Proceedings
of the 34th International Conference on Machine Learning, 70:3598–3607. ML
Research Press, 2017.
ieee: D. Wang, K. Fountoulakis, M. Henzinger, M. W. Mahoney, and Satish Rao , “Capacity
releasing diffusion for speed and locality,” in Proceedings of the 34th International
Conference on Machine Learning, Sydney, Australia, 2017, vol. 70, pp. 3598–3607.
ista: Wang D, Fountoulakis K, Henzinger M, Mahoney MW, Rao Satish. 2017. Capacity
releasing diffusion for speed and locality. Proceedings of the 34th International
Conference on Machine Learning. International Conference on Machine Learning,
PMLR, vol. 70, 3598–3607.
mla: Wang, Di, et al. “Capacity Releasing Diffusion for Speed and Locality.” Proceedings
of the 34th International Conference on Machine Learning, vol. 70, ML Research
Press, 2017, pp. 3598–607.
short: D. Wang, K. Fountoulakis, M. Henzinger, M.W. Mahoney, Satish Rao , in:,
Proceedings of the 34th International Conference on Machine Learning, ML Research
Press, 2017, pp. 3598–3607.
conference:
end_date: 2017-08-11
location: Sydney, Australia
name: International Conference on Machine Learning
start_date: 2017-08-06
date_created: 2022-07-25T13:59:21Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2024-11-06T12:04:59Z
day: '01'
extern: '1'
external_id:
arxiv:
- '1706.05826'
intvolume: ' 70'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://proceedings.mlr.press/v70/wang17b/wang17b.pdf
month: '09'
oa: 1
oa_version: Published Version
page: 3598-3607
publication: Proceedings of the 34th International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
status: public
title: Capacity releasing diffusion for speed and locality
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 70
year: '2017'
...
---
_id: '11665'
abstract:
- lang: eng
text: "We study the problem of maintaining a breadth-first spanning tree (BFS tree)
in partially dynamic distributed networks modeling a sequence of either failures
or additions of communication links (but not both). We present deterministic (1+ϵ)-approximation
algorithms whose amortized time (over some number of link changes) is sublinear
in D, the maximum diameter of the network.\r\n\r\nOur technique also leads to
a deterministic (1+ϵ)-approximate incremental algorithm for single-source shortest
paths in the sequential (usual RAM) model. Prior to our work, the state of the
art was the classic exact algorithm of Even and Shiloach (1981), which is optimal
under some assumptions (Roditty and Zwick 2011; Henzinger et al. 2015). Our result
is the first to show that, in the incremental setting, this bound can be beaten
in certain cases if some approximation is allowed."
acknowledgement: "We thank the reviewers of ICALP 2013 for pointing to related articles
and to an error in an example\r\ngiven in a previous version of this article. We
also thank one of the reviewers of Transactions on\r\nAlgorithms for very detailed
comments."
article_number: '51'
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 M, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first
spanning trees in partially dynamic networks. ACM Transactions on Algorithms.
2017;13(4). doi:10.1145/3146550
apa: Henzinger, M., Krinninger, S., & Nanongkai, D. (2017). Sublinear-time maintenance
of breadth-first spanning trees in partially dynamic networks. ACM Transactions
on Algorithms. Association for Computing Machinery. https://doi.org/10.1145/3146550
chicago: Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time
Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.” ACM
Transactions on Algorithms. Association for Computing Machinery, 2017. https://doi.org/10.1145/3146550.
ieee: M. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance
of breadth-first spanning trees in partially dynamic networks,” ACM Transactions
on Algorithms, vol. 13, no. 4. Association for Computing Machinery, 2017.
ista: Henzinger M, Krinninger S, Nanongkai D. 2017. Sublinear-time maintenance of
breadth-first spanning trees in partially dynamic networks. ACM Transactions on
Algorithms. 13(4), 51.
mla: Henzinger, Monika, et al. “Sublinear-Time Maintenance of Breadth-First Spanning
Trees in Partially Dynamic Networks.” ACM Transactions on Algorithms, vol.
13, no. 4, 51, Association for Computing Machinery, 2017, doi:10.1145/3146550.
short: M. Henzinger, S. Krinninger, D. Nanongkai, ACM Transactions on Algorithms
13 (2017).
date_created: 2022-07-27T11:37:23Z
date_published: 2017-10-01T00:00:00Z
date_updated: 2024-11-06T12:06:03Z
day: '01'
doi: 10.1145/3146550
extern: '1'
external_id:
arxiv:
- '1512.08147'
intvolume: ' 13'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1512.08147
month: '10'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sublinear-time maintenance of breadth-first spanning trees in partially dynamic
networks
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2017'
...
---
_id: '11676'
abstract:
- lang: eng
text: We study the problem of maximizing a monotone submodular function with viability
constraints. This problem originates from computational biology, where we are
given a phylogenetic tree over a set of species and a directed graph, the so-called
food web, encoding viability constraints between these species. These food webs
usually have constant depth. The goal is to select a subset of k species that
satisfies the viability constraints and has maximal phylogenetic diversity. As
this problem is known to be NP-hard, we investigate approximation algorithms.
We present the first constant factor approximation algorithm if the depth is constant.
Its approximation ratio is (1−1e√). This algorithm not only applies to phylogenetic
trees with viability constraints but for arbitrary monotone submodular set functions
with viability constraints. Second, we show that there is no (1−1/e+ϵ)-approximation
algorithm for our problem setting (even for additive functions) and that there
is no approximation algorithm for a slight extension of this setting.
acknowledgement: "The research leading to these results has received funding from
the European Research\r\nCouncil under the European Union’s Seventh Framework Programme
(FP/2007-2013)/ERC Grant Agreement No. 340506."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Wolfgang
full_name: Dvořák, Wolfgang
last_name: Dvořák
- 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: David P.
full_name: Williamson, David P.
last_name: Williamson
citation:
ama: Dvořák W, Henzinger M, Williamson DP. Maximizing a submodular function with
viability constraints. Algorithmica. 2017;77(1):152-172. doi:10.1007/s00453-015-0066-y
apa: Dvořák, W., Henzinger, M., & Williamson, D. P. (2017). Maximizing a submodular
function with viability constraints. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-015-0066-y
chicago: Dvořák, Wolfgang, Monika Henzinger, and David P. Williamson. “Maximizing
a Submodular Function with Viability Constraints.” Algorithmica. Springer
Nature, 2017. https://doi.org/10.1007/s00453-015-0066-y.
ieee: W. Dvořák, M. Henzinger, and D. P. Williamson, “Maximizing a submodular function
with viability constraints,” Algorithmica, vol. 77, no. 1. Springer Nature,
pp. 152–172, 2017.
ista: Dvořák W, Henzinger M, Williamson DP. 2017. Maximizing a submodular function
with viability constraints. Algorithmica. 77(1), 152–172.
mla: Dvořák, Wolfgang, et al. “Maximizing a Submodular Function with Viability Constraints.”
Algorithmica, vol. 77, no. 1, Springer Nature, 2017, pp. 152–72, doi:10.1007/s00453-015-0066-y.
short: W. Dvořák, M. Henzinger, D.P. Williamson, Algorithmica 77 (2017) 152–172.
date_created: 2022-07-27T14:37:24Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2024-11-06T12:07:55Z
day: '01'
doi: 10.1007/s00453-015-0066-y
extern: '1'
external_id:
arxiv:
- '1611.05753'
intvolume: ' 77'
issue: '1'
keyword:
- Approximation algorithms
- Submodular functions
- Phylogenetic diversity
- Viability constraints
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1611.05753
month: '01'
oa: 1
oa_version: Preprint
page: 152-172
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Maximizing a submodular function with viability constraints
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 77
year: '2017'
...
---
_id: '1168'
abstract:
- lang: eng
text: Optimum experimental design theory has recently been extended for parameter
estimation in copula models. The use of these models allows one to gain in flexibility
by considering the model parameter set split into marginal and dependence parameters.
However, this separation also leads to the natural issue of estimating only a
subset of all model parameters. In this work, we treat this problem with the application
of the (Formula presented.)-optimality to copula models. First, we provide an
extension of the corresponding equivalence theory. Then, we analyze a wide range
of flexible copula models to highlight the usefulness of (Formula presented.)-optimality
in many possible scenarios. Finally, we discuss how the usage of the introduced
design criterion also relates to the more general issue of copula selection and
optimal design for model discrimination.
acknowledgement: 'This work has been supported by the project ANR-2011-IS01-001-01
“DESIRE” and Austrian Science Fund (FWF) I833-N18. Open access funding is provided
by the Austrian Science Fund (FWF). '
article_processing_charge: No
author:
- first_name: Elisa
full_name: Perrone, Elisa
id: 2A5F8724-F248-11E8-B48F-1D18A9856A87
last_name: Perrone
orcid: 0000-0003-0370-9835
- first_name: Andreas
full_name: Rappold, Andreas
last_name: Rappold
- first_name: Werner
full_name: Müller, Werner
last_name: Müller
citation:
ama: Perrone E, Rappold A, Müller W. D inf s optimality in copula models. Statistical
Methods and Applications. 2017;26(3):403-418. doi:10.1007/s10260-016-0375-6
apa: Perrone, E., Rappold, A., & Müller, W. (2017). D inf s optimality in copula
models. Statistical Methods and Applications. Springer. https://doi.org/10.1007/s10260-016-0375-6
chicago: Perrone, Elisa, Andreas Rappold, and Werner Müller. “D Inf s Optimality
in Copula Models.” Statistical Methods and Applications. Springer, 2017.
https://doi.org/10.1007/s10260-016-0375-6.
ieee: E. Perrone, A. Rappold, and W. Müller, “D inf s optimality in copula models,”
Statistical Methods and Applications, vol. 26, no. 3. Springer, pp. 403–418,
2017.
ista: Perrone E, Rappold A, Müller W. 2017. D inf s optimality in copula models.
Statistical Methods and Applications. 26(3), 403–418.
mla: Perrone, Elisa, et al. “D Inf s Optimality in Copula Models.” Statistical
Methods and Applications, vol. 26, no. 3, Springer, 2017, pp. 403–18, doi:10.1007/s10260-016-0375-6.
short: E. Perrone, A. Rappold, W. Müller, Statistical Methods and Applications 26
(2017) 403–418.
corr_author: '1'
date_created: 2018-12-11T11:50:31Z
date_published: 2017-08-01T00:00:00Z
date_updated: 2024-10-09T20:57:17Z
day: '01'
ddc:
- '519'
department:
- _id: CaUh
doi: 10.1007/s10260-016-0375-6
external_id:
isi:
- '000407973200004'
file:
- access_level: open_access
checksum: 0b2d1b647ca96e9ef13a14b8b6775e0f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:13Z
date_updated: 2020-07-14T12:44:37Z
file_id: '5199'
file_name: IST-2017-739-v1+2_10260_2016_375_MOESM1_ESM.pdf
file_size: 56664
relation: main_file
- access_level: open_access
checksum: 3321ef34e02e28acfc427f77cf32812a
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:14Z
date_updated: 2020-07-14T12:44:37Z
file_id: '5200'
file_name: IST-2017-739-v1+3_s10260-016-0375-6.pdf
file_size: 688953
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 26'
isi: 1
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '08'
oa: 1
oa_version: Submitted Version
page: 403 - 418
publication: Statistical Methods and Applications
publication_status: published
publisher: Springer
publist_id: '6189'
pubrep_id: '739'
quality_controlled: '1'
scopus_import: '1'
status: public
title: D inf s optimality in copula models
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 26
year: '2017'
...
---
_id: '1169'
abstract:
- lang: eng
text: Dispersal is a crucial factor in natural evolution, since it determines the
habitat experienced by any population and defines the spatial scale of interactions
between individuals. There is compelling evidence for systematic differences in
dispersal characteristics within the same population, i.e., genotype-dependent
dispersal. The consequences of genotype-dependent dispersal on other evolutionary
phenomena, however, are poorly understood. In this article we investigate the
effect of genotype-dependent dispersal on spatial gene frequency patterns, using
a generalization of the classical diffusion model of selection and dispersal.
Dispersal is characterized by the variance of dispersal (diffusion coefficient)
and the mean displacement (directional advection term). We demonstrate that genotype-dependent
dispersal may change the qualitative behavior of Fisher waves, which change from
being “pulled” to being “pushed” wave fronts as the discrepancy in dispersal between
genotypes increases. The speed of any wave is partitioned into components due
to selection, genotype-dependent variance of dispersal, and genotype-dependent
mean displacement. We apply our findings to wave fronts maintained by selection
against heterozygotes. Furthermore, we identify a benefit of increased variance
of dispersal, quantify its effect on the speed of the wave, and discuss the implications
for the evolution of dispersal strategies.
article_processing_charge: No
author:
- first_name: Sebastian
full_name: Novak, Sebastian
id: 461468AE-F248-11E8-B48F-1D18A9856A87
last_name: Novak
orcid: 0000-0002-2519-824X
- first_name: Richard
full_name: Kollár, Richard
last_name: Kollár
citation:
ama: Novak S, Kollár R. Spatial gene frequency waves under genotype dependent dispersal.
Genetics. 2017;205(1):367-374. doi:10.1534/genetics.116.193946
apa: Novak, S., & Kollár, R. (2017). Spatial gene frequency waves under genotype
dependent dispersal. Genetics. Genetics Society of America. https://doi.org/10.1534/genetics.116.193946
chicago: Novak, Sebastian, and Richard Kollár. “Spatial Gene Frequency Waves under
Genotype Dependent Dispersal.” Genetics. Genetics Society of America, 2017.
https://doi.org/10.1534/genetics.116.193946.
ieee: S. Novak and R. Kollár, “Spatial gene frequency waves under genotype dependent
dispersal,” Genetics, vol. 205, no. 1. Genetics Society of America, pp.
367–374, 2017.
ista: Novak S, Kollár R. 2017. Spatial gene frequency waves under genotype dependent
dispersal. Genetics. 205(1), 367–374.
mla: Novak, Sebastian, and Richard Kollár. “Spatial Gene Frequency Waves under Genotype
Dependent Dispersal.” Genetics, vol. 205, no. 1, Genetics Society of America,
2017, pp. 367–74, doi:10.1534/genetics.116.193946.
short: S. Novak, R. Kollár, Genetics 205 (2017) 367–374.
date_created: 2018-12-11T11:50:31Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2025-07-10T11:50:13Z
day: '01'
ddc:
- '576'
department:
- _id: NiBa
doi: 10.1534/genetics.116.193946
ec_funded: 1
external_id:
isi:
- '000393677300025'
file:
- access_level: open_access
checksum: 7c8ab79cda1f92760bbbbe0f53175bfc
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:43Z
date_updated: 2020-07-14T12:44:37Z
file_id: '4833'
file_name: IST-2016-727-v1+1_SFC_Genetics_final.pdf
file_size: 361500
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 205'
isi: 1
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 367 - 374
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Genetics
publication_identifier:
issn:
- 0016-6731
publication_status: published
publisher: Genetics Society of America
publist_id: '6188'
pubrep_id: '727'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Spatial gene frequency waves under genotype dependent dispersal
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 205
year: '2017'
...
---
_id: '1173'
abstract:
- lang: eng
text: We introduce the Voronoi functional of a triangulation of a finite set of
points in the Euclidean plane and prove that among all geometric triangulations
of the point set, the Delaunay triangulation maximizes the functional. This result
neither extends to topological triangulations in the plane nor to geometric triangulations
in three and higher dimensions.
acknowledgement: This research is partially supported by the Russian Government under
the Mega Project 11.G34.31.0053, by the Toposys project FP7-ICT-318493-STREP, by
ESF under the ACAT Research Network Programme, by RFBR grant 11-01-00735, and by
NSF grants DMS-1101688, DMS-1400876.
article_processing_charge: No
arxiv: 1
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Alexey
full_name: Glazyrin, Alexey
last_name: Glazyrin
- first_name: Oleg
full_name: Musin, Oleg
last_name: Musin
- first_name: Anton
full_name: Nikitenko, Anton
id: 3E4FF1BA-F248-11E8-B48F-1D18A9856A87
last_name: Nikitenko
orcid: 0000-0002-0659-3201
citation:
ama: Edelsbrunner H, Glazyrin A, Musin O, Nikitenko A. The Voronoi functional is
maximized by the Delaunay triangulation in the plane. Combinatorica. 2017;37(5):887-910.
doi:10.1007/s00493-016-3308-y
apa: Edelsbrunner, H., Glazyrin, A., Musin, O., & Nikitenko, A. (2017). The
Voronoi functional is maximized by the Delaunay triangulation in the plane. Combinatorica.
Springer. https://doi.org/10.1007/s00493-016-3308-y
chicago: Edelsbrunner, Herbert, Alexey Glazyrin, Oleg Musin, and Anton Nikitenko.
“The Voronoi Functional Is Maximized by the Delaunay Triangulation in the Plane.”
Combinatorica. Springer, 2017. https://doi.org/10.1007/s00493-016-3308-y.
ieee: H. Edelsbrunner, A. Glazyrin, O. Musin, and A. Nikitenko, “The Voronoi functional
is maximized by the Delaunay triangulation in the plane,” Combinatorica,
vol. 37, no. 5. Springer, pp. 887–910, 2017.
ista: Edelsbrunner H, Glazyrin A, Musin O, Nikitenko A. 2017. The Voronoi functional
is maximized by the Delaunay triangulation in the plane. Combinatorica. 37(5),
887–910.
mla: Edelsbrunner, Herbert, et al. “The Voronoi Functional Is Maximized by the Delaunay
Triangulation in the Plane.” Combinatorica, vol. 37, no. 5, Springer, 2017,
pp. 887–910, doi:10.1007/s00493-016-3308-y.
short: H. Edelsbrunner, A. Glazyrin, O. Musin, A. Nikitenko, Combinatorica 37 (2017)
887–910.
date_created: 2018-12-11T11:50:32Z
date_published: 2017-10-01T00:00:00Z
date_updated: 2025-06-04T08:44:44Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s00493-016-3308-y
ec_funded: 1
external_id:
arxiv:
- '1411.6337'
isi:
- '000418056000005'
intvolume: ' 37'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1411.6337
month: '10'
oa: 1
oa_version: Submitted Version
page: 887 - 910
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Combinatorica
publication_identifier:
issn:
- 0209-9683
publication_status: published
publisher: Springer
publist_id: '6182'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Voronoi functional is maximized by the Delaunay triangulation in the plane
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 37
year: '2017'
...
---
_id: '1174'
abstract:
- lang: eng
text: Security of cryptographic applications is typically defined by security games.
The adversary, within certain resources, cannot win with probability much better
than 0 (for unpredictability applications, like one-way functions) or much better
than 1/2 (indistinguishability applications for instance encryption schemes).
In so called squared-friendly applications the winning probability of the adversary,
for different values of the application secret randomness, is not only close to
0 or 1/2 on average, but also concentrated in the sense that its second central
moment is small. The class of squared-friendly applications, which contains all
unpredictability applications and many indistinguishability applications, is particularly
important for key derivation. Barak et al. observed that for square-friendly applications
one can beat the "RT-bound", extracting secure keys with significantly
smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications
one can directly use a "weak" key, which has only high entropy, as a
secure key. In this paper we give sharp lower bounds on square security assuming
security for "weak" keys. We show that any application which is either
(a) secure with weak keys or (b) allows for entropy savings for keys derived by
universal hashing, must be square-friendly. Quantitatively, our lower bounds match
the positive results of Dodis and Yu and Barak et al. (TCC\'13, CRYPTO\'11) Hence,
they can be understood as a general characterization of squared-friendly applications.
While the positive results on squared-friendly applications where derived by one
clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we
need more machinery. In our approach we use convex optimization techniques and
some theory of circular matrices.
alternative_title:
- LIPIcs
article_number: '57'
article_processing_charge: No
author:
- first_name: Maciej
full_name: Skórski, Maciej
id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
last_name: Skórski
citation:
ama: 'Skórski M. Lower bounds on key derivation for square-friendly applications.
In: Vol 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.STACS.2017.57'
apa: 'Skórski, M. (2017). Lower bounds on key derivation for square-friendly applications
(Vol. 66). Presented at the STACS: Symposium on Theoretical Aspects of Computer
Science, Hannover, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.STACS.2017.57'
chicago: Skórski, Maciej. “Lower Bounds on Key Derivation for Square-Friendly Applications,”
Vol. 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.STACS.2017.57.
ieee: 'M. Skórski, “Lower bounds on key derivation for square-friendly applications,”
presented at the STACS: Symposium on Theoretical Aspects of Computer Science,
Hannover, Germany, 2017, vol. 66.'
ista: 'Skórski M. 2017. Lower bounds on key derivation for square-friendly applications.
STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 66,
57.'
mla: Skórski, Maciej. Lower Bounds on Key Derivation for Square-Friendly Applications.
Vol. 66, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.STACS.2017.57.
short: M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-03-11
location: Hannover, Germany
name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
start_date: 2017-03-08
date_created: 2018-12-11T11:50:32Z
date_published: 2017-03-01T00:00:00Z
date_updated: 2025-07-10T11:50:14Z
day: '01'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.STACS.2017.57
ec_funded: 1
external_id:
isi:
- '000521077300057'
intvolume: ' 66'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://drops.dagstuhl.de/opus/volltexte/2017/6976
month: '03'
oa: 1
oa_version: Submitted Version
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6180'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounds on key derivation for square-friendly applications
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 66
year: '2017'
...
---
_id: '1175'
abstract:
- lang: eng
text: We study space complexity and time-space trade-offs with a focus not on peak
memory usage but on overall memory consumption throughout the computation. Such
a cumulative space measure was introduced for the computational model of parallel
black pebbling by [Alwen and Serbinenko ’15] as a tool for obtaining results in
cryptography. We consider instead the non- deterministic black-white pebble game
and prove optimal cumulative space lower bounds and trade-offs, where in order
to minimize pebbling time the space has to remain large during a significant fraction
of the pebbling. We also initiate the study of cumulative space in proof complexity,
an area where other space complexity measures have been extensively studied during
the last 10–15 years. Using and extending the connection between proof complexity
and pebble games in [Ben-Sasson and Nordström ’08, ’11] we obtain several strong
cumulative space results for (even parallel versions of) the resolution proof
system, and outline some possible future directions of study of this, in our opinion,
natural and interesting space measure.
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Susanna
full_name: De Rezende, Susanna
last_name: De Rezende
- first_name: Jakob
full_name: Nordstrom, Jakob
last_name: Nordstrom
- first_name: Marc
full_name: Vinyals, Marc
last_name: Vinyals
citation:
ama: 'Alwen JF, De Rezende S, Nordstrom J, Vinyals M. Cumulative space in black-white
pebbling and resolution. In: Papadimitriou C, ed. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2017:38:1-38-21. doi:10.4230/LIPIcs.ITCS.2017.38'
apa: 'Alwen, J. F., De Rezende, S., Nordstrom, J., & Vinyals, M. (2017). Cumulative
space in black-white pebbling and resolution. In C. Papadimitriou (Ed.) (Vol.
67, p. 38:1-38-21). Presented at the ITCS: Innovations in Theoretical Computer
Science, Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2017.38'
chicago: Alwen, Joel F, Susanna De Rezende, Jakob Nordstrom, and Marc Vinyals. “Cumulative
Space in Black-White Pebbling and Resolution.” edited by Christos Papadimitriou,
67:38:1-38-21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.ITCS.2017.38.
ieee: 'J. F. Alwen, S. De Rezende, J. Nordstrom, and M. Vinyals, “Cumulative space
in black-white pebbling and resolution,” presented at the ITCS: Innovations in
Theoretical Computer Science, Berkeley, CA, United States, 2017, vol. 67, p. 38:1-38-21.'
ista: 'Alwen JF, De Rezende S, Nordstrom J, Vinyals M. 2017. Cumulative space in
black-white pebbling and resolution. ITCS: Innovations in Theoretical Computer
Science, LIPIcs, vol. 67, 38:1-38-21.'
mla: Alwen, Joel F., et al. Cumulative Space in Black-White Pebbling and Resolution.
Edited by Christos Papadimitriou, vol. 67, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017, p. 38:1-38-21, doi:10.4230/LIPIcs.ITCS.2017.38.
short: J.F. Alwen, S. De Rezende, J. Nordstrom, M. Vinyals, in:, C. Papadimitriou
(Ed.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21.
conference:
end_date: 2017-01-11
location: Berkeley, CA, United States
name: 'ITCS: Innovations in Theoretical Computer Science'
start_date: 2017-01-09
corr_author: '1'
date_created: 2018-12-11T11:50:33Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2025-09-10T10:49:13Z
day: '01'
ddc:
- '005'
- '600'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.ITCS.2017.38
editor:
- first_name: Christos
full_name: Papadimitriou, Christos
last_name: Papadimitriou
external_id:
isi:
- '001532708700038'
file:
- access_level: open_access
checksum: dbc94810be07c2fb1945d5c2a6130e6c
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:11Z
date_updated: 2020-07-14T12:44:37Z
file_id: '5263'
file_name: IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf
file_size: 557769
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 67'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 38:1-38-21
publication_identifier:
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6179'
pubrep_id: '927'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Cumulative space in black-white pebbling and resolution
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 67
year: '2017'
...
---
_id: '1176'
abstract:
- lang: eng
text: The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being
considered by the IRTF (Internet Research Task Force) as a new de-facto standard
for password hashing. An older version (Argon2i-A) of the same algorithm was chosen
as the winner of the recent Password Hashing Competition. An important competitor
to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs,
Boneh and Schechter. A key security desiderata for any such algorithm is that
evaluating it (even using a custom device) requires a large amount of memory amortized
across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of
theoretical attacks against Argon2i-A and BH. While these attacks yield large
asymptotic reductions in the amount of memory, it was not, a priori, clear if
(1) they can be extended to the newer Argon2i-B, (2) the attacks are effective
on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3)
if they can be effectively instantiated against any algorithm under realistic
hardware constrains. In this work we answer all three of these questions in the
affirmative for all three algorithms. This is also the first work to analyze the
security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen
and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe
asymptotic deficiencies in its security. Next we introduce several novel heuristics
for improving the attack's concrete memory efficiency even when on-chip memory
bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A,
Argon2i-B and BH instances and measure the resulting memory consumption for various
practical parameter ranges and for a variety of upperbounds on the amount of parallelism
available to the attacker. Finally we describe, implement, and test a new heuristic
for applying the Alwen-Blocki attack to functions employing a technique developed
by Corrigan-Gibs et al. for improving concrete security of memory-hard functions.
We analyze the collected data and show the effects various parameters have on
the memory consumption of the attack. In particular, we can draw several interesting
conclusions about the level of security provided by these functions. · For the
Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must
be instantiated with more than 10 passes on memory - beyond the "paranoid" parameter
setting in the current IRTF proposal. · The technique of Corrigan-Gibs for improving
security can also be overcome by the Alwen-Blocki attack under realistic hardware
constraints. · On a positive note, both the asymptotic and concrete security of
Argon2i-B seem to improve on that of Argon2i-A.
article_number: '7961977'
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Jeremiah
full_name: Blocki, Jeremiah
last_name: Blocki
citation:
ama: 'Alwen JF, Blocki J. Towards practical attacks on Argon2i and balloon hashing.
In: IEEE; 2017. doi:10.1109/EuroSP.2017.47'
apa: 'Alwen, J. F., & Blocki, J. (2017). Towards practical attacks on Argon2i
and balloon hashing. Presented at the EuroS&P: European Symposium on Security
and Privacy, Paris, France: IEEE. https://doi.org/10.1109/EuroSP.2017.47'
chicago: Alwen, Joel F, and Jeremiah Blocki. “Towards Practical Attacks on Argon2i
and Balloon Hashing.” IEEE, 2017. https://doi.org/10.1109/EuroSP.2017.47.
ieee: 'J. F. Alwen and J. Blocki, “Towards practical attacks on Argon2i and balloon
hashing,” presented at the EuroS&P: European Symposium on Security and Privacy,
Paris, France, 2017.'
ista: 'Alwen JF, Blocki J. 2017. Towards practical attacks on Argon2i and balloon
hashing. EuroS&P: European Symposium on Security and Privacy, 7961977.'
mla: Alwen, Joel F., and Jeremiah Blocki. Towards Practical Attacks on Argon2i
and Balloon Hashing. 7961977, IEEE, 2017, doi:10.1109/EuroSP.2017.47.
short: J.F. Alwen, J. Blocki, in:, IEEE, 2017.
conference:
end_date: 2017-04-28
location: Paris, France
name: 'EuroS&P: European Symposium on Security and Privacy'
start_date: 2017-04-26
date_created: 2018-12-11T11:50:33Z
date_published: 2017-07-03T00:00:00Z
date_updated: 2023-09-20T11:22:25Z
day: '03'
department:
- _id: KrPi
doi: 10.1109/EuroSP.2017.47
external_id:
isi:
- '000424197300011'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/759
month: '07'
oa: 1
oa_version: Submitted Version
publication_identifier:
isbn:
- 978-150905761-0
publication_status: published
publisher: IEEE
publist_id: '6178'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Towards practical attacks on Argon2i and balloon hashing
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '11772'
abstract:
- lang: eng
text: A dynamic graph algorithm is a data structure that supports operations on
dynamically changing graphs.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Henzinger M. The state of the art in dynamic graph algorithms. In: 44th
International Conference on Current Trends in Theory and Practice of Computer
Science. Vol 10706. Springer Nature; 2017:40–44. doi:10.1007/978-3-319-73117-9_3'
apa: 'Henzinger, M. (2017). The state of the art in dynamic graph algorithms. In
44th International Conference on Current Trends in Theory and Practice of Computer
Science (Vol. 10706, pp. 40–44). Krems, Austria: Springer Nature. https://doi.org/10.1007/978-3-319-73117-9_3'
chicago: Henzinger, Monika. “The State of the Art in Dynamic Graph Algorithms.”
In 44th International Conference on Current Trends in Theory and Practice of
Computer Science, 10706:40–44. Springer Nature, 2017. https://doi.org/10.1007/978-3-319-73117-9_3.
ieee: M. Henzinger, “The state of the art in dynamic graph algorithms,” in 44th
International Conference on Current Trends in Theory and Practice of Computer
Science, Krems, Austria, 2017, vol. 10706, pp. 40–44.
ista: 'Henzinger M. 2017. The state of the art in dynamic graph algorithms. 44th
International Conference on Current Trends in Theory and Practice of Computer
Science. SOFSEM: Theory and Practice of Computer Science, LNCS, vol. 10706, 40–44.'
mla: Henzinger, Monika. “The State of the Art in Dynamic Graph Algorithms.” 44th
International Conference on Current Trends in Theory and Practice of Computer
Science, vol. 10706, Springer Nature, 2017, pp. 40–44, doi:10.1007/978-3-319-73117-9_3.
short: M. Henzinger, in:, 44th International Conference on Current Trends in Theory
and Practice of Computer Science, Springer Nature, 2017, pp. 40–44.
conference:
end_date: 2018-02-02
location: Krems, Austria
name: 'SOFSEM: Theory and Practice of Computer Science'
start_date: 2018-01-29
date_created: 2022-08-08T13:16:37Z
date_published: 2017-12-22T00:00:00Z
date_updated: 2024-11-06T08:15:42Z
day: '22'
doi: 10.1007/978-3-319-73117-9_3
extern: '1'
intvolume: ' 10706'
language:
- iso: eng
month: '12'
oa_version: None
page: 40–44
publication: 44th International Conference on Current Trends in Theory and Practice
of Computer Science
publication_identifier:
eisbn:
- '9783319731179'
isbn:
- '9783319731162'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: The state of the art in dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10706
year: '2017'
...
---
_id: '1178'
abstract:
- lang: eng
text: 'For any pair (X, Z) of correlated random variables we can think of Z as a
randomized function of X. If the domain of Z is small, one can make this function
computationally efficient by allowing it to be only approximately correct. In
folklore this problem is known as simulating auxiliary inputs. This idea of simulating
auxiliary information turns out to be a very usefull tool, finding applications
in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this
paper we revisit this problem, achieving the following results: (a) We present
a novel boosting algorithm for constructing the simulator. This boosting proof
is of independent interest, as it shows how to handle “negative mass” issues when
constructing probability measures by shifting distinguishers in descent algorithms.
Our technique essentially fixes the flaw in the TCC’14 paper “How to Fake Auxiliary
Inputs”. (b) The complexity of our simulator is better than in previous works,
including results derived from the uniform min-max theorem due to Vadhan and Zheng.
To achieve (s,ϵ) -indistinguishability we need the complexity O(s⋅25ℓϵ−2) in time/circuit
size, which improve previous bounds by a factor of ϵ−2. In particular, with we
get meaningful provable security for the EUROCRYPT’09 leakage-resilient stream
cipher instantiated with a standard 256-bit block cipher, like '
acknowledgement: This work was supported by the National Science Center, Poland (2015/17/N/ST6/03564).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Maciej
full_name: Skórski, Maciej
id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
last_name: Skórski
citation:
ama: 'Skórski M. Simulating auxiliary inputs, revisited. In: Vol 9985. Springer;
2017:159-179. doi:10.1007/978-3-662-53641-4_7'
apa: 'Skórski, M. (2017). Simulating auxiliary inputs, revisited (Vol. 9985, pp.
159–179). Presented at the TCC: Theory of Cryptography Conference, Springer. https://doi.org/10.1007/978-3-662-53641-4_7'
chicago: Skórski, Maciej. “Simulating Auxiliary Inputs, Revisited,” 9985:159–79.
Springer, 2017. https://doi.org/10.1007/978-3-662-53641-4_7.
ieee: 'M. Skórski, “Simulating auxiliary inputs, revisited,” presented at the TCC:
Theory of Cryptography Conference, 2017, vol. 9985, pp. 159–179.'
ista: 'Skórski M. 2017. Simulating auxiliary inputs, revisited. TCC: Theory of Cryptography
Conference, LNCS, vol. 9985, 159–179.'
mla: Skórski, Maciej. Simulating Auxiliary Inputs, Revisited. Vol. 9985,
Springer, 2017, pp. 159–79, doi:10.1007/978-3-662-53641-4_7.
short: M. Skórski, in:, Springer, 2017, pp. 159–179.
conference:
name: 'TCC: Theory of Cryptography Conference'
date_created: 2018-12-11T11:50:34Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-09-20T11:21:57Z
day: '01'
doi: 10.1007/978-3-662-53641-4_7
extern: '1'
external_id:
isi:
- '000390176000007'
intvolume: ' 9985'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: 'https://eprint.iacr.org/2016/808.pdf '
month: '01'
oa: 1
oa_version: Submitted Version
page: 159 - 179
publication_status: published
publisher: Springer
publist_id: '6176'
quality_controlled: '1'
status: public
title: Simulating auxiliary inputs, revisited
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 9985
year: '2017'
...
---
_id: '1180'
abstract:
- lang: eng
text: In this article we define an algebraic vertex of a generalized polyhedron
and show that the set of algebraic vertices is the smallest set of points needed
to define the polyhedron. We prove that the indicator function of a generalized
polytope P is a linear combination of indicator functions of simplices whose vertices
are algebraic vertices of P. We also show that the indicator function of any generalized
polyhedron is a linear combination, with integer coefficients, of indicator functions
of cones with apices at algebraic vertices and line-cones. The concept of an algebraic
vertex is closely related to the Fourier–Laplace transform. We show that a point
v is an algebraic vertex of a generalized polyhedron P if and only if the tangent
cone of P, at v, has non-zero Fourier–Laplace transform.
article_processing_charge: No
arxiv: 1
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Imre
full_name: Bárány, Imre
last_name: Bárány
- first_name: Sinai
full_name: Robins, Sinai
last_name: Robins
citation:
ama: Akopyan A, Bárány I, Robins S. Algebraic vertices of non-convex polyhedra.
Advances in Mathematics. 2017;308:627-644. doi:10.1016/j.aim.2016.12.026
apa: Akopyan, A., Bárány, I., & Robins, S. (2017). Algebraic vertices of non-convex
polyhedra. Advances in Mathematics. Academic Press. https://doi.org/10.1016/j.aim.2016.12.026
chicago: Akopyan, Arseniy, Imre Bárány, and Sinai Robins. “Algebraic Vertices of
Non-Convex Polyhedra.” Advances in Mathematics. Academic Press, 2017. https://doi.org/10.1016/j.aim.2016.12.026.
ieee: A. Akopyan, I. Bárány, and S. Robins, “Algebraic vertices of non-convex polyhedra,”
Advances in Mathematics, vol. 308. Academic Press, pp. 627–644, 2017.
ista: Akopyan A, Bárány I, Robins S. 2017. Algebraic vertices of non-convex polyhedra.
Advances in Mathematics. 308, 627–644.
mla: Akopyan, Arseniy, et al. “Algebraic Vertices of Non-Convex Polyhedra.” Advances
in Mathematics, vol. 308, Academic Press, 2017, pp. 627–44, doi:10.1016/j.aim.2016.12.026.
short: A. Akopyan, I. Bárány, S. Robins, Advances in Mathematics 308 (2017) 627–644.
date_created: 2018-12-11T11:50:34Z
date_published: 2017-02-21T00:00:00Z
date_updated: 2025-06-04T08:45:48Z
day: '21'
department:
- _id: HeEd
doi: 10.1016/j.aim.2016.12.026
ec_funded: 1
external_id:
arxiv:
- '1508.07594'
isi:
- '000409292900015'
intvolume: ' 308'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1508.07594
month: '02'
oa: 1
oa_version: Submitted Version
page: 627 - 644
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Advances in Mathematics
publication_identifier:
issn:
- 0001-8708
publication_status: published
publisher: Academic Press
publist_id: '6173'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algebraic vertices of non-convex polyhedra
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 308
year: '2017'
...
---
_id: '11829'
abstract:
- lang: eng
text: "In recent years it has become popular to study dynamic problems in a sensitivity
setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity
model only allows to apply batch updates of small size to the original input data.
The sensitivity model is particularly appealing since recent strong conditional
lower bounds ruled out fast algorithms for many dynamic problems, such as shortest
paths, reachability, or subgraph connectivity.\r\n\r\nIn this paper we prove conditional
lower bounds for these and additional problems in a sensitivity setting. For example,
we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial
algorithms cannot compute the (4/3-\\varepsilon)-approximate diameter of an undirected
unweighted dense graph with truly subcubic preprocessing time and truly subquadratic
update/query time. This result is surprising since in the static setting it is
not clear whether a reduction from BMM to diameter is possible. We further show
under the BMM conjecture that many problems, such as reachability or approximate
shortest paths, cannot be solved faster than by recomputation from scratch even
after only one or two edge insertions. We extend our reduction from BMM to Diameter
to give a reduction from All Pairs Shortest Paths to Diameter under one deletion
in weighted graphs. This is intriguing, as in the static setting it is a big open
problem whether Diameter is as hard as APSP. We further get a nearly tight lower
bound for shortest paths after two edge deletions based on the APSP conjecture.
We give more lower bounds under the Strong Exponential Time Hypothesis. Many of
our lower bounds also hold for static oracle data structures where no sensitivity
is required.\r\n\r\nFinally, we give the first algorithm for the (1+\\varepsilon)-approximate
radius, diameter, and eccentricity problems in directed or undirected unweighted
graphs in case of single edges failures. The algorithm has a truly subcubic running
time for graphs with a truly subquadratic number of edges; it is tight w.r.t.
the conditional lower bounds we obtain."
alternative_title:
- LIPIcs
article_number: '26'
article_processing_charge: No
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: Andrea
full_name: Lincoln, Andrea
last_name: Lincoln
- first_name: Stefan
full_name: Neumann, Stefan
last_name: Neumann
- first_name: Virginia
full_name: Vassilevska Williams, Virginia
last_name: Vassilevska Williams
citation:
ama: 'Henzinger M, Lincoln A, Neumann S, Vassilevska Williams V. Conditional hardness
for sensitivity problems. In: 8th Innovations in Theoretical Computer Science
Conference. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017.
doi:10.4230/LIPICS.ITCS.2017.26'
apa: 'Henzinger, M., Lincoln, A., Neumann, S., & Vassilevska Williams, V. (2017).
Conditional hardness for sensitivity problems. In 8th Innovations in Theoretical
Computer Science Conference (Vol. 67). Berkley, CA, United States: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2017.26'
chicago: Henzinger, Monika, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska
Williams. “Conditional Hardness for Sensitivity Problems.” In 8th Innovations
in Theoretical Computer Science Conference, Vol. 67. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017. https://doi.org/10.4230/LIPICS.ITCS.2017.26.
ieee: M. Henzinger, A. Lincoln, S. Neumann, and V. Vassilevska Williams, “Conditional
hardness for sensitivity problems,” in 8th Innovations in Theoretical Computer
Science Conference, Berkley, CA, United States, 2017, vol. 67.
ista: 'Henzinger M, Lincoln A, Neumann S, Vassilevska Williams V. 2017. Conditional
hardness for sensitivity problems. 8th Innovations in Theoretical Computer Science
Conference. ITCS: Innovations in Theoretical Computer Science Conference, LIPIcs,
vol. 67, 26.'
mla: Henzinger, Monika, et al. “Conditional Hardness for Sensitivity Problems.”
8th Innovations in Theoretical Computer Science Conference, vol. 67, 26,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ITCS.2017.26.
short: M. Henzinger, A. Lincoln, S. Neumann, V. Vassilevska Williams, in:, 8th Innovations
in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017.
conference:
end_date: 2017-01-11
location: Berkley, CA, United States
name: 'ITCS: Innovations in Theoretical Computer Science Conference'
start_date: 2017-01-09
date_created: 2022-08-12T08:55:33Z
date_published: 2017-11-28T00:00:00Z
date_updated: 2024-11-06T11:56:09Z
day: '28'
doi: 10.4230/LIPICS.ITCS.2017.26
extern: '1'
external_id:
arxiv:
- '1703.01638'
intvolume: ' 67'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPICS.ITCS.2017.26
month: '11'
oa: 1
oa_version: Published Version
publication: 8th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959770293'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Conditional hardness for sensitivity problems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 67
year: '2017'
...
---
_id: '11831'
abstract:
- lang: eng
text: "Graph Sparsification aims at compressing large graphs into smaller ones while
(approximately) preserving important characteristics of the input graph. In this
work we study Vertex Sparsifiers, i.e., sparsifiers whose goal is to reduce the
number of vertices. Given a weighted graph G=(V,E), and a terminal set K with
|K|=k, a quality-q vertex cut sparsifier of G is a graph H with K contained in
V_H that preserves the value of minimum cuts separating any bipartition of K,
up to a factor of q. We show that planar graphs with all the k terminals lying
on the same face admit quality-1 vertex cut sparsifier of size O(k^2) that are
also planar. Our result extends to vertex flow and distance sparsifiers. It improves
the previous best known bound of O(k^2 2^(2k)) for cut and flow sparsifiers by
an exponential factor, and matches an Omega(k^2) lower-bound for this class of
graphs.\r\n\r\nWe also study vertex reachability sparsifiers for directed graphs.
Given a digraph G=(V,E) and a terminal set K, a vertex reachability sparsifier
of G is a digraph H=(V_H,E_H), K contained in V_H that preserves all reachability
information among terminal pairs. We introduce the notion of reachability-preserving
minors, i.e., we require H to be a minor of G. Among others, for general planar
digraphs, we construct reachability-preserving minors of size O(k^2 log^2 k).
We complement our upper-bound by showing that there exists an infinite family
of acyclic planar digraphs such that any reachability-preserving minor must have
Omega(k^2) vertices."
alternative_title:
- LIPIcs
article_number: '44'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: Pan
full_name: Peng, Pan
last_name: Peng
citation:
ama: 'Goranci G, Henzinger M, Peng P. Improved guarantees for vertex sparsification
in planar graphs. In: 25th Annual European Symposium on Algorithms. Vol
87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.44'
apa: 'Goranci, G., Henzinger, M., & Peng, P. (2017). Improved guarantees for
vertex sparsification in planar graphs. In 25th Annual European Symposium on
Algorithms (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ESA.2017.44'
chicago: Goranci, Gramoz, Monika Henzinger, and Pan Peng. “Improved Guarantees for
Vertex Sparsification in Planar Graphs.” In 25th Annual European Symposium
on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017. https://doi.org/10.4230/LIPICS.ESA.2017.44.
ieee: G. Goranci, M. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification
in planar graphs,” in 25th Annual European Symposium on Algorithms, Vienna,
Austria, 2017, vol. 87.
ista: 'Goranci G, Henzinger M, Peng P. 2017. Improved guarantees for vertex sparsification
in planar graphs. 25th Annual European Symposium on Algorithms. ESA: Annual European
Symposium on Algorithms, LIPIcs, vol. 87, 44.'
mla: Goranci, Gramoz, et al. “Improved Guarantees for Vertex Sparsification in Planar
Graphs.” 25th Annual European Symposium on Algorithms, vol. 87, 44, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.44.
short: G. Goranci, M. Henzinger, P. Peng, in:, 25th Annual European Symposium on
Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-09-06
location: Vienna, Austria
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2017-09-04
date_created: 2022-08-12T09:27:11Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2024-11-06T11:57:54Z
day: '01'
doi: 10.4230/LIPICS.ESA.2017.44
extern: '1'
external_id:
arxiv:
- '1702.01136'
intvolume: ' 87'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.ESA.2017.44
month: '09'
oa: 1
oa_version: Published Version
publication: 25th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- 978-3-95977-049-1
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '11894'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Improved guarantees for vertex sparsification in planar graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 87
year: '2017'
...
---
_id: '11832'
abstract:
- lang: eng
text: "In this paper, we study the problem of opening centers to cluster a set of
clients in a metric space so as to minimize the sum of the costs of the centers
and of the cluster radii, in a dynamic environment where clients arrive and depart,
and the solution must be updated efficiently while remaining competitive with
respect to the current optimal solution. We call this dynamic sum-of-radii clustering
problem.\r\n\r\nWe present a data structure that maintains a solution whose cost
is within a constant factor of the cost of an optimal solution in metric spaces
with bounded doubling dimension and whose worst-case update time is logarithmic
in the parameters of the problem."
alternative_title:
- LIPIcs
article_number: '48'
article_processing_charge: No
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: Dariusz
full_name: Leniowski, Dariusz
last_name: Leniowski
- first_name: Claire
full_name: Mathieu, Claire
last_name: Mathieu
citation:
ama: 'Henzinger M, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum
of radii. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.48'
apa: 'Henzinger, M., Leniowski, D., & Mathieu, C. (2017). Dynamic clustering
to minimize the sum of radii. In 25th Annual European Symposium on Algorithms
(Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPICS.ESA.2017.48'
chicago: Henzinger, Monika, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering
to Minimize the Sum of Radii.” In 25th Annual European Symposium on Algorithms,
Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.48.
ieee: M. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize
the sum of radii,” in 25th Annual European Symposium on Algorithms, Vienna,
Austria, 2017, vol. 87.
ista: 'Henzinger M, Leniowski D, Mathieu C. 2017. Dynamic clustering to minimize
the sum of radii. 25th Annual European Symposium on Algorithms. ESA: Annual European
Symposium on Algorithms, LIPIcs, vol. 87, 48.'
mla: Henzinger, Monika, et al. “Dynamic Clustering to Minimize the Sum of Radii.”
25th Annual European Symposium on Algorithms, vol. 87, 48, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.48.
short: M. Henzinger, D. Leniowski, C. Mathieu, in:, 25th Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-09-06
location: Vienna, Austria
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2017-09-04
date_created: 2022-08-12T09:58:46Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2024-11-06T11:59:20Z
day: '01'
doi: 10.4230/LIPICS.ESA.2017.48
extern: '1'
external_id:
arxiv:
- '1707.02577'
intvolume: ' 87'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPICS.ESA.2017.48
month: '09'
oa: 1
oa_version: Published Version
publication: 25th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- 978-3-95977-049-1
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic clustering to minimize the sum of radii
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 87
year: '2017'
...
---
_id: '11833'
abstract:
- lang: eng
text: "We introduce a new algorithmic framework for designing dynamic graph algorithms
in minor-free graphs, by exploiting the structure of such graphs and a tool called
vertex sparsification, which is a way to compress large graphs into small ones
that well preserve relevant properties among a subset of vertices and has previously
mainly been used in the design of approximation algorithms.\r\n\r\nUsing this
framework, we obtain a Monte Carlo randomized fully dynamic algorithm for (1 +
epsilon)-approximating the energy of electrical flows in n-vertex planar graphs
with tilde{O}(r epsilon^{-2}) worst-case update time and tilde{O}((r + n / sqrt{r})
epsilon^{-2}) worst-case query time, for any r larger than some constant. For
r=n^{2/3}, this gives tilde{O}(n^{2/3} epsilon^{-2}) update time and tilde{O}(n^{2/3}
epsilon^{-2}) query time. We also extend this algorithm to work for minor-free
graphs with similar approximation and running time guarantees. Furthermore, we
illustrate our framework on the all-pairs max flow and shortest path problems
by giving corresponding dynamic algorithms in minor-free graphs with both sublinear
update and query times. To the best of our knowledge, our results are the first
to systematically establish such a connection between dynamic graph algorithms
and vertex sparsification.\r\n\r\nWe also present both upper bound and lower bound
for maintaining the energy of electrical flows in the incremental subgraph model,
where updates consist of only vertex activations, which might be of independent
interest."
alternative_title:
- LIPIcs
article_number: '45'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: Pan
full_name: Peng, Pan
last_name: Peng
citation:
ama: 'Goranci G, Henzinger M, Peng P. The power of vertex sparsifiers in dynamic
graph algorithms. In: 25th Annual European Symposium on Algorithms. Vol
87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.45'
apa: 'Goranci, G., Henzinger, M., & Peng, P. (2017). The power of vertex sparsifiers
in dynamic graph algorithms. In 25th Annual European Symposium on Algorithms
(Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPICS.ESA.2017.45'
chicago: Goranci, Gramoz, Monika Henzinger, and Pan Peng. “The Power of Vertex Sparsifiers
in Dynamic Graph Algorithms.” In 25th Annual European Symposium on Algorithms,
Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.45.
ieee: G. Goranci, M. Henzinger, and P. Peng, “The power of vertex sparsifiers in
dynamic graph algorithms,” in 25th Annual European Symposium on Algorithms,
Vienna, Austria, 2017, vol. 87.
ista: 'Goranci G, Henzinger M, Peng P. 2017. The power of vertex sparsifiers in
dynamic graph algorithms. 25th Annual European Symposium on Algorithms. ESA: Annual
European Symposium on Algorithms, LIPIcs, vol. 87, 45.'
mla: Goranci, Gramoz, et al. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.”
25th Annual European Symposium on Algorithms, vol. 87, 45, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.45.
short: G. Goranci, M. Henzinger, P. Peng, in:, 25th Annual European Symposium on
Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-09-06
location: Vienna, Austria
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2017-09-04
date_created: 2022-08-12T10:46:26Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2024-11-06T11:58:29Z
day: '01'
doi: 10.4230/LIPICS.ESA.2017.45
extern: '1'
external_id:
arxiv:
- '1712.06473'
intvolume: ' 87'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.ESA.2017.45
month: '09'
oa: 1
oa_version: Published Version
publication: 25th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- 978-3-95977-049-1
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: The power of vertex sparsifiers in dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 87
year: '2017'
...
---
_id: '1187'
abstract:
- lang: eng
text: We construct efficient authentication protocols and message authentication
codes (MACs) whose security can be reduced to the learning parity with noise (LPN)
problem. Despite a large body of work—starting with the (Formula presented.) protocol
of Hopper and Blum in 2001—until now it was not even known how to construct an
efficient authentication protocol from LPN which is secure against man-in-the-middle
attacks. A MAC implies such a (two-round) protocol.
article_processing_charge: No
article_type: original
author:
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniele
full_name: Venturi, Daniele
last_name: Venturi
- first_name: David
full_name: Cash, David
last_name: Cash
- first_name: Abhishek
full_name: Jain, Abhishek
last_name: Jain
citation:
ama: Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. Efficient authentication from
hard learning problems. Journal of Cryptology. 2017;30(4):1238-1275. doi:10.1007/s00145-016-9247-3
apa: Kiltz, E., Pietrzak, K. Z., Venturi, D., Cash, D., & Jain, A. (2017). Efficient
authentication from hard learning problems. Journal of Cryptology. Springer.
https://doi.org/10.1007/s00145-016-9247-3
chicago: Kiltz, Eike, Krzysztof Z Pietrzak, Daniele Venturi, David Cash, and Abhishek
Jain. “Efficient Authentication from Hard Learning Problems.” Journal of Cryptology.
Springer, 2017. https://doi.org/10.1007/s00145-016-9247-3.
ieee: E. Kiltz, K. Z. Pietrzak, D. Venturi, D. Cash, and A. Jain, “Efficient authentication
from hard learning problems,” Journal of Cryptology, vol. 30, no. 4. Springer,
pp. 1238–1275, 2017.
ista: Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. 2017. Efficient authentication
from hard learning problems. Journal of Cryptology. 30(4), 1238–1275.
mla: Kiltz, Eike, et al. “Efficient Authentication from Hard Learning Problems.”
Journal of Cryptology, vol. 30, no. 4, Springer, 2017, pp. 1238–75, doi:10.1007/s00145-016-9247-3.
short: E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology
30 (2017) 1238–1275.
date_created: 2018-12-11T11:50:37Z
date_published: 2017-10-01T00:00:00Z
date_updated: 2025-04-14T07:22:06Z
day: '01'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1007/s00145-016-9247-3
ec_funded: 1
external_id:
isi:
- '000410788600007'
file:
- access_level: open_access
checksum: c647520d115b772a1682fc06fa273eb1
content_type: application/pdf
creator: dernst
date_created: 2020-05-14T16:30:17Z
date_updated: 2020-07-14T12:44:37Z
file_id: '7843'
file_name: 2017_JournalCrypto_Kiltz.pdf
file_size: 516959
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 30'
isi: 1
issue: '4'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 1238 - 1275
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Journal of Cryptology
publication_status: published
publisher: Springer
publist_id: '6166'
quality_controlled: '1'
related_material:
record:
- id: '3238'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Efficient authentication from hard learning problems
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 30
year: '2017'
...
---
_id: '11873'
abstract:
- lang: eng
text: "We study the problem of computing a minimum cut in a simple, undirected graph
and give a deterministic O(m log2 n log log2 n) time algorithm. This improves
both on the best previously known deterministic running time of O(m log12 n) (Kawarabayashi
and Thorup [12]) and the best previously known randomized running time of O(mlog3n)
(Karger [11]) for this problem, though Karger's algorithm can be further applied
to weighted graphs.\r\n\r\nOur approach is using the Kawarabayashi and Tho- rup
graph compression technique, which repeatedly finds low-conductance cuts. To find
these cuts they use a diffusion-based local algorithm. We use instead a flow-
based local algorithm and suitably adjust their framework to work with our flow-based
subroutine. Both flow and diffusion based methods have a long history of being
applied to finding low conductance cuts. Diffusion algorithms have several variants
that are naturally local while it is more complicated to make flow methods local.
Some prior work has proven nice properties for local flow based algorithms with
respect to improving or cleaning up low conductance cuts. Our flow subroutine,
however, is the first that is both local and produces low conductance cuts. Thus,
it may be of independent interest."
article_processing_charge: No
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: Satish
full_name: Rao, Satish
last_name: Rao
- first_name: Di
full_name: Wang, Di
last_name: Wang
citation:
ama: 'Henzinger M, Rao S, Wang D. Local flow partitioning for faster edge connectivity.
In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for
Industrial and Applied Mathematics; 2017:1919-1938. doi:10.1137/1.9781611974782.125'
apa: 'Henzinger, M., Rao, S., & Wang, D. (2017). Local flow partitioning for
faster edge connectivity. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms
(pp. 1919–1938). Barcelona, Spain: Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/1.9781611974782.125'
chicago: Henzinger, Monika, Satish Rao, and Di Wang. “Local Flow Partitioning for
Faster Edge Connectivity.” In 28th Annual ACM-SIAM Symposium on Discrete Algorithms,
1919–38. Society for Industrial and Applied Mathematics, 2017. https://doi.org/10.1137/1.9781611974782.125.
ieee: M. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge
connectivity,” in 28th Annual ACM-SIAM Symposium on Discrete Algorithms,
Barcelona, Spain, 2017, pp. 1919–1938.
ista: 'Henzinger M, Rao S, Wang D. 2017. Local flow partitioning for faster edge
connectivity. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium
on Discrete Algorithms, 1919–1938.'
mla: Henzinger, Monika, et al. “Local Flow Partitioning for Faster Edge Connectivity.”
28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial
and Applied Mathematics, 2017, pp. 1919–38, doi:10.1137/1.9781611974782.125.
short: M. Henzinger, S. Rao, D. Wang, in:, 28th Annual ACM-SIAM Symposium on Discrete
Algorithms, Society for Industrial and Applied Mathematics, 2017, pp. 1919–1938.
conference:
end_date: 2017-01-19
location: Barcelona, Spain
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2017-01-16
date_created: 2022-08-16T12:20:59Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2024-11-06T12:22:42Z
day: '01'
doi: 10.1137/1.9781611974782.125
extern: '1'
external_id:
arxiv:
- '1704.01254'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1704.01254
month: '01'
oa: 1
oa_version: Preprint
page: 1919-1938
publication: 28th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- 978-161197478-2
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '11889'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Local flow partitioning for faster edge connectivity
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...