---
_id: '635'
abstract:
- lang: eng
text: Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is
dominated by memory cost. As memory, unlike computation, costs about the same
across different platforms, MHFs cannot be evaluated at significantly lower cost
on dedicated hardware like ASICs. MHFs have found widespread applications including
password hashing, key derivation, and proofs-of-work. This paper focuses on scrypt,
a simple candidate MHF designed by Percival, and described in RFC 7914. It has
been used within a number of cryptocurrencies (e.g., Litecoin and Dogecoin) and
has been an inspiration for Argon2d, one of the winners of the recent password-hashing
competition. Despite its popularity, no rigorous lower bounds on its memory complexity
are known. We prove that scrypt is optimally memory-hard, i.e., its cumulative
memory complexity (cmc) in the parallel random oracle model is Ω(n2w), where w
and n are the output length and number of invocations of the underlying hash function,
respectively. High cmc is a strong security target for MHFs introduced by Alwen
and Serbinenko (STOC’15) which implies high memory cost even for adversaries who
can amortize the cost over many evaluations and evaluate the underlying hash functions
many times in parallel. Our proof is the first showing optimal memory-hardness
for any MHF. Our result improves both quantitatively and qualitatively upon the
recent work by Alwen et al. (EUROCRYPT’16) who proved a weaker lower bound of
Ω(n2w/ log2 n) for a restricted class of adversaries.
alternative_title:
- LNCS
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Binchi
full_name: Chen, Binchi
last_name: Chen
- 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: Leonid
full_name: Reyzin, Leonid
last_name: Reyzin
- first_name: Stefano
full_name: Tessaro, Stefano
last_name: Tessaro
citation:
ama: 'Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. Scrypt is maximally memory
hard. In: Coron J-S, Buus Nielsen J, eds. Vol 10212. Springer; 2017:33-62. doi:10.1007/978-3-319-56617-7_2'
apa: 'Alwen, J. F., Chen, B., Pietrzak, K. Z., Reyzin, L., & Tessaro, S. (2017).
Scrypt is maximally memory hard. In J.-S. Coron & J. Buus Nielsen (Eds.) (Vol.
10212, pp. 33–62). Presented at the EUROCRYPT: Theory and Applications of Cryptographic
Techniques, Paris, France: Springer. https://doi.org/10.1007/978-3-319-56617-7_2'
chicago: Alwen, Joel F, Binchi Chen, Krzysztof Z Pietrzak, Leonid Reyzin, and Stefano
Tessaro. “Scrypt Is Maximally Memory Hard.” edited by Jean-Sébastien Coron and
Jesper Buus Nielsen, 10212:33–62. Springer, 2017. https://doi.org/10.1007/978-3-319-56617-7_2.
ieee: 'J. F. Alwen, B. Chen, K. Z. Pietrzak, L. Reyzin, and S. Tessaro, “Scrypt
is maximally memory hard,” presented at the EUROCRYPT: Theory and Applications
of Cryptographic Techniques, Paris, France, 2017, vol. 10212, pp. 33–62.'
ista: 'Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. 2017. Scrypt is maximally
memory hard. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS,
vol. 10212, 33–62.'
mla: Alwen, Joel F., et al. Scrypt Is Maximally Memory Hard. Edited by Jean-Sébastien
Coron and Jesper Buus Nielsen, vol. 10212, Springer, 2017, pp. 33–62, doi:10.1007/978-3-319-56617-7_2.
short: J.F. Alwen, B. Chen, K.Z. Pietrzak, L. Reyzin, S. Tessaro, in:, J.-S. Coron,
J. Buus Nielsen (Eds.), Springer, 2017, pp. 33–62.
conference:
end_date: 2017-05-04
location: Paris, France
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2017-04-30
date_created: 2018-12-11T11:47:37Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2021-01-12T08:07:10Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-56617-7_2
ec_funded: 1
editor:
- first_name: Jean-Sébastien
full_name: Coron, Jean-Sébastien
last_name: Coron
- first_name: Jesper
full_name: Buus Nielsen, Jesper
last_name: Buus Nielsen
intvolume: ' 10212'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/989
month: '01'
oa: 1
oa_version: Submitted Version
page: 33 - 62
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
isbn:
- 978-331956616-0
publication_status: published
publisher: Springer
publist_id: '7154'
quality_controlled: '1'
scopus_import: 1
status: public
title: Scrypt is maximally memory hard
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 10212
year: '2017'
...
---
_id: '636'
abstract:
- lang: eng
text: Signal regular expressions can specify sequential properties of real-valued
signals based on threshold conditions, regular operations, and duration constraints.
In this paper we endow them with a quantitative semantics which indicates how
robustly a signal matches or does not match a given expression. First, we show
that this semantics is a safe approximation of a distance between the signal and
the language defined by the expression. Then, we consider the robust matching
problem, that is, computing the quantitative semantics of every segment of a given
signal relative to an expression. We present an algorithm that solves this problem
for piecewise-constant and piecewise-linear signals and show that for such signals
the robustness map is a piecewise-linear function. The availability of an indicator
describing how robustly a signal segment matches some regular pattern provides
a general framework for quantitative monitoring of cyber-physical systems.
alternative_title:
- LNCS
author:
- first_name: Alexey
full_name: Bakhirkin, Alexey
last_name: Bakhirkin
- first_name: Thomas
full_name: Ferrere, Thomas
id: 40960E6E-F248-11E8-B48F-1D18A9856A87
last_name: Ferrere
orcid: 0000-0001-5199-3143
- first_name: Oded
full_name: Maler, Oded
last_name: Maler
- first_name: Dogan
full_name: Ulus, Dogan
last_name: Ulus
citation:
ama: 'Bakhirkin A, Ferrere T, Maler O, Ulus D. On the quantitative semantics of
regular expressions over real-valued signals. In: Abate A, Geeraerts G, eds. Vol
10419. Springer; 2017:189-206. doi:10.1007/978-3-319-65765-3_11'
apa: 'Bakhirkin, A., Ferrere, T., Maler, O., & Ulus, D. (2017). On the quantitative
semantics of regular expressions over real-valued signals. In A. Abate & G.
Geeraerts (Eds.) (Vol. 10419, pp. 189–206). Presented at the FORMATS: Formal Modelling
and Analysis of Timed Systems, Berlin, Germany: Springer. https://doi.org/10.1007/978-3-319-65765-3_11'
chicago: Bakhirkin, Alexey, Thomas Ferrere, Oded Maler, and Dogan Ulus. “On the
Quantitative Semantics of Regular Expressions over Real-Valued Signals.” edited
by Alessandro Abate and Gilles Geeraerts, 10419:189–206. Springer, 2017. https://doi.org/10.1007/978-3-319-65765-3_11.
ieee: 'A. Bakhirkin, T. Ferrere, O. Maler, and D. Ulus, “On the quantitative semantics
of regular expressions over real-valued signals,” presented at the FORMATS: Formal
Modelling and Analysis of Timed Systems, Berlin, Germany, 2017, vol. 10419, pp.
189–206.'
ista: 'Bakhirkin A, Ferrere T, Maler O, Ulus D. 2017. On the quantitative semantics
of regular expressions over real-valued signals. FORMATS: Formal Modelling and
Analysis of Timed Systems, LNCS, vol. 10419, 189–206.'
mla: Bakhirkin, Alexey, et al. On the Quantitative Semantics of Regular Expressions
over Real-Valued Signals. Edited by Alessandro Abate and Gilles Geeraerts,
vol. 10419, Springer, 2017, pp. 189–206, doi:10.1007/978-3-319-65765-3_11.
short: A. Bakhirkin, T. Ferrere, O. Maler, D. Ulus, in:, A. Abate, G. Geeraerts
(Eds.), Springer, 2017, pp. 189–206.
conference:
end_date: 2017-09-07
location: Berlin, Germany
name: 'FORMATS: Formal Modelling and Analysis of Timed Systems'
start_date: 2017-09-05
date_created: 2018-12-11T11:47:38Z
date_published: 2017-08-03T00:00:00Z
date_updated: 2021-01-12T08:07:14Z
day: '03'
department:
- _id: ToHe
doi: 10.1007/978-3-319-65765-3_11
editor:
- first_name: Alessandro
full_name: Abate, Alessandro
last_name: Abate
- first_name: Gilles
full_name: Geeraerts, Gilles
last_name: Geeraerts
intvolume: ' 10419'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://hal.archives-ouvertes.fr/hal-01552132
month: '08'
oa: 1
oa_version: Submitted Version
page: 189 - 206
project:
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
publication_identifier:
isbn:
- 978-331965764-6
publication_status: published
publisher: Springer
publist_id: '7152'
quality_controlled: '1'
scopus_import: 1
status: public
title: On the quantitative semantics of regular expressions over real-valued signals
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10419
year: '2017'
...
---
_id: '637'
abstract:
- lang: eng
text: For many cryptographic primitives, it is relatively easy to achieve selective
security (where the adversary commits a-priori to some of the choices to be made
later in the attack) but appears difficult to achieve the more natural notion
of adaptive security (where the adversary can make all choices on the go as the
attack progresses). A series of several recent works shows how to cleverly achieve
adaptive security in several such scenarios including generalized selective decryption
(Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer
et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b).
Although the above works expressed vague intuition that they share a common technique,
the connection was never made precise. In this work we present a new framework
that connects all of these works and allows us to present them in a unified and
simplified fashion. Moreover, we use the framework to derive a new result for
adaptively secure secret sharing over access structures defined via monotone circuits.
We envision that further applications will follow in the future. Underlying our
framework is the following simple idea. It is well known that selective security,
where the adversary commits to n-bits of information about his future choices,
automatically implies adaptive security at the cost of amplifying the adversary’s
advantage by a factor of up to 2n. However, in some cases the proof of selective
security proceeds via a sequence of hybrids, where each pair of adjacent hybrids
locally only requires some smaller partial information consisting of m ≪ n bits.
The partial information needed might be completely different between different
pairs of hybrids, and if we look across all the hybrids we might rely on the entire
n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security,
at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n.
In all of our examples using the above framework, the different hybrids are captured
by some sort of a graph pebbling game and the amount of information that the adversary
needs to commit to in each pair of hybrids is bounded by the maximum number of
pebbles in play at any point in time. Therefore, coming up with better strategies
for proving adaptive security translates to various pebbling strategies for different
types of graphs.
alternative_title:
- LNCS
author:
- first_name: Zahra
full_name: Jafargholi, Zahra
last_name: Jafargholi
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Ilan
full_name: Komargodski, Ilan
last_name: Komargodski
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs
D. Be adaptive avoid overcommitting. In: Katz J, Shacham H, eds. Vol 10401. Springer;
2017:133-163. doi:10.1007/978-3-319-63688-7_5'
apa: 'Jafargholi, Z., Kamath Hosdurg, C., Klein, K., Komargodski, I., Pietrzak,
K. Z., & Wichs, D. (2017). Be adaptive avoid overcommitting. In J. Katz &
H. Shacham (Eds.) (Vol. 10401, pp. 133–163). Presented at the CRYPTO: Cryptology,
Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-319-63688-7_5'
chicago: Jafargholi, Zahra, Chethan Kamath Hosdurg, Karen Klein, Ilan Komargodski,
Krzysztof Z Pietrzak, and Daniel Wichs. “Be Adaptive Avoid Overcommitting.” edited
by Jonathan Katz and Hovav Shacham, 10401:133–63. Springer, 2017. https://doi.org/10.1007/978-3-319-63688-7_5.
ieee: 'Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K. Z. Pietrzak,
and D. Wichs, “Be adaptive avoid overcommitting,” presented at the CRYPTO: Cryptology,
Santa Barbara, CA, United States, 2017, vol. 10401, pp. 133–163.'
ista: 'Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs
D. 2017. Be adaptive avoid overcommitting. CRYPTO: Cryptology, LNCS, vol. 10401,
133–163.'
mla: Jafargholi, Zahra, et al. Be Adaptive Avoid Overcommitting. Edited by
Jonathan Katz and Hovav Shacham, vol. 10401, Springer, 2017, pp. 133–63, doi:10.1007/978-3-319-63688-7_5.
short: Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K.Z. Pietrzak,
D. Wichs, in:, J. Katz, H. Shacham (Eds.), Springer, 2017, pp. 133–163.
conference:
end_date: 2017-07-24
location: Santa Barbara, CA, United States
name: 'CRYPTO: Cryptology'
start_date: 2017-07-20
date_created: 2018-12-11T11:47:38Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-09-07T13:32:11Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-63688-7_5
ec_funded: 1
editor:
- first_name: Jonathan
full_name: Katz, Jonathan
last_name: Katz
- first_name: Hovav
full_name: Shacham, Hovav
last_name: Shacham
intvolume: ' 10401'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2017/515
month: '01'
oa: 1
oa_version: Submitted Version
page: 133 - 163
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
isbn:
- 978-331963687-0
publication_status: published
publisher: Springer
publist_id: '7151'
quality_controlled: '1'
related_material:
record:
- id: '10035'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Be adaptive avoid overcommitting
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10401
year: '2017'
...
---
_id: '639'
abstract:
- lang: eng
text: We study the problem of developing efficient approaches for proving worst-case
bounds of non-deterministic recursive programs. Ranking functions are sound and
complete for proving termination and worst-case bounds of non-recursive programs.
First, we apply ranking functions to recursion, resulting in measure functions,
and show that they provide a sound and complete approach to prove worst-case bounds
of non-deterministic recursive programs. Our second contribution is the synthesis
of measure functions in non-polynomial forms. We show that non-polynomial measure
functions with logarithm and exponentiation can be synthesized through abstraction
of logarithmic or exponentiation terms, Farkas’ Lemma, and Handelman’s Theorem
using linear programming. While previous methods obtain worst-case polynomial
bounds, our approach can synthesize bounds of the form O(n log n) as well as O(nr)
where r is not an integer. We present experimental results to demonstrate that
our approach can efficiently obtain worst-case bounds of classical recursive algorithms
such as Merge-Sort, Closest-Pair, Karatsuba’s algorithm and Strassen’s algorithm.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Hongfei
full_name: Fu, Hongfei
last_name: Fu
- first_name: Amir
full_name: Goharshady, Amir
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
citation:
ama: 'Chatterjee K, Fu H, Goharshady AK. Non-polynomial worst case analysis of recursive
programs. In: Majumdar R, Kunčak V, eds. Vol 10427. Springer; 2017:41-63. doi:10.1007/978-3-319-63390-9_3'
apa: 'Chatterjee, K., Fu, H., & Goharshady, A. K. (2017). Non-polynomial worst
case analysis of recursive programs. In R. Majumdar & V. Kunčak (Eds.) (Vol.
10427, pp. 41–63). Presented at the CAV: Computer Aided Verification, Heidelberg,
Germany: Springer. https://doi.org/10.1007/978-3-319-63390-9_3'
chicago: Chatterjee, Krishnendu, Hongfei Fu, and Amir Kafshdar Goharshady. “Non-Polynomial
Worst Case Analysis of Recursive Programs.” edited by Rupak Majumdar and Viktor
Kunčak, 10427:41–63. Springer, 2017. https://doi.org/10.1007/978-3-319-63390-9_3.
ieee: 'K. Chatterjee, H. Fu, and A. K. Goharshady, “Non-polynomial worst case analysis
of recursive programs,” presented at the CAV: Computer Aided Verification, Heidelberg,
Germany, 2017, vol. 10427, pp. 41–63.'
ista: 'Chatterjee K, Fu H, Goharshady AK. 2017. Non-polynomial worst case analysis
of recursive programs. CAV: Computer Aided Verification, LNCS, vol. 10427, 41–63.'
mla: Chatterjee, Krishnendu, et al. Non-Polynomial Worst Case Analysis of Recursive
Programs. Edited by Rupak Majumdar and Viktor Kunčak, vol. 10427, Springer,
2017, pp. 41–63, doi:10.1007/978-3-319-63390-9_3.
short: K. Chatterjee, H. Fu, A.K. Goharshady, in:, R. Majumdar, V. Kunčak (Eds.),
Springer, 2017, pp. 41–63.
conference:
end_date: 2017-07-28
location: Heidelberg, Germany
name: 'CAV: Computer Aided Verification'
start_date: 2017-07-24
date_created: 2018-12-11T11:47:39Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2025-06-02T08:53:47Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-319-63390-9_3
ec_funded: 1
editor:
- first_name: Rupak
full_name: Majumdar, Rupak
last_name: Majumdar
- first_name: Viktor
full_name: Kunčak, Viktor
last_name: Kunčak
external_id:
arxiv:
- '1705.00317'
intvolume: ' 10427'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1705.00317
month: '01'
oa: 1
oa_version: Submitted Version
page: 41 - 63
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication_identifier:
isbn:
- 978-331963389-3
publication_status: published
publisher: Springer
publist_id: '7149'
quality_controlled: '1'
related_material:
record:
- id: '8934'
relation: dissertation_contains
status: public
- id: '7014'
relation: later_version
status: public
scopus_import: 1
status: public
title: Non-polynomial worst case analysis of recursive programs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10427
year: '2017'
...
---
_id: '640'
abstract:
- lang: eng
text: 'Data-independent Memory Hard Functions (iMHFS) are finding a growing number
of applications in security; especially in the domain of password hashing. An
important property of a concrete iMHF is specified by fixing a directed acyclic
graph (DAG) Gn on n nodes. The quality of that iMHF is then captured by the following
two pebbling complexities of Gn: – The parallel cumulative pebbling complexity
Π∥cc(Gn) must be as high as possible (to ensure that the amortized cost of computing
the function on dedicated hardware is dominated by the cost of memory). – The
sequential space-time pebbling complexity Πst(Gn) should be as close as possible
to Π∥cc(Gn) (to ensure that using many cores in parallel and amortizing over many
instances does not give much of an advantage). In this paper we construct a family
of DAGs with best possible parameters in an asymptotic sense, i.e., where Π∥cc(Gn)
= Ω(n2/ log(n)) (which matches a known upper bound) and Πst(Gn) is within a constant
factor of Π∥cc(Gn). Our analysis relies on a new connection between the pebbling
complexity of a DAG and its depth-robustness (DR) – a well studied combinatorial
property. We show that high DR is sufficient for high Π∥cc. Alwen and Blocki (CRYPTO’16)
showed that high DR is necessary and so, together, these results fully characterize
DAGs with high Π∥cc in terms of DR. Complementing these results, we provide new
upper and lower bounds on the Π∥cc of several important candidate iMHFs from the
literature. We give the first lower bounds on the memory hardness of the Catena
and Balloon Hashing functions in a parallel model of computation and we give the
first lower bounds of any kind for (a version) of Argon2i. Finally we describe
a new class of pebbling attacks improving on those of Alwen and Blocki (CRYPTO’16).
By instantiating these attacks we upperbound the Π∥cc of the Password Hashing
Competition winner Argon2i and one of the Balloon Hashing functions by O (n1.71).
We also show an upper bound of O(n1.625) for the Catena functions and the two
remaining Balloon Hashing functions.'
alternative_title:
- LNCS
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
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Alwen JF, Blocki J, Pietrzak KZ. Depth-robust graphs and their cumulative
memory complexity. In: Coron J-S, Buus Nielsen J, eds. Vol 10212. Springer; 2017:3-32.
doi:10.1007/978-3-319-56617-7_1'
apa: 'Alwen, J. F., Blocki, J., & Pietrzak, K. Z. (2017). Depth-robust graphs
and their cumulative memory complexity. In J.-S. Coron & J. Buus Nielsen (Eds.)
(Vol. 10212, pp. 3–32). Presented at the EUROCRYPT: Theory and Applications of
Cryptographic Techniques, Paris, France: Springer. https://doi.org/10.1007/978-3-319-56617-7_1'
chicago: Alwen, Joel F, Jeremiah Blocki, and Krzysztof Z Pietrzak. “Depth-Robust
Graphs and Their Cumulative Memory Complexity.” edited by Jean-Sébastien Coron
and Jesper Buus Nielsen, 10212:3–32. Springer, 2017. https://doi.org/10.1007/978-3-319-56617-7_1.
ieee: 'J. F. Alwen, J. Blocki, and K. Z. Pietrzak, “Depth-robust graphs and their
cumulative memory complexity,” presented at the EUROCRYPT: Theory and Applications
of Cryptographic Techniques, Paris, France, 2017, vol. 10212, pp. 3–32.'
ista: 'Alwen JF, Blocki J, Pietrzak KZ. 2017. Depth-robust graphs and their cumulative
memory complexity. EUROCRYPT: Theory and Applications of Cryptographic Techniques,
LNCS, vol. 10212, 3–32.'
mla: Alwen, Joel F., et al. Depth-Robust Graphs and Their Cumulative Memory Complexity.
Edited by Jean-Sébastien Coron and Jesper Buus Nielsen, vol. 10212, Springer,
2017, pp. 3–32, doi:10.1007/978-3-319-56617-7_1.
short: J.F. Alwen, J. Blocki, K.Z. Pietrzak, in:, J.-S. Coron, J. Buus Nielsen (Eds.),
Springer, 2017, pp. 3–32.
conference:
end_date: 2017-05-04
location: Paris, France
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2017-04-30
date_created: 2018-12-11T11:47:39Z
date_published: 2017-04-01T00:00:00Z
date_updated: 2021-01-12T08:07:22Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-56617-7_1
ec_funded: 1
editor:
- first_name: Jean-Sébastien
full_name: Coron, Jean-Sébastien
last_name: Coron
- first_name: Jesper
full_name: Buus Nielsen, Jesper
last_name: Buus Nielsen
intvolume: ' 10212'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/875
month: '04'
oa: 1
oa_version: Submitted Version
page: 3 - 32
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
isbn:
- 978-331956616-0
publication_status: published
publisher: Springer
publist_id: '7148'
quality_controlled: '1'
scopus_import: 1
status: public
title: Depth-robust graphs and their cumulative memory complexity
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10212
year: '2017'
...
---
_id: '642'
abstract:
- lang: eng
text: Cauchy problems with SPDEs on the whole space are localized to Cauchy problems
on a ball of radius R. This localization reduces various kinds of spatial approximation
schemes to finite dimensional problems. The error is shown to be exponentially
small. As an application, a numerical scheme is presented which combines the localization
and the space and time discretization, and thus is fully implementable.
author:
- first_name: Mate
full_name: Gerencser, Mate
id: 44ECEDF2-F248-11E8-B48F-1D18A9856A87
last_name: Gerencser
- first_name: István
full_name: Gyöngy, István
last_name: Gyöngy
citation:
ama: Gerencser M, Gyöngy I. Localization errors in solving stochastic partial differential
equations in the whole space. Mathematics of Computation. 2017;86(307):2373-2397.
doi:10.1090/mcom/3201
apa: Gerencser, M., & Gyöngy, I. (2017). Localization errors in solving stochastic
partial differential equations in the whole space. Mathematics of Computation.
American Mathematical Society. https://doi.org/10.1090/mcom/3201
chicago: Gerencser, Mate, and István Gyöngy. “Localization Errors in Solving Stochastic
Partial Differential Equations in the Whole Space.” Mathematics of Computation.
American Mathematical Society, 2017. https://doi.org/10.1090/mcom/3201.
ieee: M. Gerencser and I. Gyöngy, “Localization errors in solving stochastic partial
differential equations in the whole space,” Mathematics of Computation,
vol. 86, no. 307. American Mathematical Society, pp. 2373–2397, 2017.
ista: Gerencser M, Gyöngy I. 2017. Localization errors in solving stochastic partial
differential equations in the whole space. Mathematics of Computation. 86(307),
2373–2397.
mla: Gerencser, Mate, and István Gyöngy. “Localization Errors in Solving Stochastic
Partial Differential Equations in the Whole Space.” Mathematics of Computation,
vol. 86, no. 307, American Mathematical Society, 2017, pp. 2373–97, doi:10.1090/mcom/3201.
short: M. Gerencser, I. Gyöngy, Mathematics of Computation 86 (2017) 2373–2397.
date_created: 2018-12-11T11:47:40Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2021-01-12T08:07:26Z
day: '01'
department:
- _id: JaMa
doi: 10.1090/mcom/3201
intvolume: ' 86'
issue: '307'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1508.05535
month: '01'
oa: 1
oa_version: Submitted Version
page: 2373 - 2397
publication: Mathematics of Computation
publication_identifier:
issn:
- '00255718'
publication_status: published
publisher: American Mathematical Society
publist_id: '7144'
quality_controlled: '1'
scopus_import: 1
status: public
title: Localization errors in solving stochastic partial differential equations in
the whole space
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 86
year: '2017'
...
---
_id: '6426'
abstract:
- lang: eng
text: Synchronous programs are easy to specify because the side effects of an operation
are finished by the time the invocation of the operation returns to the caller.
Asynchronous programs, on the other hand, are difficult to specify because there
are side effects due to pending computation scheduled as a result of the invocation
of an operation. They are also difficult to verify because of the large number
of possible interleavings of concurrent asynchronous computation threads. We show
that specifications and correctness proofs for asynchronous programs can be structured
by introducing the fiction, for proof purposes, that intermediate, non-quiescent
states of asynchronous operations can be ignored. Then, the task of specification
becomes relatively simple and the task of verification can be naturally decomposed
into smaller sub-tasks. The sub-tasks iteratively summarize, guided by the structure
of an asynchronous program, the atomic effect of non-atomic operations and the
synchronous effect of asynchronous operations. This structuring of specifications
and proofs corresponds to the introduction of multiple layers of stepwise refinement
for asynchronous programs. We present the first proof rule, called synchronization,
to reduce asynchronous invocations on a lower layer to synchronous invocations
on a higher layer. We implemented our proof method in CIVL and evaluated it on
a collection of benchmark programs.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Bernhard
full_name: Kragl, Bernhard
id: 320FC952-F248-11E8-B48F-1D18A9856A87
last_name: Kragl
orcid: 0000-0001-7745-9117
- first_name: Shaz
full_name: Qadeer, Shaz
last_name: Qadeer
citation:
ama: Henzinger TA, Kragl B, Qadeer S. Synchronizing the Asynchronous. IST
Austria; 2017. doi:10.15479/AT:IST-2018-853-v2-2
apa: Henzinger, T. A., Kragl, B., & Qadeer, S. (2017). Synchronizing the
asynchronous. IST Austria. https://doi.org/10.15479/AT:IST-2018-853-v2-2
chicago: Henzinger, Thomas A, Bernhard Kragl, and Shaz Qadeer. Synchronizing
the Asynchronous. IST Austria, 2017. https://doi.org/10.15479/AT:IST-2018-853-v2-2.
ieee: T. A. Henzinger, B. Kragl, and S. Qadeer, Synchronizing the asynchronous.
IST Austria, 2017.
ista: Henzinger TA, Kragl B, Qadeer S. 2017. Synchronizing the asynchronous, IST
Austria, 28p.
mla: Henzinger, Thomas A., et al. Synchronizing the Asynchronous. IST Austria,
2017, doi:10.15479/AT:IST-2018-853-v2-2.
short: T.A. Henzinger, B. Kragl, S. Qadeer, Synchronizing the Asynchronous, IST
Austria, 2017.
date_created: 2019-05-13T08:15:55Z
date_published: 2017-08-04T00:00:00Z
date_updated: 2023-02-21T16:59:21Z
day: '04'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2018-853-v2-2
file:
- access_level: open_access
checksum: b48d42725182d7ca10107a118815f4cf
content_type: application/pdf
creator: dernst
date_created: 2019-05-13T08:14:44Z
date_updated: 2020-07-14T12:47:30Z
file_id: '6431'
file_name: main(1).pdf
file_size: 971347
relation: main_file
file_date_updated: 2020-07-14T12:47:30Z
has_accepted_license: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: '28'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
related_material:
record:
- id: '133'
relation: later_version
status: public
status: public
title: Synchronizing the asynchronous
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '644'
abstract:
- lang: eng
text: An instance of the valued constraint satisfaction problem (VCSP) is given
by a finite set of variables, a finite domain of labels, and a sum of functions,
each function depending on a subset of the variables. Each function can take finite
values specifying costs of assignments of labels to its variables or the infinite
value, which indicates an infeasible assignment. The goal is to find an assignment
of labels to the variables that minimizes the sum. We study, assuming that P 6=
NP, how the complexity of this very general problem depends on the set of functions
allowed in the instances, the so-called constraint language. The case when all
allowed functions take values in f0;1g corresponds to ordinary CSPs, where one
deals only with the feasibility issue, and there is no optimization. This case
is the subject of the algebraic CSP dichotomy conjecture predicting for which
constraint languages CSPs are tractable (i.e., solvable in polynomial time) and
for which they are NP-hard. The case when all allowed functions take only finite
values corresponds to a finitevalued CSP, where the feasibility aspect is trivial
and one deals only with the optimization issue. The complexity of finite-valued
CSPs was fully classified by Thapper and Živný. An algebraic necessary condition
for tractability of a general-valued CSP with a fixed constraint language was
recently given by Kozik and Ochremiak. As our main result, we prove that if a
constraint language satisfies this algebraic necessary condition, and the feasibility
CSP (i.e., the problem of deciding whether a given instance has a feasible solution)
corresponding to the VCSP with this language is tractable, then the VCSP is tractable.
The algorithm is a simple combination of the assumed algorithm for the feasibility
CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy
for ordinary CSPs would imply a dichotomy for general-valued CSPs.
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Andrei
full_name: Krokhin, Andrei
last_name: Krokhin
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
ama: Kolmogorov V, Krokhin A, Rolinek M. The complexity of general-valued CSPs.
SIAM Journal on Computing. 2017;46(3):1087-1110. doi:10.1137/16M1091836
apa: Kolmogorov, V., Krokhin, A., & Rolinek, M. (2017). The complexity of general-valued
CSPs. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/16M1091836
chicago: Kolmogorov, Vladimir, Andrei Krokhin, and Michal Rolinek. “The Complexity
of General-Valued CSPs.” SIAM Journal on Computing. SIAM, 2017. https://doi.org/10.1137/16M1091836.
ieee: V. Kolmogorov, A. Krokhin, and M. Rolinek, “The complexity of general-valued
CSPs,” SIAM Journal on Computing, vol. 46, no. 3. SIAM, pp. 1087–1110,
2017.
ista: Kolmogorov V, Krokhin A, Rolinek M. 2017. The complexity of general-valued
CSPs. SIAM Journal on Computing. 46(3), 1087–1110.
mla: Kolmogorov, Vladimir, et al. “The Complexity of General-Valued CSPs.” SIAM
Journal on Computing, vol. 46, no. 3, SIAM, 2017, pp. 1087–110, doi:10.1137/16M1091836.
short: V. Kolmogorov, A. Krokhin, M. Rolinek, SIAM Journal on Computing 46 (2017)
1087–1110.
date_created: 2018-12-11T11:47:40Z
date_published: 2017-06-29T00:00:00Z
date_updated: 2023-02-23T10:07:49Z
day: '29'
department:
- _id: VlKo
doi: 10.1137/16M1091836
ec_funded: 1
intvolume: ' 46'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1502.07327
month: '06'
oa: 1
oa_version: Preprint
page: 1087 - 1110
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: SIAM Journal on Computing
publication_status: published
publisher: SIAM
publist_id: '7138'
quality_controlled: '1'
related_material:
record:
- id: '1637'
relation: other
status: public
scopus_import: 1
status: public
title: The complexity of general-valued CSPs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 46
year: '2017'
...
---
_id: '645'
abstract:
- lang: eng
text: Markov decision processes (MDPs) are standard models for probabilistic systems
with non-deterministic behaviours. Long-run average rewards provide a mathematically
elegant formalism for expressing long term performance. Value iteration (VI) is
one of the simplest and most efficient algorithmic approaches to MDPs with other
properties, such as reachability objectives. Unfortunately, a naive extension
of VI does not work for MDPs with long-run average rewards, as there is no known
stopping criterion. In this work our contributions are threefold. (1) We refute
a conjecture related to stopping criteria for MDPs with long-run average rewards.
(2) We present two practical algorithms for MDPs with long-run average rewards
based on VI. First, we show that a combination of applying VI locally for each
maximal end-component (MEC) and VI for reachability objectives can provide approximation
guarantees. Second, extending the above approach with a simulation-guided on-demand
variant of VI, we present an anytime algorithm that is able to deal with very
large models. (3) Finally, we present experimental results showing that our methods
significantly outperform the standard approaches on several benchmarks.
alternative_title:
- LNCS
author:
- first_name: Pranav
full_name: Ashok, Pranav
last_name: Ashok
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Tobias
full_name: Meggendorfer, Tobias
last_name: Meggendorfer
citation:
ama: 'Ashok P, Chatterjee K, Daca P, Kretinsky J, Meggendorfer T. Value iteration
for long run average reward in markov decision processes. In: Majumdar R, Kunčak
V, eds. Vol 10426. Springer; 2017:201-221. doi:10.1007/978-3-319-63387-9_10'
apa: 'Ashok, P., Chatterjee, K., Daca, P., Kretinsky, J., & Meggendorfer, T.
(2017). Value iteration for long run average reward in markov decision processes.
In R. Majumdar & V. Kunčak (Eds.) (Vol. 10426, pp. 201–221). Presented at
the CAV: Computer Aided Verification, Heidelberg, Germany: Springer. https://doi.org/10.1007/978-3-319-63387-9_10'
chicago: Ashok, Pranav, Krishnendu Chatterjee, Przemyslaw Daca, Jan Kretinsky, and
Tobias Meggendorfer. “Value Iteration for Long Run Average Reward in Markov Decision
Processes.” edited by Rupak Majumdar and Viktor Kunčak, 10426:201–21. Springer,
2017. https://doi.org/10.1007/978-3-319-63387-9_10.
ieee: 'P. Ashok, K. Chatterjee, P. Daca, J. Kretinsky, and T. Meggendorfer, “Value
iteration for long run average reward in markov decision processes,” presented
at the CAV: Computer Aided Verification, Heidelberg, Germany, 2017, vol. 10426,
pp. 201–221.'
ista: 'Ashok P, Chatterjee K, Daca P, Kretinsky J, Meggendorfer T. 2017. Value iteration
for long run average reward in markov decision processes. CAV: Computer Aided
Verification, LNCS, vol. 10426, 201–221.'
mla: Ashok, Pranav, et al. Value Iteration for Long Run Average Reward in Markov
Decision Processes. Edited by Rupak Majumdar and Viktor Kunčak, vol. 10426,
Springer, 2017, pp. 201–21, doi:10.1007/978-3-319-63387-9_10.
short: P. Ashok, K. Chatterjee, P. Daca, J. Kretinsky, T. Meggendorfer, in:, R.
Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 201–221.
conference:
end_date: 2017-07-28
location: Heidelberg, Germany
name: 'CAV: Computer Aided Verification'
start_date: 2017-07-24
date_created: 2018-12-11T11:47:41Z
date_published: 2017-07-13T00:00:00Z
date_updated: 2021-01-12T08:07:32Z
day: '13'
department:
- _id: KrCh
doi: 10.1007/978-3-319-63387-9_10
ec_funded: 1
editor:
- first_name: Rupak
full_name: Majumdar, Rupak
last_name: Majumdar
- first_name: Viktor
full_name: Kunčak, Viktor
last_name: Kunčak
intvolume: ' 10426'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1705.02326
month: '07'
oa: 1
oa_version: Submitted Version
page: 201 - 221
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication_identifier:
isbn:
- 978-331963386-2
publication_status: published
publisher: Springer
publist_id: '7135'
quality_controlled: '1'
scopus_import: 1
status: public
title: Value iteration for long run average reward in markov decision processes
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10426
year: '2017'
...
---
_id: '646'
abstract:
- lang: eng
text: We present a novel convex relaxation and a corresponding inference algorithm
for the non-binary discrete tomography problem, that is, reconstructing discrete-valued
images from few linear measurements. In contrast to state of the art approaches
that split the problem into a continuous reconstruction problem for the linear
measurement constraints and a discrete labeling problem to enforce discrete-valued
reconstructions, we propose a joint formulation that addresses both problems simultaneously,
resulting in a tighter convex relaxation. For this purpose a constrained graphical
model is set up and evaluated using a novel relaxation optimized by dual decomposition.
We evaluate our approach experimentally and show superior solutions both mathematically
(tighter relaxation) and experimentally in comparison to previously proposed relaxations.
alternative_title:
- LNCS
author:
- first_name: Jan
full_name: Kuske, Jan
last_name: Kuske
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Stefanie
full_name: Petra, Stefanie
last_name: Petra
citation:
ama: 'Kuske J, Swoboda P, Petra S. A novel convex relaxation for non binary discrete
tomography. In: Lauze F, Dong Y, Bjorholm Dahl A, eds. Vol 10302. Springer; 2017:235-246.
doi:10.1007/978-3-319-58771-4_19'
apa: 'Kuske, J., Swoboda, P., & Petra, S. (2017). A novel convex relaxation
for non binary discrete tomography. In F. Lauze, Y. Dong, & A. Bjorholm Dahl
(Eds.) (Vol. 10302, pp. 235–246). Presented at the SSVM: Scale Space and Variational
Methods in Computer Vision, Kolding, Denmark: Springer. https://doi.org/10.1007/978-3-319-58771-4_19'
chicago: Kuske, Jan, Paul Swoboda, and Stefanie Petra. “A Novel Convex Relaxation
for Non Binary Discrete Tomography.” edited by François Lauze, Yiqiu Dong, and
Anders Bjorholm Dahl, 10302:235–46. Springer, 2017. https://doi.org/10.1007/978-3-319-58771-4_19.
ieee: 'J. Kuske, P. Swoboda, and S. Petra, “A novel convex relaxation for non binary
discrete tomography,” presented at the SSVM: Scale Space and Variational Methods
in Computer Vision, Kolding, Denmark, 2017, vol. 10302, pp. 235–246.'
ista: 'Kuske J, Swoboda P, Petra S. 2017. A novel convex relaxation for non binary
discrete tomography. SSVM: Scale Space and Variational Methods in Computer Vision,
LNCS, vol. 10302, 235–246.'
mla: Kuske, Jan, et al. A Novel Convex Relaxation for Non Binary Discrete Tomography.
Edited by François Lauze et al., vol. 10302, Springer, 2017, pp. 235–46, doi:10.1007/978-3-319-58771-4_19.
short: J. Kuske, P. Swoboda, S. Petra, in:, F. Lauze, Y. Dong, A. Bjorholm Dahl
(Eds.), Springer, 2017, pp. 235–246.
conference:
end_date: 2017-06-08
location: Kolding, Denmark
name: 'SSVM: Scale Space and Variational Methods in Computer Vision'
start_date: 2017-06-04
date_created: 2018-12-11T11:47:41Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2021-01-12T08:07:34Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-319-58771-4_19
ec_funded: 1
editor:
- first_name: François
full_name: Lauze, François
last_name: Lauze
- first_name: Yiqiu
full_name: Dong, Yiqiu
last_name: Dong
- first_name: Anders
full_name: Bjorholm Dahl, Anders
last_name: Bjorholm Dahl
intvolume: ' 10302'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1703.03769
month: '06'
oa: 1
oa_version: Submitted Version
page: 235 - 246
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
isbn:
- 978-331958770-7
publication_status: published
publisher: Springer
publist_id: '7132'
quality_controlled: '1'
scopus_import: 1
status: public
title: A novel convex relaxation for non binary discrete tomography
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10302
year: '2017'
...
---
_id: '647'
abstract:
- lang: eng
text: Despite researchers’ efforts in the last couple of decades, reachability analysis
is still a challenging problem even for linear hybrid systems. Among the existing
approaches, the most practical ones are mainly based on bounded-time reachable
set over-approximations. For the purpose of unbounded-time analysis, one important
strategy is to abstract the original system and find an invariant for the abstraction.
In this paper, we propose an approach to constructing a new kind of abstraction
called conic abstraction for affine hybrid systems, and to computing reachable
sets based on this abstraction. The essential feature of a conic abstraction is
that it partitions the state space of a system into a set of convex polyhedral
cones which is derived from a uniform conic partition of the derivative space.
Such a set of polyhedral cones is able to cut all trajectories of the system into
almost straight segments so that every segment of a reach pipe in a polyhedral
cone tends to be straight as well, and hence can be over-approximated tightly
by polyhedra using similar techniques as HyTech or PHAVer. In particular, for
diagonalizable affine systems, our approach can guarantee to find an invariant
for unbounded reachable sets, which is beyond the capability of bounded-time reachability
analysis tools. We implemented the approach in a tool and experiments on benchmarks
show that our approach is more powerful than SpaceEx and PHAVer in dealing with
diagonalizable systems.
alternative_title:
- LNCS
author:
- first_name: Sergiy
full_name: Bogomolov, Sergiy
id: 369D9A44-F248-11E8-B48F-1D18A9856A87
last_name: Bogomolov
orcid: 0000-0002-0686-0365
- first_name: Mirco
full_name: Giacobbe, Mirco
id: 3444EA5E-F248-11E8-B48F-1D18A9856A87
last_name: Giacobbe
orcid: 0000-0001-8180-0904
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Hui
full_name: Kong, Hui
id: 3BDE25AA-F248-11E8-B48F-1D18A9856A87
last_name: Kong
orcid: 0000-0002-3066-6941
citation:
ama: 'Bogomolov S, Giacobbe M, Henzinger TA, Kong H. Conic abstractions for hybrid
systems. In: Vol 10419. Springer; 2017:116-132. doi:10.1007/978-3-319-65765-3_7'
apa: 'Bogomolov, S., Giacobbe, M., Henzinger, T. A., & Kong, H. (2017). Conic
abstractions for hybrid systems (Vol. 10419, pp. 116–132). Presented at the FORMATS:
Formal Modelling and Analysis of Timed Systems, Berlin, Germany: Springer. https://doi.org/10.1007/978-3-319-65765-3_7'
chicago: Bogomolov, Sergiy, Mirco Giacobbe, Thomas A Henzinger, and Hui Kong. “Conic
Abstractions for Hybrid Systems,” 10419:116–32. Springer, 2017. https://doi.org/10.1007/978-3-319-65765-3_7.
ieee: 'S. Bogomolov, M. Giacobbe, T. A. Henzinger, and H. Kong, “Conic abstractions
for hybrid systems,” presented at the FORMATS: Formal Modelling and Analysis of
Timed Systems, Berlin, Germany, 2017, vol. 10419, pp. 116–132.'
ista: 'Bogomolov S, Giacobbe M, Henzinger TA, Kong H. 2017. Conic abstractions for
hybrid systems. FORMATS: Formal Modelling and Analysis of Timed Systems, LNCS,
vol. 10419, 116–132.'
mla: Bogomolov, Sergiy, et al. Conic Abstractions for Hybrid Systems. Vol.
10419, Springer, 2017, pp. 116–32, doi:10.1007/978-3-319-65765-3_7.
short: S. Bogomolov, M. Giacobbe, T.A. Henzinger, H. Kong, in:, Springer, 2017,
pp. 116–132.
conference:
end_date: 2017-09-07
location: Berlin, Germany
name: 'FORMATS: Formal Modelling and Analysis of Timed Systems'
start_date: 2017-09-05
date_created: 2018-12-11T11:47:41Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2023-09-07T12:53:00Z
day: '01'
ddc:
- '005'
department:
- _id: ToHe
doi: 10.1007/978-3-319-65765-3_7
file:
- access_level: open_access
checksum: faf546914ba29bcf9974ee36b6b16750
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:38Z
date_updated: 2020-07-14T12:47:31Z
file_id: '4956'
file_name: IST-2017-831-v1+1_main.pdf
file_size: 3806864
relation: main_file
file_date_updated: 2020-07-14T12:47:31Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
page: 116 - 132
project:
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
publication_identifier:
isbn:
- 978-331965764-6
publication_status: published
publisher: Springer
publist_id: '7129'
pubrep_id: '831'
quality_controlled: '1'
related_material:
record:
- id: '6894'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Conic abstractions for hybrid systems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: '10419 '
year: '2017'
...
---
_id: '648'
abstract:
- lang: eng
text: 'Pseudoentropy has found a lot of important applications to cryptography and
complexity theory. In this paper we focus on the foundational problem that has
not been investigated so far, namely by how much pseudoentropy (the amount seen
by computationally bounded attackers) differs from its information-theoretic counterpart
(seen by unbounded observers), given certain limits on attacker’s computational
power? We provide the following answer for HILL pseudoentropy, which exhibits
a threshold behavior around the size exponential in the entropy amount:– If the
attacker size (s) and advantage () satisfy s (formula presented) where k is the
claimed amount of pseudoentropy, then the pseudoentropy boils down to the information-theoretic
smooth entropy. – If s (formula presented) then pseudoentropy could be arbitrarily
bigger than the information-theoretic smooth entropy. Besides answering the posted
question, we show an elegant application of our result to the complexity theory,
namely that it implies the clas-sical result on the existence of functions hard
to approximate (due to Pippenger). In our approach we utilize non-constructive
techniques: the duality of linear programming and the probabilistic method.'
alternative_title:
- LNCS
author:
- first_name: Maciej
full_name: Skórski, Maciej
id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
last_name: Skórski
citation:
ama: 'Skórski M. On the complexity of breaking pseudoentropy. In: Jäger G, Steila
S, eds. Vol 10185. Springer; 2017:600-613. doi:10.1007/978-3-319-55911-7_43'
apa: 'Skórski, M. (2017). On the complexity of breaking pseudoentropy. In G. Jäger
& S. Steila (Eds.) (Vol. 10185, pp. 600–613). Presented at the TAMC: Theory
and Applications of Models of Computation, Bern, Switzerland: Springer. https://doi.org/10.1007/978-3-319-55911-7_43'
chicago: Skórski, Maciej. “On the Complexity of Breaking Pseudoentropy.” edited
by Gerhard Jäger and Silvia Steila, 10185:600–613. Springer, 2017. https://doi.org/10.1007/978-3-319-55911-7_43.
ieee: 'M. Skórski, “On the complexity of breaking pseudoentropy,” presented at the
TAMC: Theory and Applications of Models of Computation, Bern, Switzerland, 2017,
vol. 10185, pp. 600–613.'
ista: 'Skórski M. 2017. On the complexity of breaking pseudoentropy. TAMC: Theory
and Applications of Models of Computation, LNCS, vol. 10185, 600–613.'
mla: Skórski, Maciej. On the Complexity of Breaking Pseudoentropy. Edited
by Gerhard Jäger and Silvia Steila, vol. 10185, Springer, 2017, pp. 600–13, doi:10.1007/978-3-319-55911-7_43.
short: M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 600–613.
conference:
end_date: 2017-04-22
location: Bern, Switzerland
name: 'TAMC: Theory and Applications of Models of Computation'
start_date: 2017-04-20
date_created: 2018-12-11T11:47:42Z
date_published: 2017-04-01T00:00:00Z
date_updated: 2021-01-12T08:07:39Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-55911-7_43
editor:
- first_name: Gerhard
full_name: Jäger, Gerhard
last_name: Jäger
- first_name: Silvia
full_name: Steila, Silvia
last_name: Steila
intvolume: ' 10185'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/1186.pdf
month: '04'
oa: 1
oa_version: Submitted Version
page: 600 - 613
publication_identifier:
isbn:
- 978-331955910-0
publication_status: published
publisher: Springer
publist_id: '7125'
quality_controlled: '1'
scopus_import: 1
status: public
title: On the complexity of breaking pseudoentropy
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10185
year: '2017'
...
---
_id: '650'
abstract:
- lang: eng
text: 'In this work we present a short and unified proof for the Strong and Weak
Regularity Lemma, based on the cryptographic tech-nique called low-complexity
approximations. In short, both problems reduce to a task of finding constructively
an approximation for a certain target function under a class of distinguishers
(test functions), where dis-tinguishers are combinations of simple rectangle-indicators.
In our case these approximations can be learned by a simple iterative procedure,
which yields a unified and simple proof, achieving for any graph with density
d and any approximation parameter the partition size. The novelty in our proof
is: (a) a simple approach which yields both strong and weaker variant, and (b)
improvements when d = o(1). At an abstract level, our proof can be seen a refinement
and simplification of the “analytic” proof given by Lovasz and Szegedy.'
alternative_title:
- LNCS
author:
- first_name: Maciej
full_name: Skórski, Maciej
id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
last_name: Skórski
citation:
ama: 'Skórski M. A cryptographic view of regularity lemmas: Simpler unified proofs
and refined bounds. In: Jäger G, Steila S, eds. Vol 10185. Springer; 2017:586-599.
doi:10.1007/978-3-319-55911-7_42'
apa: 'Skórski, M. (2017). A cryptographic view of regularity lemmas: Simpler unified
proofs and refined bounds. In G. Jäger & S. Steila (Eds.) (Vol. 10185, pp.
586–599). Presented at the TAMC: Theory and Applications of Models of Computation,
Bern, Switzerland: Springer. https://doi.org/10.1007/978-3-319-55911-7_42'
chicago: 'Skórski, Maciej. “A Cryptographic View of Regularity Lemmas: Simpler Unified
Proofs and Refined Bounds.” edited by Gerhard Jäger and Silvia Steila, 10185:586–99.
Springer, 2017. https://doi.org/10.1007/978-3-319-55911-7_42.'
ieee: 'M. Skórski, “A cryptographic view of regularity lemmas: Simpler unified proofs
and refined bounds,” presented at the TAMC: Theory and Applications of Models
of Computation, Bern, Switzerland, 2017, vol. 10185, pp. 586–599.'
ista: 'Skórski M. 2017. A cryptographic view of regularity lemmas: Simpler unified
proofs and refined bounds. TAMC: Theory and Applications of Models of Computation,
LNCS, vol. 10185, 586–599.'
mla: 'Skórski, Maciej. A Cryptographic View of Regularity Lemmas: Simpler Unified
Proofs and Refined Bounds. Edited by Gerhard Jäger and Silvia Steila, vol.
10185, Springer, 2017, pp. 586–99, doi:10.1007/978-3-319-55911-7_42.'
short: M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 586–599.
conference:
end_date: 2017-04-22
location: Bern, Switzerland
name: 'TAMC: Theory and Applications of Models of Computation'
start_date: 2017-04-20
date_created: 2018-12-11T11:47:42Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2021-01-12T08:07:46Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-55911-7_42
editor:
- first_name: Gerhard
full_name: Jäger, Gerhard
last_name: Jäger
- first_name: Silvia
full_name: Steila, Silvia
last_name: Steila
intvolume: ' 10185'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/965.pdf
month: '01'
oa: 1
oa_version: Submitted Version
page: 586 - 599
publication_identifier:
issn:
- '03029743'
publication_status: published
publisher: Springer
publist_id: '7119'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'A cryptographic view of regularity lemmas: Simpler unified proofs and refined
bounds'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10185
year: '2017'
...
---
_id: '6517'
abstract:
- lang: eng
text: A (possibly degenerate) drawing of a graph G in the plane is approximable
by an embedding if it can be turned into an embedding by an arbitrarily small
perturbation. We show that testing, whether a drawing of a planar graph G in the
plane is approximable by an embedding, can be carried out in polynomial time,
if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation
system (or equivalently the faces) of the embedding of G and the choice of outer
face are fixed. In other words, we show that c-planarity with embedded pipes is
tractable for graphs with fixed embeddings. To the best of our knowledge an analogous
result was previously known essentially only when G is a cycle.
article_number: '34'
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
citation:
ama: 'Fulek R. Embedding graphs into embedded graphs. In: Vol 92. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ISAAC.2017.34'
apa: 'Fulek, R. (2017). Embedding graphs into embedded graphs (Vol. 92). Presented
at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ISAAC.2017.34'
chicago: Fulek, Radoslav. “Embedding Graphs into Embedded Graphs,” Vol. 92. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ISAAC.2017.34.
ieee: 'R. Fulek, “Embedding graphs into embedded graphs,” presented at the ISAAC:
International Symposium on Algorithms and Computation, Phuket, Thailand, 2017,
vol. 92.'
ista: 'Fulek R. 2017. Embedding graphs into embedded graphs. ISAAC: International
Symposium on Algorithms and Computation vol. 92, 34.'
mla: Fulek, Radoslav. Embedding Graphs into Embedded Graphs. Vol. 92, 34,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ISAAC.2017.34.
short: R. Fulek, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-12-22
location: Phuket, Thailand
name: 'ISAAC: International Symposium on Algorithms and Computation'
start_date: 2017-12-09
date_created: 2019-06-04T12:11:52Z
date_published: 2017-12-01T00:00:00Z
date_updated: 2021-01-12T08:07:51Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPICS.ISAAC.2017.34
ec_funded: 1
file:
- access_level: open_access
checksum: fc7a643e29621c8bbe49d36b39081f31
content_type: application/pdf
creator: kschuh
date_created: 2019-06-04T12:20:35Z
date_updated: 2020-07-14T12:47:33Z
file_id: '6518'
file_name: 2017_LIPIcs-Fulek.pdf
file_size: 588982
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 92'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Embedding graphs into embedded graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 92
year: '2017'
...
---
_id: '6519'
abstract:
- lang: eng
text: 'Graph games with omega-regular winning conditions provide a mathematical
framework to analyze a wide range of problems in the analysis of reactive systems
and programs (such as the synthesis of reactive systems, program repair, and the
verification of branching time properties). Parity conditions are canonical forms
to specify omega-regular winning conditions. Graph games with parity conditions
are equivalent to mu-calculus model checking, and thus a very important algorithmic
problem. Symbolic algorithms are of great significance because they provide scalable
algorithms for the analysis of large finite-state systems, as well as algorithms
for the analysis of infinite-state systems with finite quotient. A set-based symbolic
algorithm uses the basic set operations and the one-step predecessor operators.
We consider graph games with n vertices and parity conditions with c priorities
(equivalently, a mu-calculus formula with c alternations of least and greatest
fixed points). While many explicit algorithms exist for graph games with parity
conditions, for set-based symbolic algorithms there are only two algorithms (notice
that we use space to refer to the number of sets stored by a symbolic algorithm):
(a) the basic algorithm that requires O(n^c) symbolic operations and linear space;
and (b) an improved algorithm that requires O(n^{c/2+1}) symbolic operations but
also O(n^{c/2+1}) space (i.e., exponential space). In this work we present two
set-based symbolic algorithms for parity games: (a) our first algorithm requires
O(n^{c/2+1}) symbolic operations and only requires linear space; and (b) developing
on our first algorithm, we present an algorithm that requires O(n^{c/3+1}) symbolic
operations and only linear space. We also present the first linear space set-based
symbolic algorithm for parity games that requires at most a sub-exponential number
of symbolic operations. '
article_number: '18'
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: Wolfgang
full_name: Dvorák, Wolfgang
last_name: Dvorá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: Veronika
full_name: Loitzenbauer, Veronika
last_name: Loitzenbauer
citation:
ama: 'Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. Improved set-based symbolic
algorithms for parity games. In: Vol 82. Schloss Dagstuhl -Leibniz-Zentrum fuer
Informatik; 2017. doi:10.4230/LIPICS.CSL.2017.18'
apa: 'Chatterjee, K., Dvorák, W., Henzinger, M. H., & Loitzenbauer, V. (2017).
Improved set-based symbolic algorithms for parity games (Vol. 82). Presented at
the CSL: Conference on Computer Science Logic, Stockholm, Sweden: Schloss Dagstuhl
-Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPICS.CSL.2017.18'
chicago: Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Veronika
Loitzenbauer. “Improved Set-Based Symbolic Algorithms for Parity Games,” Vol.
82. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 2017. https://doi.org/10.4230/LIPICS.CSL.2017.18.
ieee: 'K. Chatterjee, W. Dvorák, M. H. Henzinger, and V. Loitzenbauer, “Improved
set-based symbolic algorithms for parity games,” presented at the CSL: Conference
on Computer Science Logic, Stockholm, Sweden, 2017, vol. 82.'
ista: 'Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. 2017. Improved set-based
symbolic algorithms for parity games. CSL: Conference on Computer Science Logic
vol. 82, 18.'
mla: Chatterjee, Krishnendu, et al. Improved Set-Based Symbolic Algorithms for
Parity Games. Vol. 82, 18, Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik,
2017, doi:10.4230/LIPICS.CSL.2017.18.
short: K. Chatterjee, W. Dvorák, M.H. Henzinger, V. Loitzenbauer, in:, Schloss Dagstuhl
-Leibniz-Zentrum fuer Informatik, 2017.
conference:
end_date: 2017-08-24
location: Stockholm, Sweden
name: 'CSL: Conference on Computer Science Logic'
start_date: 2017-08-20
date_created: 2019-06-04T12:42:43Z
date_published: 2017-08-01T00:00:00Z
date_updated: 2025-06-02T08:53:46Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.4230/LIPICS.CSL.2017.18
ec_funded: 1
file:
- access_level: open_access
checksum: 7c2c9d09970af79026d7e37d9b632ef8
content_type: application/pdf
creator: kschuh
date_created: 2019-06-04T12:56:52Z
date_updated: 2020-07-14T12:47:33Z
file_id: '6520'
file_name: 2017_LIPIcs-Chatterjee.pdf
file_size: 710185
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 82'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
publication_status: published
publisher: Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Improved set-based symbolic algorithms for parity games
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 82
year: '2017'
...
---
_id: '6526'
abstract:
- lang: eng
text: 'This paper studies the complexity of estimating Rényi divergences of discrete
distributions: p observed from samples and the baseline distribution q known a
priori. Extending the results of Acharya et al. (SODA''15) on estimating Rényi
entropy, we present improved estimation techniques together with upper and lower
bounds on the sample complexity. We show that, contrarily to estimating Rényi
entropy where a sublinear (in the alphabet size) number of samples suffices, the
sample complexity is heavily dependent on events occurring unlikely in q, and
is unbounded in general (no matter what an estimation technique is used). For
any divergence of integer order bigger than 1, we provide upper and lower bounds
on the number of samples dependent on probabilities of p and q (the lower bounds
hold for non-integer orders as well). We conclude that the worst-case sample complexity
is polynomial in the alphabet size if and only if the probabilities of q are non-negligible.
This gives theoretical insights into heuristics used in the applied literature
to handle numerical instability, which occurs for small probabilities of q. Our
result shows that they should be handled with care not only because of numerical
issues, but also because of a blow up in the sample complexity.'
article_number: '8006529'
arxiv: 1
author:
- first_name: Maciej
full_name: Skórski, Maciej
id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
last_name: Skórski
citation:
ama: 'Skórski M. On the complexity of estimating Rènyi divergences. In: 2017
IEEE International Symposium on Information Theory (ISIT). IEEE; 2017. doi:10.1109/isit.2017.8006529'
apa: 'Skórski, M. (2017). On the complexity of estimating Rènyi divergences. In
2017 IEEE International Symposium on Information Theory (ISIT). Aachen,
Germany: IEEE. https://doi.org/10.1109/isit.2017.8006529'
chicago: Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” In
2017 IEEE International Symposium on Information Theory (ISIT). IEEE, 2017.
https://doi.org/10.1109/isit.2017.8006529.
ieee: M. Skórski, “On the complexity of estimating Rènyi divergences,” in 2017
IEEE International Symposium on Information Theory (ISIT), Aachen, Germany,
2017.
ista: 'Skórski M. 2017. On the complexity of estimating Rènyi divergences. 2017
IEEE International Symposium on Information Theory (ISIT). ISIT: International
Symposium on Information Theory, 8006529.'
mla: Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” 2017
IEEE International Symposium on Information Theory (ISIT), 8006529, IEEE,
2017, doi:10.1109/isit.2017.8006529.
short: M. Skórski, in:, 2017 IEEE International Symposium on Information Theory
(ISIT), IEEE, 2017.
conference:
end_date: 2017-06-30
location: Aachen, Germany
name: 'ISIT: International Symposium on Information Theory'
start_date: 2017-06-25
date_created: 2019-06-06T12:53:09Z
date_published: 2017-08-09T00:00:00Z
date_updated: 2021-01-12T08:07:53Z
day: '09'
department:
- _id: KrPi
doi: 10.1109/isit.2017.8006529
ec_funded: 1
external_id:
arxiv:
- '1702.01666'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1702.01666
month: '08'
oa: 1
oa_version: Preprint
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 2017 IEEE International Symposium on Information Theory (ISIT)
publication_identifier:
isbn:
- '9781509040964'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: 1
status: public
title: On the complexity of estimating Rènyi divergences
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '6527'
abstract:
- lang: eng
text: "A memory-hard function (MHF) ƒn with parameter n can be computed in sequential
time and space n. Simultaneously, a high amortized parallel area-time complexity
(aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate
at which an adversary (using a custom computational device) can evaluate a security
sensitive function that still occasionally needs to be evaluated by honest users
(using an off-the-shelf general purpose device). The most prevalent examples of
such sensitive functions are Key Derivation Functions (KDFs) and password hashing
algorithms where rate limits help mitigate off-line dictionary attacks. As the
honest users' inputs to these functions are often (low-entropy) passwords special
attention is given to a class of side-channel resistant MHFs called iMHFs.\r\n\r\nEssentially
all iMHFs can be viewed as some mode of operation (making n calls to some round
function) given by a directed acyclic graph (DAG) with very low indegree. Recently,
a combinatorial property of a DAG has been identified (called \"depth-robustness\")
which results in good provable security for an iMHF based on that DAG. Depth-robust
DAGs have also proven useful in other cryptographic applications. Unfortunately,
up till now, all known very depth-robust DAGs are impractically complicated and
little is known about their exact (i.e. non-asymptotic) depth-robustness both
in theory and in practice.\r\n\r\nIn this work we build and analyze (both formally
and empirically) several exceedingly simple and efficient to navigate practical
DAGs for use in iMHFs and other applications. For each DAG we:\r\n*Prove that
their depth-robustness is asymptotically maximal.\r\n*Prove bounds of at least
3 orders of magnitude better on their exact depth-robustness compared to known
bounds for other practical iMHF.\r\n*Implement and empirically evaluate their
depth-robustness and aAT against a variety of state-of-the art (and several new)
depth-reduction and low aAT attacks. \r\nWe find that, against all attacks, the
new DAGs perform significantly better in practice than Argon2i, the most widely
deployed iMHF in practice.\r\n\r\nAlong the way we also improve the best known
empirical attacks on the aAT of Argon2i by implementing and testing several heuristic
versions of a (hitherto purely theoretical) depth-reduction attack. Finally, we
demonstrate practicality of our constructions by modifying the Argon2i code base
to use one of the new high aAT DAGs. Experimental benchmarks on a standard off-the-shelf
CPU show that the new modifications do not adversely affect the impressive throughput
of Argon2i (despite seemingly enjoying significantly higher aAT).\r\n"
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
- first_name: Ben
full_name: Harsha, Ben
last_name: Harsha
citation:
ama: 'Alwen JF, Blocki J, Harsha B. Practical graphs for optimal side-channel resistant
memory-hard functions. In: Proceedings of the 2017 ACM SIGSAC Conference on
Computer and Communications Security. ACM Press; 2017:1001-1017. doi:10.1145/3133956.3134031'
apa: 'Alwen, J. F., Blocki, J., & Harsha, B. (2017). Practical graphs for optimal
side-channel resistant memory-hard functions. In Proceedings of the 2017 ACM
SIGSAC Conference on Computer and Communications Security (pp. 1001–1017).
Dallas, TX, USA: ACM Press. https://doi.org/10.1145/3133956.3134031'
chicago: Alwen, Joel F, Jeremiah Blocki, and Ben Harsha. “Practical Graphs for Optimal
Side-Channel Resistant Memory-Hard Functions.” In Proceedings of the 2017 ACM
SIGSAC Conference on Computer and Communications Security, 1001–17. ACM Press,
2017. https://doi.org/10.1145/3133956.3134031.
ieee: J. F. Alwen, J. Blocki, and B. Harsha, “Practical graphs for optimal side-channel
resistant memory-hard functions,” in Proceedings of the 2017 ACM SIGSAC Conference
on Computer and Communications Security, Dallas, TX, USA, 2017, pp. 1001–1017.
ista: 'Alwen JF, Blocki J, Harsha B. 2017. Practical graphs for optimal side-channel
resistant memory-hard functions. Proceedings of the 2017 ACM SIGSAC Conference
on Computer and Communications Security. CCS: Conference on Computer and Communications
Security, 1001–1017.'
mla: Alwen, Joel F., et al. “Practical Graphs for Optimal Side-Channel Resistant
Memory-Hard Functions.” Proceedings of the 2017 ACM SIGSAC Conference on Computer
and Communications Security, ACM Press, 2017, pp. 1001–17, doi:10.1145/3133956.3134031.
short: J.F. Alwen, J. Blocki, B. Harsha, in:, Proceedings of the 2017 ACM SIGSAC
Conference on Computer and Communications Security, ACM Press, 2017, pp. 1001–1017.
conference:
end_date: 2017-11-03
location: Dallas, TX, USA
name: 'CCS: Conference on Computer and Communications Security'
start_date: 2017-10-30
date_created: 2019-06-06T13:21:29Z
date_published: 2017-10-30T00:00:00Z
date_updated: 2021-01-12T08:07:53Z
day: '30'
department:
- _id: KrPi
doi: 10.1145/3133956.3134031
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2017/443
month: '10'
oa: 1
oa_version: Submitted Version
page: 1001-1017
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications
Security
publication_identifier:
isbn:
- '9781450349468'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
scopus_import: 1
status: public
title: Practical graphs for optimal side-channel resistant memory-hard functions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '653'
abstract:
- lang: eng
text: The extent of heterogeneity among driver gene mutations present in naturally
occurring metastases - that is, treatment-naive metastatic disease - is largely
unknown. To address this issue, we carried out 60× whole-genome sequencing of
26 metastases from four patients with pancreatic cancer. We found that identical
mutations in known driver genes were present in every metastatic lesion for each
patient studied. Passenger gene mutations, which do not have known or predicted
functional consequences, accounted for all intratumoral heterogeneity. Even with
respect to these passenger mutations, our analysis suggests that the genetic similarity
among the founding cells of metastases was higher than that expected for any two
cells randomly taken from a normal tissue. The uniformity of known driver gene
mutations among metastases in the same patient has critical and encouraging implications
for the success of future targeted therapies in advanced-stage disease.
acknowledgement: 'We thank the Memorial Sloan Kettering Cancer Center Molecular Cytology
core facility for immunohistochemistry staining. This work was supported by Office
of Naval Research grant N00014-16-1-2914, the Bill and Melinda Gates Foundation
(OPP1148627), and a gift from B. Wu and E. Larson (M.A.N.), National Institutes
of Health grants CA179991 (C.A.I.-D. and I.B.), F31 CA180682 (A.P.M.-M.), CA43460
(B.V.), and P50 CA62924, the Monastra Foundation, the Virginia and D.K. Ludwig Fund
for Cancer Research, the Lustgarten Foundation for Pancreatic Cancer Research, the
Sol Goldman Center for Pancreatic Cancer Research, the Sol Goldman Sequencing Center,
ERC Start grant 279307: Graph Games (J.G.R., D.K., and C.K.), Austrian Science Fund
(FWF) grant P23499-N23 (J.G.R., D.K., and C.K.), and FWF NFN grant S11407-N23 RiSE/SHiNE
(J.G.R., D.K., and C.K.).'
article_processing_charge: No
article_type: original
author:
- first_name: Alvin
full_name: Makohon Moore, Alvin
last_name: Makohon Moore
- first_name: Ming
full_name: Zhang, Ming
last_name: Zhang
- first_name: Johannes
full_name: Reiter, Johannes
id: 4A918E98-F248-11E8-B48F-1D18A9856A87
last_name: Reiter
orcid: 0000-0002-0170-7353
- first_name: Ivana
full_name: Božić, Ivana
last_name: Božić
- first_name: Benjamin
full_name: Allen, Benjamin
last_name: Allen
- first_name: Deepanjan
full_name: Kundu, Deepanjan
id: 1d4c0f4f-e8a3-11ec-a351-e36772758c45
last_name: Kundu
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Fay
full_name: Wong, Fay
last_name: Wong
- first_name: Yuchen
full_name: Jiao, Yuchen
last_name: Jiao
- first_name: Zachary
full_name: Kohutek, Zachary
last_name: Kohutek
- first_name: Jungeui
full_name: Hong, Jungeui
last_name: Hong
- first_name: Marc
full_name: Attiyeh, Marc
last_name: Attiyeh
- first_name: Breanna
full_name: Javier, Breanna
last_name: Javier
- first_name: Laura
full_name: Wood, Laura
last_name: Wood
- first_name: Ralph
full_name: Hruban, Ralph
last_name: Hruban
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
- first_name: Nickolas
full_name: Papadopoulos, Nickolas
last_name: Papadopoulos
- first_name: Kenneth
full_name: Kinzler, Kenneth
last_name: Kinzler
- first_name: Bert
full_name: Vogelstein, Bert
last_name: Vogelstein
- first_name: Christine
full_name: Iacobuzio Donahue, Christine
last_name: Iacobuzio Donahue
citation:
ama: Makohon Moore A, Zhang M, Reiter J, et al. Limited heterogeneity of known driver
gene mutations among the metastases of individual patients with pancreatic cancer.
Nature Genetics. 2017;49(3):358-366. doi:10.1038/ng.3764
apa: Makohon Moore, A., Zhang, M., Reiter, J., Božić, I., Allen, B., Kundu, D.,
… Iacobuzio Donahue, C. (2017). Limited heterogeneity of known driver gene mutations
among the metastases of individual patients with pancreatic cancer. Nature
Genetics. Nature Publishing Group. https://doi.org/10.1038/ng.3764
chicago: Makohon Moore, Alvin, Ming Zhang, Johannes Reiter, Ivana Božić, Benjamin
Allen, Deepanjan Kundu, Krishnendu Chatterjee, et al. “Limited Heterogeneity of
Known Driver Gene Mutations among the Metastases of Individual Patients with Pancreatic
Cancer.” Nature Genetics. Nature Publishing Group, 2017. https://doi.org/10.1038/ng.3764.
ieee: A. Makohon Moore et al., “Limited heterogeneity of known driver gene
mutations among the metastases of individual patients with pancreatic cancer,”
Nature Genetics, vol. 49, no. 3. Nature Publishing Group, pp. 358–366,
2017.
ista: Makohon Moore A, Zhang M, Reiter J, Božić I, Allen B, Kundu D, Chatterjee
K, Wong F, Jiao Y, Kohutek Z, Hong J, Attiyeh M, Javier B, Wood L, Hruban R, Nowak
M, Papadopoulos N, Kinzler K, Vogelstein B, Iacobuzio Donahue C. 2017. Limited
heterogeneity of known driver gene mutations among the metastases of individual
patients with pancreatic cancer. Nature Genetics. 49(3), 358–366.
mla: Makohon Moore, Alvin, et al. “Limited Heterogeneity of Known Driver Gene Mutations
among the Metastases of Individual Patients with Pancreatic Cancer.” Nature
Genetics, vol. 49, no. 3, Nature Publishing Group, 2017, pp. 358–66, doi:10.1038/ng.3764.
short: A. Makohon Moore, M. Zhang, J. Reiter, I. Božić, B. Allen, D. Kundu, K. Chatterjee,
F. Wong, Y. Jiao, Z. Kohutek, J. Hong, M. Attiyeh, B. Javier, L. Wood, R. Hruban,
M. Nowak, N. Papadopoulos, K. Kinzler, B. Vogelstein, C. Iacobuzio Donahue, Nature
Genetics 49 (2017) 358–366.
date_created: 2018-12-11T11:47:43Z
date_published: 2017-03-01T00:00:00Z
date_updated: 2022-06-10T09:55:08Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1038/ng.3764
ec_funded: 1
external_id:
pmid:
- '28092682'
file:
- access_level: open_access
checksum: e442dc3b7420a36ec805e9bb45cc1a2e
content_type: application/pdf
creator: dernst
date_created: 2019-11-19T08:13:50Z
date_updated: 2020-07-14T12:47:33Z
file_id: '7050'
file_name: 2017_NatureGenetics_Makohon.pdf
file_size: 908099
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 49'
issue: '3'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 358 - 366
pmid: 1
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: Nature Genetics
publication_identifier:
issn:
- '10614036'
publication_status: published
publisher: Nature Publishing Group
publist_id: '7092'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Limited heterogeneity of known driver gene mutations among the metastases of
individual patients with pancreatic cancer
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 49
year: '2017'
...
---
_id: '654'
abstract:
- lang: eng
text: In November 2016, developmental biologists, synthetic biologists and engineers
gathered in Paris for a meeting called ‘Engineering the embryo’. The participants
shared an interest in exploring how synthetic systems can reveal new principles
of embryonic development, and how the in vitro manipulation and modeling of development
using stem cells can be used to integrate ideas and expertise from physics, developmental
biology and tissue engineering. As we review here, the conference pinpointed some
of the challenges arising at the intersection of these fields, along with great
enthusiasm for finding new approaches and collaborations.
author:
- first_name: Anna
full_name: Kicheva, Anna
id: 3959A2A0-F248-11E8-B48F-1D18A9856A87
last_name: Kicheva
orcid: 0000-0003-4509-4998
- first_name: Nicolas
full_name: Rivron, Nicolas
last_name: Rivron
citation:
ama: Kicheva A, Rivron N. Creating to understand – developmental biology meets engineering
in Paris. Development. 2017;144(5):733-736. doi:10.1242/dev.144915
apa: Kicheva, A., & Rivron, N. (2017). Creating to understand – developmental
biology meets engineering in Paris. Development. Company of Biologists.
https://doi.org/10.1242/dev.144915
chicago: Kicheva, Anna, and Nicolas Rivron. “Creating to Understand – Developmental
Biology Meets Engineering in Paris.” Development. Company of Biologists,
2017. https://doi.org/10.1242/dev.144915.
ieee: A. Kicheva and N. Rivron, “Creating to understand – developmental biology
meets engineering in Paris,” Development, vol. 144, no. 5. Company of Biologists,
pp. 733–736, 2017.
ista: Kicheva A, Rivron N. 2017. Creating to understand – developmental biology
meets engineering in Paris. Development. 144(5), 733–736.
mla: Kicheva, Anna, and Nicolas Rivron. “Creating to Understand – Developmental
Biology Meets Engineering in Paris.” Development, vol. 144, no. 5, Company
of Biologists, 2017, pp. 733–36, doi:10.1242/dev.144915.
short: A. Kicheva, N. Rivron, Development 144 (2017) 733–736.
date_created: 2018-12-11T11:47:44Z
date_published: 2017-03-01T00:00:00Z
date_updated: 2021-01-12T08:07:54Z
day: '01'
ddc:
- '571'
department:
- _id: AnKi
doi: 10.1242/dev.144915
ec_funded: 1
file:
- access_level: open_access
checksum: eef22a0f42a55b232cb2d1188a2322cb
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:20Z
date_updated: 2020-07-14T12:47:33Z
file_id: '5139'
file_name: IST-2018-987-v1+1_2017_KichevaRivron__Creating_to.pdf
file_size: 228206
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 144'
issue: '5'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 733 - 736
project:
- _id: B6FC0238-B512-11E9-945C-1524E6697425
call_identifier: H2020
grant_number: '680037'
name: Coordination of Patterning And Growth In the Spinal Cord
publication: Development
publication_identifier:
issn:
- '09501991'
publication_status: published
publisher: Company of Biologists
publist_id: '7089'
pubrep_id: '987'
quality_controlled: '1'
scopus_import: 1
status: public
title: Creating to understand – developmental biology meets engineering in Paris
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 144
year: '2017'
...
---
_id: '655'
abstract:
- lang: eng
text: 'The bacterial flagellum is a self-assembling nanomachine. The external flagellar
filament, several times longer than a bacterial cell body, is made of a few tens
of thousands subunits of a single protein: flagellin. A fundamental problem concerns
the molecular mechanism of how the flagellum grows outside the cell, where no
discernible energy source is available. Here, we monitored the dynamic assembly
of individual flagella using in situ labelling and real-time immunostaining of
elongating flagellar filaments. We report that the rate of flagellum growth, initially
~1,700 amino acids per second, decreases with length and that the previously proposed
chain mechanism does not contribute to the filament elongation dynamics. Inhibition
of the proton motive force-dependent export apparatus revealed a major contribution
of substrate injection in driving filament elongation. The combination of experimental
and mathematical evidence demonstrates that a simple, injection-diffusion mechanism
controls bacterial flagella growth outside the cell.'
article_number: e23136
author:
- first_name: Thibaud
full_name: Renault, Thibaud
last_name: Renault
- first_name: Anthony
full_name: Abraham, Anthony
last_name: Abraham
- first_name: Tobias
full_name: Bergmiller, Tobias
id: 2C471CFA-F248-11E8-B48F-1D18A9856A87
last_name: Bergmiller
orcid: 0000-0001-5396-4346
- first_name: Guillaume
full_name: Paradis, Guillaume
last_name: Paradis
- first_name: Simon
full_name: Rainville, Simon
last_name: Rainville
- first_name: Emmanuelle
full_name: Charpentier, Emmanuelle
last_name: Charpentier
- first_name: Calin C
full_name: Guet, Calin C
id: 47F8433E-F248-11E8-B48F-1D18A9856A87
last_name: Guet
orcid: 0000-0001-6220-2052
- first_name: Yuhai
full_name: Tu, Yuhai
last_name: Tu
- first_name: Keiichi
full_name: Namba, Keiichi
last_name: Namba
- first_name: James
full_name: Keener, James
last_name: Keener
- first_name: Tohru
full_name: Minamino, Tohru
last_name: Minamino
- first_name: Marc
full_name: Erhardt, Marc
last_name: Erhardt
citation:
ama: Renault T, Abraham A, Bergmiller T, et al. Bacterial flagella grow through
an injection diffusion mechanism. eLife. 2017;6. doi:10.7554/eLife.23136
apa: Renault, T., Abraham, A., Bergmiller, T., Paradis, G., Rainville, S., Charpentier,
E., … Erhardt, M. (2017). Bacterial flagella grow through an injection diffusion
mechanism. ELife. eLife Sciences Publications. https://doi.org/10.7554/eLife.23136
chicago: Renault, Thibaud, Anthony Abraham, Tobias Bergmiller, Guillaume Paradis,
Simon Rainville, Emmanuelle Charpentier, Calin C Guet, et al. “Bacterial Flagella
Grow through an Injection Diffusion Mechanism.” ELife. eLife Sciences Publications,
2017. https://doi.org/10.7554/eLife.23136.
ieee: T. Renault et al., “Bacterial flagella grow through an injection diffusion
mechanism,” eLife, vol. 6. eLife Sciences Publications, 2017.
ista: Renault T, Abraham A, Bergmiller T, Paradis G, Rainville S, Charpentier E,
Guet CC, Tu Y, Namba K, Keener J, Minamino T, Erhardt M. 2017. Bacterial flagella
grow through an injection diffusion mechanism. eLife. 6, e23136.
mla: Renault, Thibaud, et al. “Bacterial Flagella Grow through an Injection Diffusion
Mechanism.” ELife, vol. 6, e23136, eLife Sciences Publications, 2017, doi:10.7554/eLife.23136.
short: T. Renault, A. Abraham, T. Bergmiller, G. Paradis, S. Rainville, E. Charpentier,
C.C. Guet, Y. Tu, K. Namba, J. Keener, T. Minamino, M. Erhardt, ELife 6 (2017).
date_created: 2018-12-11T11:47:44Z
date_published: 2017-03-06T00:00:00Z
date_updated: 2021-01-12T08:07:55Z
day: '06'
ddc:
- '579'
department:
- _id: CaGu
doi: 10.7554/eLife.23136
file:
- access_level: open_access
checksum: 39e1c3e82ddac83a30422fa72fa1a383
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:53Z
date_updated: 2020-07-14T12:47:33Z
file_id: '4716'
file_name: IST-2017-904-v1+1_elife-23136-v2.pdf
file_size: 5520359
relation: main_file
- access_level: open_access
checksum: a6d542253028f52e00aa29739ddffe8f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:54Z
date_updated: 2020-07-14T12:47:33Z
file_id: '4717'
file_name: IST-2017-904-v1+2_elife-23136-figures-v2.pdf
file_size: 11242920
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 6'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
publication: eLife
publication_identifier:
issn:
- 2050084X
publication_status: published
publisher: eLife Sciences Publications
publist_id: '7082'
pubrep_id: '904'
quality_controlled: '1'
scopus_import: 1
status: public
title: Bacterial flagella grow through an injection diffusion mechanism
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6
year: '2017'
...