---
_id: '641'
abstract:
- lang: eng
text: 'We introduce two novel methods for learning parameters of graphical models
for image labelling. The following two tasks underline both methods: (i) perturb
model parameters based on given features and ground truth labelings, so as to
exactly reproduce these labelings as optima of the local polytope relaxation of
the labelling problem; (ii) train a predictor for the perturbed model parameters
so that improved model parameters can be applied to the labelling of novel data.
Our first method implements task (i) by inverse linear programming and task (ii)
using a regressor e.g. a Gaussian process. Our second approach simultaneously
solves tasks (i) and (ii) in a joint manner, while being restricted to linearly
parameterised predictors. Experiments demonstrate the merits of both approaches.'
alternative_title:
- LNCS
author:
- first_name: Vera
full_name: Trajkovska, Vera
last_name: Trajkovska
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Freddie
full_name: Åström, Freddie
last_name: Åström
- first_name: Stefanie
full_name: Petra, Stefanie
last_name: Petra
citation:
ama: 'Trajkovska V, Swoboda P, Åström F, Petra S. Graphical model parameter learning
by inverse linear programming. In: Lauze F, Dong Y, Bjorholm Dahl A, eds. Vol
10302. Springer; 2017:323-334. doi:10.1007/978-3-319-58771-4_26'
apa: 'Trajkovska, V., Swoboda, P., Åström, F., & Petra, S. (2017). Graphical
model parameter learning by inverse linear programming. In F. Lauze, Y. Dong,
& A. Bjorholm Dahl (Eds.) (Vol. 10302, pp. 323–334). 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_26'
chicago: Trajkovska, Vera, Paul Swoboda, Freddie Åström, and Stefanie Petra. “Graphical
Model Parameter Learning by Inverse Linear Programming.” edited by François Lauze,
Yiqiu Dong, and Anders Bjorholm Dahl, 10302:323–34. Springer, 2017. https://doi.org/10.1007/978-3-319-58771-4_26.
ieee: 'V. Trajkovska, P. Swoboda, F. Åström, and S. Petra, “Graphical model parameter
learning by inverse linear programming,” presented at the SSVM: Scale Space and
Variational Methods in Computer Vision, Kolding, Denmark, 2017, vol. 10302, pp.
323–334.'
ista: 'Trajkovska V, Swoboda P, Åström F, Petra S. 2017. Graphical model parameter
learning by inverse linear programming. SSVM: Scale Space and Variational Methods
in Computer Vision, LNCS, vol. 10302, 323–334.'
mla: Trajkovska, Vera, et al. Graphical Model Parameter Learning by Inverse Linear
Programming. Edited by François Lauze et al., vol. 10302, Springer, 2017,
pp. 323–34, doi:10.1007/978-3-319-58771-4_26.
short: V. Trajkovska, P. Swoboda, F. Åström, S. Petra, in:, F. Lauze, Y. Dong, A.
Bjorholm Dahl (Eds.), Springer, 2017, pp. 323–334.
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:39Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2021-01-12T08:07:23Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-319-58771-4_26
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
month: '01'
oa_version: None
page: 323 - 334
publication_identifier:
isbn:
- 978-331958770-7
publication_status: published
publisher: Springer
publist_id: '7147'
quality_controlled: '1'
scopus_import: 1
status: public
title: Graphical model parameter learning by inverse linear programming
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10302
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: '643'
abstract:
- lang: eng
text: It has been reported that nicotinamide-overload induces oxidative stress associated
with insulin resistance, the key feature of type 2 diabetes mellitus (T2DM). This
study aimed to investigate the effects of B vitamins in T2DM. Glucose tolerance
tests (GTT) were carried out in adult Sprague-Dawley rats treated with or without
cumulative doses of B vitamins. More specifically, insulin tolerance tests (ITT)
were also carried out in adult Sprague-Dawley rats treated with or without cumulative
doses of Vitamin B3. We found that cumulative Vitamin B1 and Vitamin B3 administration
significantly increased the plasma H2O2 levels associated with high insulin levels.
Only Vitamin B3 reduced muscular and hepatic glycogen contents. Cumulative administration
of nicotinic acid, another form of Vitamin B3, also significantly increased plasma
insulin level and H2O2 generation. Moreover, cumulative administration of nicotinic
acid or nicotinamide impaired glucose metabolism. This study suggested that excess
Vitamin B1 and Vitamin B3 caused oxidative stress and insulin resistance.
article_processing_charge: No
article_type: original
author:
- first_name: Wuping
full_name: Sun, Wuping
last_name: Sun
- first_name: Ming-Zhu
full_name: Zhai, Ming-Zhu
id: 34009CFA-F248-11E8-B48F-1D18A9856A87
last_name: Zhai
- first_name: Qian
full_name: Zhou, Qian
last_name: Zhou
- first_name: Chengrui
full_name: Qian, Chengrui
last_name: Qian
- first_name: Changyu
full_name: Jiang, Changyu
last_name: Jiang
citation:
ama: Sun W, Zhai M-Z, Zhou Q, Qian C, Jiang C. Effects of B vitamins overload on
plasma insulin level and hydrogen peroxide generation in rats. Chinese Journal
of Physiology. 2017;60(4):207-214. doi:10.4077/CJP.2017.BAF469
apa: Sun, W., Zhai, M.-Z., Zhou, Q., Qian, C., & Jiang, C. (2017). Effects of
B vitamins overload on plasma insulin level and hydrogen peroxide generation in
rats. Chinese Journal of Physiology. Chinese Physiological Society. https://doi.org/10.4077/CJP.2017.BAF469
chicago: Sun, Wuping, Ming-Zhu Zhai, Qian Zhou, Chengrui Qian, and Changyu Jiang.
“Effects of B Vitamins Overload on Plasma Insulin Level and Hydrogen Peroxide
Generation in Rats.” Chinese Journal of Physiology. Chinese Physiological
Society, 2017. https://doi.org/10.4077/CJP.2017.BAF469.
ieee: W. Sun, M.-Z. Zhai, Q. Zhou, C. Qian, and C. Jiang, “Effects of B vitamins
overload on plasma insulin level and hydrogen peroxide generation in rats,” Chinese
Journal of Physiology, vol. 60, no. 4. Chinese Physiological Society, pp.
207–214, 2017.
ista: Sun W, Zhai M-Z, Zhou Q, Qian C, Jiang C. 2017. Effects of B vitamins overload
on plasma insulin level and hydrogen peroxide generation in rats. Chinese Journal
of Physiology. 60(4), 207–214.
mla: Sun, Wuping, et al. “Effects of B Vitamins Overload on Plasma Insulin Level
and Hydrogen Peroxide Generation in Rats.” Chinese Journal of Physiology,
vol. 60, no. 4, Chinese Physiological Society, 2017, pp. 207–14, doi:10.4077/CJP.2017.BAF469.
short: W. Sun, M.-Z. Zhai, Q. Zhou, C. Qian, C. Jiang, Chinese Journal of Physiology
60 (2017) 207–214.
date_created: 2018-12-11T11:47:40Z
date_published: 2017-08-31T00:00:00Z
date_updated: 2021-01-12T08:07:28Z
day: '31'
ddc:
- '570'
department:
- _id: RySh
doi: 10.4077/CJP.2017.BAF469
external_id:
pmid:
- '28847140'
intvolume: ' 60'
issue: '4'
language:
- iso: eng
month: '08'
oa_version: Published Version
page: 207 - 214
pmid: 1
publication: Chinese Journal of Physiology
publication_identifier:
issn:
- '03044920'
publication_status: published
publisher: Chinese Physiological Society
publist_id: '7142'
quality_controlled: '1'
scopus_import: 1
status: public
title: Effects of B vitamins overload on plasma insulin level and hydrogen peroxide
generation in rats
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 60
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: '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: '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: '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: '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: '649'
abstract:
- lang: eng
text: We give a short overview on a recently developed notion of Ricci curvature
for discrete spaces. This notion relies on geodesic convexity properties of the
relative entropy along geodesics in the space of probability densities, for a
metric which is similar to (but different from) the 2-Wasserstein metric. The
theory can be considered as a discrete counterpart to the theory of Ricci curvature
for geodesic measure spaces developed by Lott–Sturm–Villani.
article_processing_charge: No
author:
- first_name: Jan
full_name: Maas, Jan
id: 4C5696CE-F248-11E8-B48F-1D18A9856A87
last_name: Maas
orcid: 0000-0002-0845-1338
citation:
ama: 'Maas J. Entropic Ricci curvature for discrete spaces. In: Najman L, Romon
P, eds. Modern Approaches to Discrete Curvature. Vol 2184. Lecture Notes
in Mathematics. Springer; 2017:159-174. doi:10.1007/978-3-319-58002-9_5'
apa: Maas, J. (2017). Entropic Ricci curvature for discrete spaces. In L. Najman
& P. Romon (Eds.), Modern Approaches to Discrete Curvature (Vol. 2184,
pp. 159–174). Springer. https://doi.org/10.1007/978-3-319-58002-9_5
chicago: Maas, Jan. “Entropic Ricci Curvature for Discrete Spaces.” In Modern
Approaches to Discrete Curvature, edited by Laurent Najman and Pascal Romon,
2184:159–74. Lecture Notes in Mathematics. Springer, 2017. https://doi.org/10.1007/978-3-319-58002-9_5.
ieee: J. Maas, “Entropic Ricci curvature for discrete spaces,” in Modern Approaches
to Discrete Curvature, vol. 2184, L. Najman and P. Romon, Eds. Springer, 2017,
pp. 159–174.
ista: 'Maas J. 2017.Entropic Ricci curvature for discrete spaces. In: Modern Approaches
to Discrete Curvature. vol. 2184, 159–174.'
mla: Maas, Jan. “Entropic Ricci Curvature for Discrete Spaces.” Modern Approaches
to Discrete Curvature, edited by Laurent Najman and Pascal Romon, vol. 2184,
Springer, 2017, pp. 159–74, doi:10.1007/978-3-319-58002-9_5.
short: J. Maas, in:, L. Najman, P. Romon (Eds.), Modern Approaches to Discrete Curvature,
Springer, 2017, pp. 159–174.
date_created: 2018-12-11T11:47:42Z
date_published: 2017-10-05T00:00:00Z
date_updated: 2022-05-24T07:01:33Z
day: '05'
department:
- _id: JaMa
doi: 10.1007/978-3-319-58002-9_5
editor:
- first_name: Laurent
full_name: Najman, Laurent
last_name: Najman
- first_name: Pascal
full_name: Romon, Pascal
last_name: Romon
intvolume: ' 2184'
language:
- iso: eng
month: '10'
oa_version: None
page: 159 - 174
publication: Modern Approaches to Discrete Curvature
publication_identifier:
eissn:
- 978-3-319-58002-9
isbn:
- 978-3-319-58001-2
publication_status: published
publisher: Springer
publist_id: '7123'
quality_controlled: '1'
scopus_import: '1'
series_title: Lecture Notes in Mathematics
status: public
title: Entropic Ricci curvature for discrete spaces
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2184
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: '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: 2023-02-14T10:08:25Z
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
license: https://creativecommons.org/licenses/by/3.0/
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: '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
license: https://creativecommons.org/licenses/by/4.0/
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: '652'
abstract:
- lang: eng
text: 'We present an approach that enables robots to self-organize their sensorimotor
behavior from scratch without providing specific information about neither the
robot nor its environment. This is achieved by a simple neural control law that
increases the consistency between external sensor dynamics and internal neural
dynamics of the utterly simple controller. In this way, the embodiment and the
agent-environment coupling are the only source of individual development. We show
how an anthropomorphic tendon driven arm-shoulder system develops different behaviors
depending on that coupling. For instance: Given a bottle half-filled with water,
the arm starts to shake it, driven by the physical response of the water. When
attaching a brush, the arm can be manipulated into wiping a table, and when connected
to a revolvable wheel it finds out how to rotate it. Thus, the robot may be said
to discover the affordances of the world. When allowing two (simulated) humanoid
robots to interact physically, they engage into a joint behavior development leading
to, for instance, spontaneous cooperation. More social effects are observed if
the robots can visually perceive each other. Although, as an observer, it is tempting
to attribute an apparent intentionality, there is nothing of the kind put in.
As a conclusion, we argue that emergent behavior may be much less rooted in explicit
intentions, internal motivations, or specific reward systems than is commonly
believed.'
article_number: '7846789'
author:
- first_name: Ralf
full_name: Der, Ralf
last_name: Der
- first_name: Georg S
full_name: Martius, Georg S
id: 3A276B68-F248-11E8-B48F-1D18A9856A87
last_name: Martius
citation:
ama: 'Der R, Martius GS. Dynamical self consistency leads to behavioral development
and emergent social interactions in robots. In: IEEE; 2017. doi:10.1109/DEVLRN.2016.7846789'
apa: 'Der, R., & Martius, G. S. (2017). Dynamical self consistency leads to
behavioral development and emergent social interactions in robots. Presented at
the ICDL EpiRob: International Conference on Development and Learning and Epigenetic
Robotics , Cergy-Pontoise, France: IEEE. https://doi.org/10.1109/DEVLRN.2016.7846789'
chicago: Der, Ralf, and Georg S Martius. “Dynamical Self Consistency Leads to Behavioral
Development and Emergent Social Interactions in Robots.” IEEE, 2017. https://doi.org/10.1109/DEVLRN.2016.7846789.
ieee: 'R. Der and G. S. Martius, “Dynamical self consistency leads to behavioral
development and emergent social interactions in robots,” presented at the ICDL
EpiRob: International Conference on Development and Learning and Epigenetic Robotics
, Cergy-Pontoise, France, 2017.'
ista: 'Der R, Martius GS. 2017. Dynamical self consistency leads to behavioral development
and emergent social interactions in robots. ICDL EpiRob: International Conference
on Development and Learning and Epigenetic Robotics , 7846789.'
mla: Der, Ralf, and Georg S. Martius. Dynamical Self Consistency Leads to Behavioral
Development and Emergent Social Interactions in Robots. 7846789, IEEE, 2017,
doi:10.1109/DEVLRN.2016.7846789.
short: R. Der, G.S. Martius, in:, IEEE, 2017.
conference:
end_date: 2016-09-22
location: Cergy-Pontoise, France
name: 'ICDL EpiRob: International Conference on Development and Learning and Epigenetic
Robotics '
start_date: 2016-09-19
date_created: 2018-12-11T11:47:43Z
date_published: 2017-02-07T00:00:00Z
date_updated: 2021-01-12T08:07:51Z
day: '07'
department:
- _id: ChLa
- _id: GaTk
doi: 10.1109/DEVLRN.2016.7846789
language:
- iso: eng
month: '02'
oa_version: None
publication_identifier:
isbn:
- 978-150905069-7
publication_status: published
publisher: IEEE
publist_id: '7100'
quality_controlled: '1'
scopus_import: 1
status: public
title: Dynamical self consistency leads to behavioral development and emergent social
interactions in robots
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '651'
abstract:
- lang: eng
text: "Superhydrophobic surfaces reduce the frictional drag between water and solid
materials, but this effect is often temporary. The realization of sustained drag
reduction has applications for water vehicles and pipeline flows.\r\n\r\n"
author:
- first_name: Björn
full_name: Hof, Björn
id: 3A374330-F248-11E8-B48F-1D18A9856A87
last_name: Hof
orcid: 0000-0003-2057-2754
citation:
ama: 'Hof B. Fluid dynamics: Water flows out of touch. Nature. 2017;541(7636):161-162.
doi:10.1038/541161a'
apa: 'Hof, B. (2017). Fluid dynamics: Water flows out of touch. Nature. Nature
Publishing Group. https://doi.org/10.1038/541161a'
chicago: 'Hof, Björn. “Fluid Dynamics: Water Flows out of Touch.” Nature.
Nature Publishing Group, 2017. https://doi.org/10.1038/541161a.'
ieee: 'B. Hof, “Fluid dynamics: Water flows out of touch,” Nature, vol. 541,
no. 7636. Nature Publishing Group, pp. 161–162, 2017.'
ista: 'Hof B. 2017. Fluid dynamics: Water flows out of touch. Nature. 541(7636),
161–162.'
mla: 'Hof, Björn. “Fluid Dynamics: Water Flows out of Touch.” Nature, vol.
541, no. 7636, Nature Publishing Group, 2017, pp. 161–62, doi:10.1038/541161a.'
short: B. Hof, Nature 541 (2017) 161–162.
date_created: 2018-12-11T11:47:43Z
date_published: 2017-01-11T00:00:00Z
date_updated: 2021-01-12T08:07:49Z
day: '11'
department:
- _id: BjHo
doi: 10.1038/541161a
intvolume: ' 541'
issue: '7636'
language:
- iso: eng
month: '01'
oa_version: None
page: 161 - 162
publication: Nature
publication_identifier:
issn:
- '00280836'
publication_status: published
publisher: Nature Publishing Group
publist_id: '7116'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Fluid dynamics: Water flows out of touch'
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 541
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: '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: '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: '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'
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: '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'
...
---
_id: '657'
abstract:
- lang: eng
text: Plant organs are typically organized into three main tissue layers. The middle
ground tissue layer comprises the majority of the plant body and serves a wide
range of functions, including photosynthesis, selective nutrient uptake and storage,
and gravity sensing. Ground tissue patterning and maintenance in Arabidopsis are
controlled by a well-established gene network revolving around the key regulator
SHORT-ROOT (SHR). In contrast, it is completely unknown how ground tissue identity
is first specified from totipotent precursor cells in the embryo. The plant signaling
molecule auxin, acting through AUXIN RESPONSE FACTOR (ARF) transcription factors,
is critical for embryo patterning. The auxin effector ARF5/MONOPTEROS (MP) acts
both cell-autonomously and noncell-autonomously to control embryonic vascular
tissue formation and root initiation, respectively. Here we show that auxin response
and ARF activity cell-autonomously control the asymmetric division of the first
ground tissue cells. By identifying embryonic target genes, we show that MP transcriptionally
initiates the ground tissue lineage and acts upstream of the regulatory network
that controls ground tissue patterning and maintenance. Strikingly, whereas the
SHR network depends on MP, this MP function is, at least in part, SHR independent.
Our study therefore identifies auxin response as a regulator of ground tissue
specification in the embryonic root, and reveals that ground tissue initiation
and maintenance use different regulators and mechanisms. Moreover, our data provide
a framework for the simultaneous formation of multiple cell types by the same
transcriptional regulator.
author:
- first_name: Barbara
full_name: Möller, Barbara
last_name: Möller
- first_name: Colette
full_name: Ten Hove, Colette
last_name: Ten Hove
- first_name: Daoquan
full_name: Xiang, Daoquan
last_name: Xiang
- first_name: Nerys
full_name: Williams, Nerys
last_name: Williams
- first_name: Lorena
full_name: López, Lorena
last_name: López
- first_name: Saiko
full_name: Yoshida, Saiko
id: 2E46069C-F248-11E8-B48F-1D18A9856A87
last_name: Yoshida
- first_name: Margot
full_name: Smit, Margot
last_name: Smit
- first_name: Raju
full_name: Datla, Raju
last_name: Datla
- first_name: Dolf
full_name: Weijers, Dolf
last_name: Weijers
citation:
ama: Möller B, Ten Hove C, Xiang D, et al. Auxin response cell autonomously controls
ground tissue initiation in the early arabidopsis embryo. PNAS. 2017;114(12):E2533-E2539.
doi:10.1073/pnas.1616493114
apa: Möller, B., Ten Hove, C., Xiang, D., Williams, N., López, L., Yoshida, S.,
… Weijers, D. (2017). Auxin response cell autonomously controls ground tissue
initiation in the early arabidopsis embryo. PNAS. National Academy of Sciences.
https://doi.org/10.1073/pnas.1616493114
chicago: Möller, Barbara, Colette Ten Hove, Daoquan Xiang, Nerys Williams, Lorena
López, Saiko Yoshida, Margot Smit, Raju Datla, and Dolf Weijers. “Auxin Response
Cell Autonomously Controls Ground Tissue Initiation in the Early Arabidopsis Embryo.”
PNAS. National Academy of Sciences, 2017. https://doi.org/10.1073/pnas.1616493114.
ieee: B. Möller et al., “Auxin response cell autonomously controls ground
tissue initiation in the early arabidopsis embryo,” PNAS, vol. 114, no.
12. National Academy of Sciences, pp. E2533–E2539, 2017.
ista: Möller B, Ten Hove C, Xiang D, Williams N, López L, Yoshida S, Smit M, Datla
R, Weijers D. 2017. Auxin response cell autonomously controls ground tissue initiation
in the early arabidopsis embryo. PNAS. 114(12), E2533–E2539.
mla: Möller, Barbara, et al. “Auxin Response Cell Autonomously Controls Ground Tissue
Initiation in the Early Arabidopsis Embryo.” PNAS, vol. 114, no. 12, National
Academy of Sciences, 2017, pp. E2533–39, doi:10.1073/pnas.1616493114.
short: B. Möller, C. Ten Hove, D. Xiang, N. Williams, L. López, S. Yoshida, M. Smit,
R. Datla, D. Weijers, PNAS 114 (2017) E2533–E2539.
date_created: 2018-12-11T11:47:45Z
date_published: 2017-03-21T00:00:00Z
date_updated: 2021-01-12T08:08:02Z
day: '21'
department:
- _id: JiFr
doi: 10.1073/pnas.1616493114
external_id:
pmid:
- '28265057'
intvolume: ' 114'
issue: '12'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5373392/
month: '03'
oa: 1
oa_version: Submitted Version
page: E2533 - E2539
pmid: 1
publication: PNAS
publication_identifier:
issn:
- '00278424'
publication_status: published
publisher: National Academy of Sciences
publist_id: '7076'
quality_controlled: '1'
scopus_import: 1
status: public
title: Auxin response cell autonomously controls ground tissue initiation in the early
arabidopsis embryo
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 114
year: '2017'
...