---
_id: '2238'
abstract:
- lang: eng
text: "We study the problem of achieving a given value in Markov decision processes
(MDPs) with several independent discounted reward objectives. We consider a generalised
version of discounted reward objectives, in which the amount of discounting depends
on the states visited and on the objective. This definition extends the usual
definition of discounted reward, and allows to capture the systems in which the
value of different commodities diminish at different and variable rates.\r\n\r\nWe
establish results for two prominent subclasses of the problem, namely state-discount
models where the discount factors are only dependent on the state of the MDP (and
independent of the objective), and reward-discount models where they are only
dependent on the objective (but not on the state of the MDP). For the state-discount
models we use a straightforward reduction to expected total reward and show that
the problem whether a value is achievable can be solved in polynomial time. For
the reward-discount model we show that memory and randomisation of the strategies
are required, but nevertheless that the problem is decidable and it is sufficient
to consider strategies which after a certain number of steps behave in a memoryless
way.\r\n\r\nFor the general case, we show that when restricted to graphs (i.e.
MDPs with no randomisation), pure strategies and discount factors of the form
1/n where n is an integer, the problem is in PSPACE and finite memory suffices
for achieving a given value. We also show that when the discount factors are not
of the form 1/n, the memory required by a strategy can be infinite.\r\n"
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Vojtěch
full_name: Forejt, Vojtěch
last_name: Forejt
- first_name: Dominik
full_name: Wojtczak, Dominik
last_name: Wojtczak
citation:
ama: Chatterjee K, Forejt V, Wojtczak D. Multi-objective discounted reward verification
in graphs and MDPs. 2013;8312:228-242. doi:10.1007/978-3-642-45221-5_17
apa: 'Chatterjee, K., Forejt, V., & Wojtczak, D. (2013). Multi-objective discounted
reward verification in graphs and MDPs. Presented at the LPAR: Logic for Programming,
Artificial Intelligence, and Reasoning, Stellenbosch, South Africa: Springer.
https://doi.org/10.1007/978-3-642-45221-5_17'
chicago: Chatterjee, Krishnendu, Vojtěch Forejt, and Dominik Wojtczak. “Multi-Objective
Discounted Reward Verification in Graphs and MDPs.” Lecture Notes in Computer
Science. Springer, 2013. https://doi.org/10.1007/978-3-642-45221-5_17.
ieee: K. Chatterjee, V. Forejt, and D. Wojtczak, “Multi-objective discounted reward
verification in graphs and MDPs,” vol. 8312. Springer, pp. 228–242, 2013.
ista: Chatterjee K, Forejt V, Wojtczak D. 2013. Multi-objective discounted reward
verification in graphs and MDPs. 8312, 228–242.
mla: Chatterjee, Krishnendu, et al. Multi-Objective Discounted Reward Verification
in Graphs and MDPs. Vol. 8312, Springer, 2013, pp. 228–42, doi:10.1007/978-3-642-45221-5_17.
short: K. Chatterjee, V. Forejt, D. Wojtczak, 8312 (2013) 228–242.
conference:
end_date: 2013-12-19
location: Stellenbosch, South Africa
name: 'LPAR: Logic for Programming, Artificial Intelligence, and Reasoning'
start_date: 2013-12-14
date_created: 2018-12-11T11:56:30Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2020-08-11T10:09:42Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-642-45221-5_17
ec_funded: 1
intvolume: ' 8312'
language:
- iso: eng
month: '12'
oa_version: None
page: 228 - 242
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication_status: published
publisher: Springer
publist_id: '4723'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Multi-objective discounted reward verification in graphs and MDPs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8312
year: '2013'
...
---
_id: '2243'
abstract:
- lang: eng
text: We show that modal logic over universally first-order definable classes of
transitive frames is decidable. More precisely, let K be an arbitrary class of
transitive Kripke frames definable by a universal first-order sentence. We show
that the global and finite global satisfiability problems of modal logic over
K are decidable in NP, regardless of choice of K. We also show that the local
satisfiability and the finite local satisfiability problems of modal logic over
K are decidable in NEXPTIME.
alternative_title:
- LIPIcs
author:
- first_name: Jakub
full_name: Michaliszyn, Jakub
last_name: Michaliszyn
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: Michaliszyn J, Otop J. Elementary modal logics over transitive structures.
2013;23:563-577. doi:10.4230/LIPIcs.CSL.2013.563
apa: 'Michaliszyn, J., & Otop, J. (2013). Elementary modal logics over transitive
structures. Presented at the CSL: Computer Science Logic, Torino, Italy: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CSL.2013.563'
chicago: Michaliszyn, Jakub, and Jan Otop. “Elementary Modal Logics over Transitive
Structures.” Leibniz International Proceedings in Informatics. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2013. https://doi.org/10.4230/LIPIcs.CSL.2013.563.
ieee: J. Michaliszyn and J. Otop, “Elementary modal logics over transitive structures,”
vol. 23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 563–577, 2013.
ista: Michaliszyn J, Otop J. 2013. Elementary modal logics over transitive structures.
23, 563–577.
mla: Michaliszyn, Jakub, and Jan Otop. Elementary Modal Logics over Transitive
Structures. Vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013,
pp. 563–77, doi:10.4230/LIPIcs.CSL.2013.563.
short: J. Michaliszyn, J. Otop, 23 (2013) 563–577.
conference:
end_date: 2013-09-05
location: Torino, Italy
name: 'CSL: Computer Science Logic'
start_date: 2013-09-02
date_created: 2018-12-11T11:56:32Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2020-08-11T10:09:42Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CSL.2013.563
ec_funded: 1
file:
- access_level: open_access
checksum: e0732e73a8b1e39483df7717d53e3e35
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:11Z
date_updated: 2020-07-14T12:45:34Z
file_id: '4929'
file_name: IST-2016-136-v1+2_39.pdf
file_size: 454915
relation: main_file
file_date_updated: 2020-07-14T12:45:34Z
has_accepted_license: '1'
intvolume: ' 23'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 563 - 577
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '4708'
pubrep_id: '136'
quality_controlled: '1'
scopus_import: 1
series_title: Leibniz International Proceedings in Informatics
status: public
title: Elementary modal logics over transitive structures
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2013'
...
---
_id: '2244'
abstract:
- lang: eng
text: 'We consider two systems (α1,...,αm) and (β1,...,βn) of curves drawn on a
compact two-dimensional surface ℳ with boundary. Each αi and each βj is either
an arc meeting the boundary of ℳ at its two endpoints, or a closed curve. The
αi are pairwise disjoint except for possibly sharing endpoints, and similarly
for the βj. We want to "untangle" the βj from the αi by a self-homeomorphism
of ℳ; more precisely, we seek an homeomorphism φ: ℳ → ℳ fixing the boundary of
ℳ pointwise such that the total number of crossings of the αi with the φ(βj) is
as small as possible. This problem is motivated by an application in the algorithmic
theory of embeddings and 3-manifolds. We prove that if ℳ is planar, i.e., a sphere
with h ≥ 0 boundary components ("holes"), then O(mn) crossings can be
achieved (independently of h), which is asymptotically tight, as an easy lower
bound shows. In general, for an arbitrary (orientable or nonorientable) surface
ℳ with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an
O((m + n)4) upper bound, again independent of h and g. '
acknowledgement: We would like to thank the authors of [GHR13] for mak- ing a draft
of their paper available to us, and, in particular, T. Huynh for an e-mail correspondence.
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Eric
full_name: Sedgwick, Eric
last_name: Sedgwick
- first_name: Martin
full_name: Tancer, Martin
id: 38AC689C-F248-11E8-B48F-1D18A9856A87
last_name: Tancer
orcid: 0000-0002-1191-6714
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing
curves. 2013;8242:472-483. doi:10.1007/978-3-319-03841-4_41
apa: 'Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2013). Untangling
two systems of noncrossing curves. Presented at the GD: Graph Drawing and Network
Visualization, Bordeaux, France: Springer. https://doi.org/10.1007/978-3-319-03841-4_41'
chicago: Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling
Two Systems of Noncrossing Curves.” Lecture Notes in Computer Science. Springer,
2013. https://doi.org/10.1007/978-3-319-03841-4_41.
ieee: J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems
of noncrossing curves,” vol. 8242. Springer, pp. 472–483, 2013.
ista: Matoušek J, Sedgwick E, Tancer M, Wagner U. 2013. Untangling two systems of
noncrossing curves. 8242, 472–483.
mla: Matoušek, Jiří, et al. Untangling Two Systems of Noncrossing Curves.
Vol. 8242, Springer, 2013, pp. 472–83, doi:10.1007/978-3-319-03841-4_41.
short: J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, 8242 (2013) 472–483.
conference:
end_date: 2013-09-25
location: Bordeaux, France
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2013-09-23
date_created: 2018-12-11T11:56:32Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2025-09-18T14:27:53Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/978-3-319-03841-4_41
external_id:
arxiv:
- '1302.6475'
intvolume: ' 8242'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1302.6475
month: '09'
oa: 1
oa_version: Preprint
page: 472 - 483
project:
- _id: 25FA3206-B435-11E9-9278-68D0E5697425
grant_number: PP00P2_138948
name: 'Embeddings in Higher Dimensions: Algorithms and Combinatorics'
publication_status: published
publisher: Springer
publist_id: '4707'
quality_controlled: '1'
related_material:
record:
- id: '1411'
relation: later_version
status: public
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Untangling two systems of noncrossing curves
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8242
year: '2013'
...
---
_id: '2256'
abstract:
- lang: eng
text: Linked (Open) Data - bibliographic data on the Semantic Web. Report of the
Working Group on Linked Data to the plenary assembly of the Austrian Library Network
(translation of the title). Linked Data stands for a certain approach to publishing
data on the Web. The underlying idea is to harmonise heterogeneous data sources
of different origin in order to improve their accessibility and interoperability,
effectively making them queryable as a big distributed database. This report summarises
relevant developments in Europe as well as the Linked Data Working Group‘s strategic
and technical considerations regarding the publishing of the Austrian Library
Network’s (OBV’s) bibliographic datasets. It concludes with the mutual agreement
that the implementation of Linked Data principles within the OBV can only be taken
into consideration accompanied by a discussion about the provision of the datasets
under a free license.
- lang: ger
text: "Linked Data steht für eine bestimmte Form der Veröffentlichung von Daten
via Internet. Die zu Grunde liegende Idee ist es, Daten verschiedenster Provenienz,
die derzeit teilweise gar nicht oder nur schwer zugänglich sind, in möglichst
\r\neinheitlicher Form miteinander zu verknüpfen und dadurch in ihrer Gesamtheit
abfragbar zu machen.\r\nDieser Bericht fasst die Entwicklungen im europäischen
Raum, sowie strategische und technische Überlegungen der AG Linked Data hinsichtlich
der Veröffentlichung von bibliothekarischen Daten des Österreichischen Bibliothekenverbundes
(OBV) zusammen und schließt mit der gemeinsamen Übereinkunft, dass die Umsetzung
von Linked Data-Prinzipien im OBV nur in Zusammenhang mit einer Diskussion über
die damit einhergehende Veröffentlichung der Daten unter einer freien Lizenz angedacht
werden sollte."
author:
- first_name: Patrick
full_name: Danowski, Patrick
id: 2EBD1598-F248-11E8-B48F-1D18A9856A87
last_name: Danowski
orcid: 0000-0002-6026-4409
- first_name: Doron
full_name: Goldfarb, Doron
last_name: Goldfarb
- first_name: Verena
full_name: Schaffner, Verena
last_name: Schaffner
- first_name: Wolfram
full_name: Seidler, Wolfram
last_name: Seidler
citation:
ama: Danowski P, Goldfarb D, Schaffner V, Seidler W. Linked (Open) Data - Bibliographische
Daten im Semantic Web. VÖB Mitteilungen. 2013;66(3/4):559-587.
apa: Danowski, P., Goldfarb, D., Schaffner, V., & Seidler, W. (2013). Linked
(Open) Data - Bibliographische Daten im Semantic Web. VÖB Mitteilungen.
Verein Österreichischer Bibliothekarinnen und Bibliothekare.
chicago: Danowski, Patrick, Doron Goldfarb, Verena Schaffner, and Wolfram Seidler.
“Linked (Open) Data - Bibliographische Daten Im Semantic Web.” VÖB Mitteilungen.
Verein Österreichischer Bibliothekarinnen und Bibliothekare, 2013.
ieee: P. Danowski, D. Goldfarb, V. Schaffner, and W. Seidler, “Linked (Open) Data
- Bibliographische Daten im Semantic Web,” VÖB Mitteilungen, vol. 66, no.
3/4. Verein Österreichischer Bibliothekarinnen und Bibliothekare, pp. 559–587,
2013.
ista: Danowski P, Goldfarb D, Schaffner V, Seidler W. 2013. Linked (Open) Data -
Bibliographische Daten im Semantic Web. VÖB Mitteilungen. 66(3/4), 559–587.
mla: Danowski, Patrick, et al. “Linked (Open) Data - Bibliographische Daten Im Semantic
Web.” VÖB Mitteilungen, vol. 66, no. 3/4, Verein Österreichischer Bibliothekarinnen
und Bibliothekare, 2013, pp. 559–87.
short: P. Danowski, D. Goldfarb, V. Schaffner, W. Seidler, VÖB Mitteilungen 66 (2013)
559–587.
date_created: 2018-12-11T11:56:36Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2021-01-12T06:56:20Z
day: '01'
ddc:
- '020'
department:
- _id: E-Lib
file:
- access_level: open_access
checksum: ae57ffcee3720adcc27b0f2767a1e04b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:09Z
date_updated: 2020-07-14T12:45:35Z
file_id: '4669'
file_name: IST-2016-719-v1+1_Patrick_Danowski__Doron_Goldfarb__Verena_Schaffner__Wolfram_Seidler_Linked__Open__Data_Bibliographische_Daten_im_Semantic_Web.pdf
file_size: 881545
relation: main_file
file_date_updated: 2020-07-14T12:45:35Z
has_accepted_license: '1'
intvolume: ' 66'
issue: 3/4
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 559 - 587
popular_science: '1'
publication: VÖB Mitteilungen
publication_status: published
publisher: Verein Österreichischer Bibliothekarinnen und Bibliothekare
publist_id: '4690'
pubrep_id: '719'
status: public
title: Linked (Open) Data - Bibliographische Daten im Semantic Web
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: 66
year: '2013'
...
---
_id: '2258'
abstract:
- lang: eng
text: "In a digital signature scheme with message recovery, rather than transmitting
the message m and its signature σ, a single enhanced signature τ is transmitted.
The verifier is able to recover m from τ and at the same time verify its authenticity.
The two most important parameters of such a scheme are its security and overhead
|τ| − |m|. A simple argument shows that for any scheme with “n bits security”
|τ| − |m| ≥ n, i.e., the overhead is lower bounded by the security parameter n.
Currently, the best known constructions in the random oracle model are far from
this lower bound requiring an overhead of n + logq h , where q h is the number
of queries to the random oracle. In this paper we give a construction which basically
matches the n bit lower bound. We propose a simple digital signature scheme with
n + o(logq h ) bits overhead, where q h denotes the number of random oracle queries.\r\n\r\nOur
construction works in two steps. First, we propose a signature scheme with message
recovery having optimal overhead in a new ideal model, the random invertible function
model. Second, we show that a four-round Feistel network with random oracles as
round functions is tightly “public-indifferentiable” from a random invertible
function. At the core of our indifferentiability proof is an almost tight upper
bound for the expected number of edges of the densest “small” subgraph of a random
Cayley graph, which may be of independent interest.\r\n"
alternative_title:
- LNCS
author:
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Mario
full_name: Szegedy, Mario
last_name: Szegedy
citation:
ama: Kiltz E, Pietrzak KZ, Szegedy M. Digital signatures with minimal overhead from
indifferentiable random invertible functions. 2013;8042:571-588. doi:10.1007/978-3-642-40041-4_31
apa: 'Kiltz, E., Pietrzak, K. Z., & Szegedy, M. (2013). Digital signatures with
minimal overhead from indifferentiable random invertible functions. Presented
at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United
States: Springer. https://doi.org/10.1007/978-3-642-40041-4_31'
chicago: Kiltz, Eike, Krzysztof Z Pietrzak, and Mario Szegedy. “Digital Signatures
with Minimal Overhead from Indifferentiable Random Invertible Functions.” Lecture
Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40041-4_31.
ieee: E. Kiltz, K. Z. Pietrzak, and M. Szegedy, “Digital signatures with minimal
overhead from indifferentiable random invertible functions,” vol. 8042. Springer,
pp. 571–588, 2013.
ista: Kiltz E, Pietrzak KZ, Szegedy M. 2013. Digital signatures with minimal overhead
from indifferentiable random invertible functions. 8042, 571–588.
mla: Kiltz, Eike, et al. Digital Signatures with Minimal Overhead from Indifferentiable
Random Invertible Functions. Vol. 8042, Springer, 2013, pp. 571–88, doi:10.1007/978-3-642-40041-4_31.
short: E. Kiltz, K.Z. Pietrzak, M. Szegedy, 8042 (2013) 571–588.
conference:
end_date: 2013-08-22
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2013-08-18
date_created: 2018-12-11T11:56:37Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T06:56:21Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-642-40041-4_31
ec_funded: 1
file:
- access_level: open_access
checksum: 18a3f602cb41de184dc0e16a0e907633
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:20Z
date_updated: 2020-07-14T12:45:35Z
file_id: '4744'
file_name: IST-2016-685-v1+1_658.pdf
file_size: 493175
relation: main_file
file_date_updated: 2020-07-14T12:45:35Z
has_accepted_license: '1'
intvolume: ' 8042'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 571 - 588
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '4688'
pubrep_id: '685'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Digital signatures with minimal overhead from indifferentiable random invertible
functions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8042
year: '2013'
...
---
_id: '2259'
abstract:
- lang: eng
text: "The learning with rounding (LWR) problem, introduced by Banerjee, Peikert
and Rosen at EUROCRYPT ’12, is a variant of learning with errors (LWE), where
one replaces random errors with deterministic rounding. The LWR problem was shown
to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error
ratio are super-polynomial. In this work we resolve the main open problem and
give a new reduction that works for a larger range of parameters, allowing for
a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus
gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater
security, which now follows from the worst-case hardness of GapSVP with polynomial
(rather than super-polynomial) approximation factors.\r\n\r\nAs a tool in the
reduction, we show that there is a “lossy mode” for the LWR problem, in which
LWR samples only reveal partial information about the secret. This property gives
us several interesting new applications, including a proof that LWR remains secure
with weakly random secrets of sufficient min-entropy, and very simple constructions
of deterministic encryption, lossy trapdoor functions and reusable extractors.\r\n\r\nOur
approach is inspired by a technique of Goldwasser et al. from ICS ’10, which implicitly
showed the existence of a “lossy mode” for LWE. By refining this technique, we
also improve on the parameters of that work to only requiring a polynomial (instead
of super-polynomial) modulus and modulus-to-error ratio.\r\n"
alternative_title:
- LNCS
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Stephan
full_name: Krenn, Stephan
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- 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: 'Alwen JF, Krenn S, Pietrzak KZ, Wichs D. Learning with rounding, revisited:
New reduction properties and applications. 2013;8042(1):57-74. doi:10.1007/978-3-642-40041-4_4'
apa: 'Alwen, J. F., Krenn, S., Pietrzak, K. Z., & Wichs, D. (2013). Learning
with rounding, revisited: New reduction properties and applications. Presented
at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United
States: Springer. https://doi.org/10.1007/978-3-642-40041-4_4'
chicago: 'Alwen, Joel F, Stephan Krenn, Krzysztof Z Pietrzak, and Daniel Wichs.
“Learning with Rounding, Revisited: New Reduction Properties and Applications.”
Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40041-4_4.'
ieee: 'J. F. Alwen, S. Krenn, K. Z. Pietrzak, and D. Wichs, “Learning with rounding,
revisited: New reduction properties and applications,” vol. 8042, no. 1. Springer,
pp. 57–74, 2013.'
ista: 'Alwen JF, Krenn S, Pietrzak KZ, Wichs D. 2013. Learning with rounding, revisited:
New reduction properties and applications. 8042(1), 57–74.'
mla: 'Alwen, Joel F., et al. Learning with Rounding, Revisited: New Reduction
Properties and Applications. Vol. 8042, no. 1, Springer, 2013, pp. 57–74,
doi:10.1007/978-3-642-40041-4_4.'
short: J.F. Alwen, S. Krenn, K.Z. Pietrzak, D. Wichs, 8042 (2013) 57–74.
conference:
end_date: 2013-08-22
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2013-08-18
date_created: 2018-12-11T11:56:37Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T06:56:21Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-642-40041-4_4
ec_funded: 1
file:
- access_level: open_access
checksum: 16d428408a806b8e49eecc607deab115
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:55Z
date_updated: 2020-07-14T12:45:35Z
file_id: '4912'
file_name: IST-2016-684-v1+1_098.pdf
file_size: 587898
relation: main_file
file_date_updated: 2020-07-14T12:45:35Z
has_accepted_license: '1'
intvolume: ' 8042'
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 57 - 74
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '4687'
pubrep_id: '684'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: 'Learning with rounding, revisited: New reduction properties and applications'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8042
year: '2013'
...
---
_id: '2260'
abstract:
- lang: eng
text: "Direct Anonymous Attestation (DAA) is one of the most complex cryptographic
protocols deployed in practice. It allows an embedded secure processor known as
a Trusted Platform Module (TPM) to attest to the configuration of its host computer
without violating the owner’s privacy. DAA has been standardized by the Trusted
Computing Group and ISO/IEC.\r\n\r\nThe security of the DAA standard and all existing
schemes is analyzed in the random-oracle model. We provide the first constructions
of DAA in the standard model, that is, without relying on random oracles. Our
constructions use new building blocks, including the first efficient signatures
of knowledge in the standard model, which have many applications beyond DAA.\r\n"
alternative_title:
- LNCS
author:
- first_name: David
full_name: Bernhard, David
last_name: Bernhard
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Essam
full_name: Ghadafi, Essam
last_name: Ghadafi
citation:
ama: Bernhard D, Fuchsbauer G, Ghadafi E. Efficient signatures of knowledge and
DAA in the standard model. 2013;7954:518-533. doi:10.1007/978-3-642-38980-1_33
apa: 'Bernhard, D., Fuchsbauer, G., & Ghadafi, E. (2013). Efficient signatures
of knowledge and DAA in the standard model. Presented at the ACNS: Applied Cryptography
and Network Security, Banff, AB, Canada: Springer. https://doi.org/10.1007/978-3-642-38980-1_33'
chicago: Bernhard, David, Georg Fuchsbauer, and Essam Ghadafi. “Efficient Signatures
of Knowledge and DAA in the Standard Model.” Lecture Notes in Computer Science.
Springer, 2013. https://doi.org/10.1007/978-3-642-38980-1_33.
ieee: D. Bernhard, G. Fuchsbauer, and E. Ghadafi, “Efficient signatures of knowledge
and DAA in the standard model,” vol. 7954. Springer, pp. 518–533, 2013.
ista: Bernhard D, Fuchsbauer G, Ghadafi E. 2013. Efficient signatures of knowledge
and DAA in the standard model. 7954, 518–533.
mla: Bernhard, David, et al. Efficient Signatures of Knowledge and DAA in the
Standard Model. Vol. 7954, Springer, 2013, pp. 518–33, doi:10.1007/978-3-642-38980-1_33.
short: D. Bernhard, G. Fuchsbauer, E. Ghadafi, 7954 (2013) 518–533.
conference:
end_date: 2013-06-28
location: Banff, AB, Canada
name: 'ACNS: Applied Cryptography and Network Security'
start_date: 2013-06-25
date_created: 2018-12-11T11:56:37Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2020-08-11T10:09:44Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-38980-1_33
intvolume: ' 7954'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2012/475
month: '06'
oa: 1
oa_version: Submitted Version
page: 518 - 533
publication_status: published
publisher: Springer
publist_id: '4686'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Efficient signatures of knowledge and DAA in the standard model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7954
year: '2013'
...
---
_id: '2264'
abstract:
- lang: eng
text: Faithful progression through the cell cycle is crucial to the maintenance
and developmental potential of stem cells. Here, we demonstrate that neural stem
cells (NSCs) and intermediate neural progenitor cells (NPCs) employ a zinc-finger
transcription factor specificity protein 2 (Sp2) as a cell cycle regulator in
two temporally and spatially distinct progenitor domains. Differential conditional
deletion of Sp2 in early embryonic cerebral cortical progenitors, and perinatal
olfactory bulb progenitors disrupted transitions through G1, G2 and M phases,
whereas DNA synthesis appeared intact. Cell-autonomous function of Sp2 was identified
by deletion of Sp2 using mosaic analysis with double markers, which clearly established
that conditional Sp2-null NSCs and NPCs are M phase arrested in vivo. Importantly,
conditional deletion of Sp2 led to a decline in the generation of NPCs and neurons
in the developing and postnatal brains. Our findings implicate Sp2-dependent mechanisms
as novel regulators of cell cycle progression, the absence of which disrupts neurogenesis
in the embryonic and postnatal brain.
article_processing_charge: No
author:
- first_name: Huixuan
full_name: Liang, Huixuan
last_name: Liang
- first_name: Guanxi
full_name: Xiao, Guanxi
last_name: Xiao
- first_name: Haifeng
full_name: Yin, Haifeng
last_name: Yin
- first_name: Simon
full_name: Hippenmeyer, Simon
id: 37B36620-F248-11E8-B48F-1D18A9856A87
last_name: Hippenmeyer
orcid: 0000-0003-2279-1061
- first_name: Jonathan
full_name: Horowitz, Jonathan
last_name: Horowitz
- first_name: Troy
full_name: Ghashghaei, Troy
last_name: Ghashghaei
citation:
ama: Liang H, Xiao G, Yin H, Hippenmeyer S, Horowitz J, Ghashghaei T. Neural development
is dependent on the function of specificity protein 2 in cell cycle progression.
Development. 2013;140(3):552-561. doi:10.1242/dev.085621
apa: Liang, H., Xiao, G., Yin, H., Hippenmeyer, S., Horowitz, J., & Ghashghaei,
T. (2013). Neural development is dependent on the function of specificity protein
2 in cell cycle progression. Development. Company of Biologists. https://doi.org/10.1242/dev.085621
chicago: Liang, Huixuan, Guanxi Xiao, Haifeng Yin, Simon Hippenmeyer, Jonathan Horowitz,
and Troy Ghashghaei. “Neural Development Is Dependent on the Function of Specificity
Protein 2 in Cell Cycle Progression.” Development. Company of Biologists,
2013. https://doi.org/10.1242/dev.085621.
ieee: H. Liang, G. Xiao, H. Yin, S. Hippenmeyer, J. Horowitz, and T. Ghashghaei,
“Neural development is dependent on the function of specificity protein 2 in cell
cycle progression,” Development, vol. 140, no. 3. Company of Biologists,
pp. 552–561, 2013.
ista: Liang H, Xiao G, Yin H, Hippenmeyer S, Horowitz J, Ghashghaei T. 2013. Neural
development is dependent on the function of specificity protein 2 in cell cycle
progression. Development. 140(3), 552–561.
mla: Liang, Huixuan, et al. “Neural Development Is Dependent on the Function of
Specificity Protein 2 in Cell Cycle Progression.” Development, vol. 140,
no. 3, Company of Biologists, 2013, pp. 552–61, doi:10.1242/dev.085621.
short: H. Liang, G. Xiao, H. Yin, S. Hippenmeyer, J. Horowitz, T. Ghashghaei, Development
140 (2013) 552–561.
date_created: 2018-12-11T11:56:39Z
date_published: 2013-02-01T00:00:00Z
date_updated: 2025-09-29T14:29:19Z
day: '01'
department:
- _id: SiHi
doi: 10.1242/dev.085621
external_id:
isi:
- '000313363500009'
pmid:
- '23293287'
intvolume: ' 140'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3561788/
month: '02'
oa: 1
oa_version: Submitted Version
page: 552 - 561
pmid: 1
publication: Development
publication_status: published
publisher: Company of Biologists
publist_id: '4681'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Neural development is dependent on the function of specificity protein 2 in
cell cycle progression
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 140
year: '2013'
...
---
_id: '2269'
abstract:
- lang: eng
text: This paper presents a parallel, implementation-friendly analytic visibility
method for triangular meshes. Together with an analytic filter convolution, it
allows for a fully analytic solution to anti-aliased 3D mesh rendering on parallel
hardware. Building on recent works in computational geometry, we present a new
edge-triangle intersection algorithm and a novel method to complete the boundaries
of all visible triangle regions after a hidden line elimination step. All stages
of the method are embarrassingly parallel and easily implementable on parallel
hardware. A GPU implementation is discussed and performance characteristics of
the method are shown and compared to traditional sampling-based rendering methods.
acknowledgement: "Funding was provided by the FWF grant P20768-N13.\nWe want to thank
the reviewers for their insightful and helpful remarks and Gernot Ziegler for providing
help with CUDA. "
author:
- first_name: Thomas
full_name: Thomas Auzinger
id: 4718F954-F248-11E8-B48F-1D18A9856A87
last_name: Auzinger
orcid: 0000-0002-1546-3265
- first_name: Michael
full_name: Wimmer, Michael
last_name: Wimmer
- first_name: Stefan
full_name: Stefan Jeschke
id: 44D6411A-F248-11E8-B48F-1D18A9856A87
last_name: Jeschke
citation:
ama: 'Auzinger T, Wimmer M, Jeschke S. Analytic Visibility on the GPU. Computer
Graphics Forum. 2013;32(124):409-418. doi:DOI:
10.1111/cgf.12061'
apa: 'Auzinger, T., Wimmer, M., & Jeschke, S. (2013). Analytic Visibility on
the GPU. Computer Graphics Forum. Wiley-Blackwell. https://doi.org/DOI: 10.1111/cgf.12061'
chicago: 'Auzinger, Thomas, Michael Wimmer, and Stefan Jeschke. “Analytic Visibility
on the GPU.” Computer Graphics Forum. Wiley-Blackwell, 2013. https://doi.org/DOI: 10.1111/cgf.12061.'
ieee: T. Auzinger, M. Wimmer, and S. Jeschke, “Analytic Visibility on the GPU,”
Computer Graphics Forum, vol. 32, no. 124. Wiley-Blackwell, pp. 409–418,
2013.
ista: Auzinger T, Wimmer M, Jeschke S. 2013. Analytic Visibility on the GPU. Computer
Graphics Forum. 32(124), 409–418.
mla: 'Auzinger, Thomas, et al. “Analytic Visibility on the GPU.” Computer Graphics
Forum, vol. 32, no. 124, Wiley-Blackwell, 2013, pp. 409–18, doi:DOI: 10.1111/cgf.12061.'
short: T. Auzinger, M. Wimmer, S. Jeschke, Computer Graphics Forum 32 (2013) 409–418.
date_created: 2018-12-11T11:56:40Z
date_published: 2013-05-06T00:00:00Z
date_updated: 2021-01-12T06:56:25Z
day: '06'
doi: 'DOI: 10.1111/cgf.12061'
extern: 1
intvolume: ' 32'
issue: 124
month: '05'
page: 409 - 418
publication: Computer Graphics Forum
publication_status: published
publisher: Wiley-Blackwell
publist_id: '4675'
quality_controlled: 0
status: public
title: Analytic Visibility on the GPU
type: journal_article
volume: 32
year: '2013'
...
---
OA_place: repository
OA_type: green
_id: '2270'
abstract:
- lang: eng
text: "Representation languages for coalitional games are a key research area in
algorithmic game theory. There is an inher-\r\nent tradeoff between how general
a language is, allowing it to capture more elaborate games, and how hard
\ it is computationally to optimize and solve such games. One prominent such
\ language is the simple yet expressive\r\nWeighted Graph Games (WGGs) representation
(Deng and Papadimitriou 1994), which maintains knowledge about synergies between
agents in the form of an edge weighted graph. We consider the problem of finding
\ the optimal coalition structure in WGGs. The agents in such games are vertices
in a graph, and the value of a coalition is the sum of the weights of the edges
present between coalition members. The optimal coalition structure is a partition
of the agents to coalitions, that maximizes the sum of utilities obtained by the
coalitions. We show that finding the optimal coalition structure is not
only hard for general graphs, but is also intractable for restricted families
such as planar graphs which are amenable for many other combinatorial problems.
\ We then provide algorithms with constant factor approximations for planar, minorfree
and bounded degree graphs."
article_processing_charge: No
arxiv: 1
author:
- first_name: Yoram
full_name: Bachrach, Yoram
last_name: Bachrach
- first_name: Pushmeet
full_name: Kohli, Pushmeet
last_name: Kohli
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Morteza
full_name: Zadimoghaddam, Morteza
last_name: Zadimoghaddam
citation:
ama: 'Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. Optimal Coalition Structures
in Cooperative Graph Games. In: AAAI Press; 2013:81-87.'
apa: 'Bachrach, Y., Kohli, P., Kolmogorov, V., & Zadimoghaddam, M. (2013). Optimal
Coalition Structures in Cooperative Graph Games (pp. 81–87). Presented at the
AAAI: Conference on Artificial Intelligence, Bellevue, WA, United States: AAAI
Press.'
chicago: Bachrach, Yoram, Pushmeet Kohli, Vladimir Kolmogorov, and Morteza Zadimoghaddam.
“Optimal Coalition Structures in Cooperative Graph Games,” 81–87. AAAI Press,
2013.
ieee: 'Y. Bachrach, P. Kohli, V. Kolmogorov, and M. Zadimoghaddam, “Optimal Coalition
Structures in Cooperative Graph Games,” presented at the AAAI: Conference on Artificial
Intelligence, Bellevue, WA, United States, 2013, pp. 81–87.'
ista: 'Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. 2013. Optimal Coalition
Structures in Cooperative Graph Games. AAAI: Conference on Artificial Intelligence,
81–87.'
mla: Bachrach, Yoram, et al. Optimal Coalition Structures in Cooperative Graph
Games. AAAI Press, 2013, pp. 81–87.
short: Y. Bachrach, P. Kohli, V. Kolmogorov, M. Zadimoghaddam, in:, AAAI Press,
2013, pp. 81–87.
conference:
end_date: 2013-07-18
location: Bellevue, WA, United States
name: 'AAAI: Conference on Artificial Intelligence'
start_date: 2013-07-14
date_created: 2018-12-11T11:56:41Z
date_published: 2013-12-31T00:00:00Z
date_updated: 2025-07-10T11:52:18Z
day: '31'
department:
- _id: VlKo
external_id:
arxiv:
- '1108.5248'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1108.5248
month: '12'
oa: 1
oa_version: Preprint
page: 81-87
publication_status: published
publisher: AAAI Press
publist_id: '4674'
quality_controlled: '1'
status: public
title: Optimal Coalition Structures in Cooperative Graph Games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2272'
abstract:
- lang: eng
text: "We consider Conditional Random Fields (CRFs) with pattern-based potentials
defined on a chain. In this model the energy of a string (labeling) x1...xn is
the sum of terms over intervals [i,j] where each term is non-zero only if the
substring xi...xj equals a prespecified pattern α. Such CRFs can be naturally
applied to many sequence tagging problems.\r\nWe present efficient algorithms
for the three standard inference tasks in a CRF, namely computing (i) the partition
function, (ii) marginals, and (iii) computing the MAP. Their complexities are
respectively O(nL), O(nLℓmax) and O(nLmin{|D|,log(ℓmax+1)}) where L is the combined
length of input patterns, ℓmax is the maximum length of a pattern, and D is the
input alphabet. This improves on the previous algorithms of (Ye et al., 2009)
whose complexities are respectively O(nL|D|), O(n|Γ|L2ℓ2max) and O(nL|D|), where
|Γ| is the number of input patterns.\r\nIn addition, we give an efficient algorithm
for sampling. Finally, we consider the case of non-positive weights. (Komodakis
& Paragios, 2009) gave an O(nL) algorithm for computing the MAP. We present
a modification that has the same worst-case complexity but can beat it in the
best case. "
alternative_title:
- JMLR
article_processing_charge: No
author:
- first_name: Rustem
full_name: Takhanov, Rustem
id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87
last_name: Takhanov
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Takhanov R, Kolmogorov V. Inference algorithms for pattern-based CRFs on sequence
data. In: ICML’13 Proceedings of the 30th International Conference on International.
Vol 28. ML Research Press; 2013:145-153.'
apa: 'Takhanov, R., & Kolmogorov, V. (2013). Inference algorithms for pattern-based
CRFs on sequence data. In ICML’13 Proceedings of the 30th International Conference
on International (Vol. 28, pp. 145–153). Atlanta, GA, USA: ML Research Press.'
chicago: Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based
CRFs on Sequence Data.” In ICML’13 Proceedings of the 30th International Conference
on International, 28:145–53. ML Research Press, 2013.
ieee: R. Takhanov and V. Kolmogorov, “Inference algorithms for pattern-based CRFs
on sequence data,” in ICML’13 Proceedings of the 30th International Conference
on International, Atlanta, GA, USA, 2013, vol. 28, no. 3, pp. 145–153.
ista: 'Takhanov R, Kolmogorov V. 2013. Inference algorithms for pattern-based CRFs
on sequence data. ICML’13 Proceedings of the 30th International Conference on
International. ICML: International Conference on Machine Learning, JMLR, vol.
28, 145–153.'
mla: Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based
CRFs on Sequence Data.” ICML’13 Proceedings of the 30th International Conference
on International, vol. 28, no. 3, ML Research Press, 2013, pp. 145–53.
short: R. Takhanov, V. Kolmogorov, in:, ICML’13 Proceedings of the 30th International
Conference on International, ML Research Press, 2013, pp. 145–153.
conference:
end_date: 2013-06-21
location: Atlanta, GA, USA
name: 'ICML: International Conference on Machine Learning'
start_date: 2013-06-16
corr_author: '1'
date_created: 2018-12-11T11:56:41Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2025-09-29T14:28:48Z
day: '01'
department:
- _id: VlKo
external_id:
isi:
- '000381149500002'
intvolume: ' 28'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://proceedings.mlr.press/v28/takhanov13.pdf?CFID=105472548&CFTOKEN=5c5859b5d97b4439-27B4AC58-BA92-A964-B598CAACEE6CC515
month: '06'
oa: 1
oa_version: Submitted Version
page: 145 - 153
publication: ICML'13 Proceedings of the 30th International Conference on International
publication_status: published
publisher: ML Research Press
publist_id: '4672'
quality_controlled: '1'
related_material:
record:
- id: '1794'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Inference algorithms for pattern-based CRFs on sequence data
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 28
year: '2013'
...
---
OA_place: repository
_id: '2273'
abstract:
- lang: eng
text: We propose a new family of message passing techniques for MAP estimation in
graphical models which we call Sequential Reweighted Message Passing (SRMP). Special
cases include well-known techniques such as Min-Sum Diusion (MSD) and a faster
Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation
is simpler than the original derivation of TRW-S, and does not involve a decomposition
into trees. This allows easy generalizations. We present such a generalization
for the case of higher-order graphical models, and test it on several real-world
problems with promising results.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. Reweighted Message Passing Revisited. IST Austria
apa: Kolmogorov, V. (n.d.). Reweighted message passing revisited. IST Austria.
chicago: Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST
Austria, n.d.
ieee: V. Kolmogorov, Reweighted message passing revisited. IST Austria.
ista: Kolmogorov V. Reweighted message passing revisited, IST Austria,p.
mla: Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST Austria.
short: V. Kolmogorov, Reweighted Message Passing Revisited, IST Austria, n.d.
corr_author: '1'
date_created: 2018-12-11T11:56:42Z
date_published: 2013-09-22T00:00:00Z
date_updated: 2025-09-22T14:33:14Z
day: '22'
department:
- _id: VlKo
external_id:
arxiv:
- '1309.5655'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1309.5655
month: '09'
oa: 1
oa_version: Preprint
publication_status: draft
publisher: IST Austria
publist_id: '4671'
related_material:
record:
- id: '1841'
relation: later_version
status: public
status: public
title: Reweighted message passing revisited
type: report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2274'
abstract:
- lang: eng
text: "Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto'92) as
protection to a shared resource. The basic idea is to ask the service requestor
to dedicate some non-trivial amount of computational work to every request. The
original applications included prevention of spam and protection against denial
of service attacks. More recently, PoWs have been used to prevent double spending
in the Bitcoin digital currency system.\r\n\r\nIn this work, we put forward an
alternative concept for PoWs -- so-called proofs of space (PoS), where a service
requestor must dedicate a significant amount of disk space as opposed to computation.
We construct secure PoS schemes in the random oracle model, using graphs with
high "pebbling complexity" and Merkle hash-trees. "
author:
- first_name: Stefan
full_name: Dziembowski, Stefan
last_name: Dziembowski
- first_name: Sebastian
full_name: Faust, Sebastian
last_name: Faust
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- 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: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. Proofs of Space.
IST Austria; 2013.
apa: Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2013). Proofs
of Space. IST Austria.
chicago: Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof
Z Pietrzak. Proofs of Space. IST Austria, 2013.
ieee: S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, Proofs of
Space. IST Austria, 2013.
ista: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2013. Proofs of Space,
IST Austria,p.
mla: Dziembowski, Stefan, et al. Proofs of Space. IST Austria, 2013.
short: S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, Proofs of Space,
IST Austria, 2013.
date_created: 2018-12-11T11:56:42Z
date_published: 2013-11-28T00:00:00Z
date_updated: 2025-09-23T09:55:25Z
day: '28'
ddc:
- '530'
department:
- _id: VlKo
- _id: KrPi
file:
- access_level: open_access
checksum: 37b61637b62fc079d9141c59d9f1a94f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:11Z
date_updated: 2020-07-14T12:45:36Z
file_id: '5197'
file_name: IST-2016-671-v1+1_796.pdf
file_size: 405870
relation: main_file
file_date_updated: 2020-07-14T12:45:36Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
publication_status: published
publisher: IST Austria
publist_id: '4670'
pubrep_id: '671'
related_material:
record:
- id: '1675'
relation: later_version
status: public
scopus_import: 1
status: public
title: Proofs of Space
type: report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2276'
abstract:
- lang: eng
text: The problem of minimizing the Potts energy function frequently occurs in computer
vision applications. One way to tackle this NP-hard problem was proposed by Kovtun
[19, 20]. It identifies a part of an optimal solution by running k maxflow computations,
where k is the number of labels. The number of “labeled” pixels can be significant
in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce
the runtime to O (log k) maxflow computations (or one parametric maxflow computation).
Furthermore, the output of our algorithm allows to speed-up the subsequent alpha
expansion for the unlabeled part, or can be used as it is for time-critical applications.
To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7]
for Tree Metrics . We also show a connection to k-submodular functions from combinatorial
optimization, and discuss k-submodular relaxations for general energy functions.
article_processing_charge: No
arxiv: 1
author:
- first_name: Igor
full_name: Gridchyn, Igor
id: 4B60654C-F248-11E8-B48F-1D18A9856A87
last_name: Gridchyn
orcid: 0000-0002-1807-1929
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Gridchyn I, Kolmogorov V. Potts model, parametric maxflow and k-submodular
functions. In: IEEE; 2013:2320-2327. doi:10.1109/ICCV.2013.288'
apa: 'Gridchyn, I., & Kolmogorov, V. (2013). Potts model, parametric maxflow
and k-submodular functions (pp. 2320–2327). Presented at the ICCV: International
Conference on Computer Vision, Sydney, Australia: IEEE. https://doi.org/10.1109/ICCV.2013.288'
chicago: Gridchyn, Igor, and Vladimir Kolmogorov. “Potts Model, Parametric Maxflow
and k-Submodular Functions,” 2320–27. IEEE, 2013. https://doi.org/10.1109/ICCV.2013.288.
ieee: 'I. Gridchyn and V. Kolmogorov, “Potts model, parametric maxflow and k-submodular
functions,” presented at the ICCV: International Conference on Computer Vision,
Sydney, Australia, 2013, pp. 2320–2327.'
ista: 'Gridchyn I, Kolmogorov V. 2013. Potts model, parametric maxflow and k-submodular
functions. ICCV: International Conference on Computer Vision, 2320–2327.'
mla: Gridchyn, Igor, and Vladimir Kolmogorov. Potts Model, Parametric Maxflow
and k-Submodular Functions. IEEE, 2013, pp. 2320–27, doi:10.1109/ICCV.2013.288.
short: I. Gridchyn, V. Kolmogorov, in:, IEEE, 2013, pp. 2320–2327.
conference:
end_date: 2013-12-08
location: Sydney, Australia
name: 'ICCV: International Conference on Computer Vision'
start_date: 2013-12-01
corr_author: '1'
date_created: 2018-12-11T11:56:43Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2025-09-29T14:27:49Z
day: '01'
department:
- _id: JoCs
- _id: VlKo
doi: 10.1109/ICCV.2013.288
external_id:
arxiv:
- '1310.1771'
isi:
- '000351830500290'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1310.1771
month: '12'
oa: 1
oa_version: Preprint
page: 2320 - 2327
publication_status: published
publisher: IEEE
publist_id: '4668'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Potts model, parametric maxflow and k-submodular functions
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2013'
...
---
_id: '2277'
abstract:
- lang: eng
text: Redundancies and correlations in the responses of sensory neurons may seem
to waste neural resources, but they can also carry cues about structured stimuli
and may help the brain to correct for response errors. To investigate the effect
of stimulus structure on redundancy in retina, we measured simultaneous responses
from populations of retinal ganglion cells presented with natural and artificial
stimuli that varied greatly in correlation structure; these stimuli and recordings
are publicly available online. Responding to spatio-temporally structured stimuli
such as natural movies, pairs of ganglion cells were modestly more correlated
than in response to white noise checkerboards, but they were much less correlated
than predicted by a non-adapting functional model of retinal response. Meanwhile,
responding to stimuli with purely spatial correlations, pairs of ganglion cells
showed increased correlations consistent with a static, non-adapting receptive
field and nonlinearity. We found that in response to spatio-temporally correlated
stimuli, ganglion cells had faster temporal kernels and tended to have stronger
surrounds. These properties of individual cells, along with gain changes that
opposed changes in effective contrast at the ganglion cell input, largely explained
the pattern of pairwise correlations across stimuli where receptive field measurements
were possible.
article_number: e1003344
article_processing_charge: No
author:
- first_name: Kristina
full_name: Simmons, Kristina
last_name: Simmons
- first_name: Jason
full_name: Prentice, Jason
last_name: Prentice
- first_name: Gasper
full_name: Tkacik, Gasper
id: 3D494DCA-F248-11E8-B48F-1D18A9856A87
last_name: Tkacik
orcid: 0000-0002-6699-1455
- first_name: Jan
full_name: Homann, Jan
last_name: Homann
- first_name: Heather
full_name: Yee, Heather
last_name: Yee
- first_name: Stephanie
full_name: Palmer, Stephanie
last_name: Palmer
- first_name: Philip
full_name: Nelson, Philip
last_name: Nelson
- first_name: Vijay
full_name: Balasubramanian, Vijay
last_name: Balasubramanian
citation:
ama: Simmons K, Prentice J, Tkačik G, et al. Transformation of stimulus correlations
by the retina. PLoS Computational Biology. 2013;9(12). doi:10.1371/journal.pcbi.1003344
apa: Simmons, K., Prentice, J., Tkačik, G., Homann, J., Yee, H., Palmer, S., … Balasubramanian,
V. (2013). Transformation of stimulus correlations by the retina. PLoS Computational
Biology. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1003344
chicago: Simmons, Kristina, Jason Prentice, Gašper Tkačik, Jan Homann, Heather Yee,
Stephanie Palmer, Philip Nelson, and Vijay Balasubramanian. “Transformation of
Stimulus Correlations by the Retina.” PLoS Computational Biology. Public
Library of Science, 2013. https://doi.org/10.1371/journal.pcbi.1003344.
ieee: K. Simmons et al., “Transformation of stimulus correlations by the
retina,” PLoS Computational Biology, vol. 9, no. 12. Public Library of
Science, 2013.
ista: Simmons K, Prentice J, Tkačik G, Homann J, Yee H, Palmer S, Nelson P, Balasubramanian
V. 2013. Transformation of stimulus correlations by the retina. PLoS Computational
Biology. 9(12), e1003344.
mla: Simmons, Kristina, et al. “Transformation of Stimulus Correlations by the Retina.”
PLoS Computational Biology, vol. 9, no. 12, e1003344, Public Library of
Science, 2013, doi:10.1371/journal.pcbi.1003344.
short: K. Simmons, J. Prentice, G. Tkačik, J. Homann, H. Yee, S. Palmer, P. Nelson,
V. Balasubramanian, PLoS Computational Biology 9 (2013).
date_created: 2018-12-11T11:56:43Z
date_published: 2013-12-05T00:00:00Z
date_updated: 2025-09-29T14:27:23Z
day: '05'
ddc:
- '570'
department:
- _id: GaTk
doi: 10.1371/journal.pcbi.1003344
external_id:
isi:
- '000329364800028'
file:
- access_level: open_access
checksum: 46722afc4f7eabb0831165d9c1b171ad
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:36Z
date_updated: 2020-07-14T12:45:36Z
file_id: '5089'
file_name: IST-2016-410-v1+1_journal.pcbi.1003344.pdf
file_size: 3115568
relation: main_file
file_date_updated: 2020-07-14T12:45:36Z
has_accepted_license: '1'
intvolume: ' 9'
isi: 1
issue: '12'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: PLoS Computational Biology
publication_status: published
publisher: Public Library of Science
publist_id: '4667'
pubrep_id: '410'
quality_controlled: '1'
related_material:
record:
- id: '9752'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Transformation of stimulus correlations by the retina
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9
year: '2013'
...
---
_id: '2278'
abstract:
- lang: eng
text: It is firmly established that interactions between neurons and glia are fundamental
across species for the correct establishment of a functional brain. Here, we found
that the glia of the Drosophila larval brain display an essential non-autonomous
role during the development of the optic lobe. The optic lobe develops from neuroepithelial
cells that proliferate by dividing symmetrically until they switch to asymmetric/differentiative
divisions that generate neuroblasts. The proneural gene lethal of scute (l9sc)
is transiently activated by the epidermal growth factor receptor (EGFR)-Ras signal
transduction pathway at the leading edge of a proneural wave that sweeps from
medial to lateral neuroepithelium, promoting this switch. This process is tightly
regulated by the tissue-autonomous function within the neuroepithelium of multiple
signaling pathways, including EGFR-Ras and Notch. This study shows that the Notch
ligand Serrate (Ser) is expressed in the glia and it forms a complex in vivo with
Notch and Canoe, which colocalize at the adherens junctions of neuroepithelial
cells. This complex is crucial for interactions between glia and neuroepithelial
cells during optic lobe development. Ser is tissue-autonomously required in the
glia where it activates Notch to regulate its proliferation, and non-autonomously
in the neuroepithelium where Ser induces Notch signaling to avoid the premature
activation of the EGFR-Ras pathway and hence of L9sc. Interestingly, different
Notch activity reporters showed very different expression patterns in the glia
and in the neuroepithelium, suggesting the existence of tissue-specific factors
that promote the expression of particular Notch target genes or/and a reporter
response dependent on different thresholds of Notch signaling.
article_processing_charge: No
author:
- first_name: Raquel
full_name: Pérez Gómez, Raquel
last_name: Pérez Gómez
- first_name: Jana
full_name: Slovakova, Jana
id: 30F3F2F0-F248-11E8-B48F-1D18A9856A87
last_name: Slovakova
- first_name: Noemí
full_name: Rives Quinto, Noemí
last_name: Rives Quinto
- first_name: Alena
full_name: Krejčí, Alena
last_name: Krejčí
- first_name: Ana
full_name: Carmena, Ana
last_name: Carmena
citation:
ama: Pérez Gómez R, Slovakova J, Rives Quinto N, Krejčí A, Carmena A. A serrate-notch-canoe
complex mediates essential interactions between glia and neuroepithelial cells
during Drosophila optic lobe development. Journal of Cell Science. 2013;126(21):4873-4884.
doi:10.1242/jcs.125617
apa: Pérez Gómez, R., Slovakova, J., Rives Quinto, N., Krejčí, A., & Carmena,
A. (2013). A serrate-notch-canoe complex mediates essential interactions between
glia and neuroepithelial cells during Drosophila optic lobe development. Journal
of Cell Science. Company of Biologists. https://doi.org/10.1242/jcs.125617
chicago: Pérez Gómez, Raquel, Jana Slovakova, Noemí Rives Quinto, Alena Krejčí,
and Ana Carmena. “A Serrate-Notch-Canoe Complex Mediates Essential Interactions
between Glia and Neuroepithelial Cells during Drosophila Optic Lobe Development.”
Journal of Cell Science. Company of Biologists, 2013. https://doi.org/10.1242/jcs.125617.
ieee: R. Pérez Gómez, J. Slovakova, N. Rives Quinto, A. Krejčí, and A. Carmena,
“A serrate-notch-canoe complex mediates essential interactions between glia and
neuroepithelial cells during Drosophila optic lobe development,” Journal of
Cell Science, vol. 126, no. 21. Company of Biologists, pp. 4873–4884, 2013.
ista: Pérez Gómez R, Slovakova J, Rives Quinto N, Krejčí A, Carmena A. 2013. A serrate-notch-canoe
complex mediates essential interactions between glia and neuroepithelial cells
during Drosophila optic lobe development. Journal of Cell Science. 126(21), 4873–4884.
mla: Pérez Gómez, Raquel, et al. “A Serrate-Notch-Canoe Complex Mediates Essential
Interactions between Glia and Neuroepithelial Cells during Drosophila Optic Lobe
Development.” Journal of Cell Science, vol. 126, no. 21, Company of Biologists,
2013, pp. 4873–84, doi:10.1242/jcs.125617.
short: R. Pérez Gómez, J. Slovakova, N. Rives Quinto, A. Krejčí, A. Carmena, Journal
of Cell Science 126 (2013) 4873–4884.
date_created: 2018-12-11T11:56:43Z
date_published: 2013-11-01T00:00:00Z
date_updated: 2025-09-29T14:26:53Z
day: '01'
department:
- _id: CaHe
doi: 10.1242/jcs.125617
external_id:
isi:
- '000326392500009'
intvolume: ' 126'
isi: 1
issue: '21'
language:
- iso: eng
month: '11'
oa_version: None
page: 4873 - 4884
publication: Journal of Cell Science
publication_status: published
publisher: Company of Biologists
publist_id: '4658'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A serrate-notch-canoe complex mediates essential interactions between glia
and neuroepithelial cells during Drosophila optic lobe development
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 126
year: '2013'
...
---
_id: '2279'
abstract:
- lang: eng
text: We consider two-player games played on weighted directed graphs with mean-payoff
and total-payoff objectives, two classical quantitative objectives. While for
single-dimensional games the complexity and memory bounds for both objectives
coincide, we show that in contrast to multi-dimensional mean-payoff games that
are known to be coNP-complete, multi-dimensional total-payoff games are undecidable.
We introduce conservative approximations of these objectives, where the payoff
is considered over a local finite window sliding along a play, instead of the
whole play. For single dimension, we show that (i) if the window size is polynomial,
deciding the winner takes polynomial time, and (ii) the existence of a bounded
window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff
games. For multiple dimensions, we show that (i) the problem with fixed window
size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to
decide the existence of a bounded window.
acknowledgement: 279307; ERC; Fonds National de la Reserche Luxembourg; 279499; ERC;
Fonds National de la Reserche Luxembourg
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: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Mickael
full_name: Randour, Mickael
last_name: Randour
- first_name: Jean
full_name: Raskin, Jean
last_name: Raskin
citation:
ama: Chatterjee K, Doyen L, Randour M, Raskin J. Looking at mean-payoff and total-payoff
through windows. 2013;8172:118-132. doi:10.1007/978-3-319-02444-8_10
apa: 'Chatterjee, K., Doyen, L., Randour, M., & Raskin, J. (2013). Looking at
mean-payoff and total-payoff through windows. Presented at the ATVA: Automated
Technology for Verification and Analysis, Hanoi, Vietnam: Springer. https://doi.org/10.1007/978-3-319-02444-8_10'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Mickael Randour, and Jean Raskin.
“Looking at Mean-Payoff and Total-Payoff through Windows.” Lecture Notes in Computer
Science. Springer, 2013. https://doi.org/10.1007/978-3-319-02444-8_10.
ieee: K. Chatterjee, L. Doyen, M. Randour, and J. Raskin, “Looking at mean-payoff
and total-payoff through windows,” vol. 8172. Springer, pp. 118–132, 2013.
ista: Chatterjee K, Doyen L, Randour M, Raskin J. 2013. Looking at mean-payoff and
total-payoff through windows. 8172, 118–132.
mla: Chatterjee, Krishnendu, et al. Looking at Mean-Payoff and Total-Payoff through
Windows. Vol. 8172, Springer, 2013, pp. 118–32, doi:10.1007/978-3-319-02444-8_10.
short: K. Chatterjee, L. Doyen, M. Randour, J. Raskin, 8172 (2013) 118–132.
conference:
end_date: 2013-10-18
location: Hanoi, Vietnam
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2013-10-15
date_created: 2018-12-11T11:56:44Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2025-09-23T09:29:54Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-319-02444-8_10
ec_funded: 1
external_id:
arxiv:
- '1302.4248'
intvolume: ' 8172'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1302.4248
month: '01'
oa: 1
oa_version: Preprint
page: 118 - 132
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication_status: published
publisher: Springer
publist_id: '4656'
quality_controlled: '1'
related_material:
record:
- id: '523'
relation: later_version
status: public
scopus_import: '1'
series_title: Lecture Notes in Computer Science
status: public
title: Looking at mean-payoff and total-payoff through windows
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8172
year: '2013'
...
---
_id: '2280'
abstract:
- lang: eng
text: The problem of packing ellipsoids of different sizes and shapes into an ellipsoidal
container so as to minimize a measure of overlap between ellipsoids is considered.
A bilevel optimization formulation is given, together with an algorithm for the
general case and a simpler algorithm for the special case in which all ellipsoids
are in fact spheres. Convergence results are proved and computational experience
is described and illustrated. The motivating application-chromosome organization
in the human cell nucleus-is discussed briefly, and some illustrative results
are presented.
article_processing_charge: No
arxiv: 1
author:
- first_name: Caroline
full_name: Uhler, Caroline
id: 49ADD78E-F248-11E8-B48F-1D18A9856A87
last_name: Uhler
orcid: 0000-0002-7008-0216
- first_name: Stephen
full_name: Wright, Stephen
last_name: Wright
citation:
ama: Uhler C, Wright S. Packing ellipsoids with overlap. SIAM Review. 2013;55(4):671-706.
doi:10.1137/120872309
apa: Uhler, C., & Wright, S. (2013). Packing ellipsoids with overlap. SIAM
Review. Society for Industrial and Applied Mathematics . https://doi.org/10.1137/120872309
chicago: Uhler, Caroline, and Stephen Wright. “Packing Ellipsoids with Overlap.”
SIAM Review. Society for Industrial and Applied Mathematics , 2013. https://doi.org/10.1137/120872309.
ieee: C. Uhler and S. Wright, “Packing ellipsoids with overlap,” SIAM Review,
vol. 55, no. 4. Society for Industrial and Applied Mathematics , pp. 671–706,
2013.
ista: Uhler C, Wright S. 2013. Packing ellipsoids with overlap. SIAM Review. 55(4),
671–706.
mla: Uhler, Caroline, and Stephen Wright. “Packing Ellipsoids with Overlap.” SIAM
Review, vol. 55, no. 4, Society for Industrial and Applied Mathematics , 2013,
pp. 671–706, doi:10.1137/120872309.
short: C. Uhler, S. Wright, SIAM Review 55 (2013) 671–706.
date_created: 2018-12-11T11:56:44Z
date_published: 2013-11-07T00:00:00Z
date_updated: 2025-09-29T14:26:18Z
day: '07'
department:
- _id: CaUh
doi: 10.1137/120872309
external_id:
arxiv:
- '1204.0235'
isi:
- '000327502800002'
intvolume: ' 55'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1204.0235
month: '11'
oa: 1
oa_version: Preprint
page: 671 - 706
publication: SIAM Review
publication_status: published
publisher: 'Society for Industrial and Applied Mathematics '
publist_id: '4655'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Packing ellipsoids with overlap
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 55
year: '2013'
...
---
_id: '2282'
abstract:
- lang: eng
text: Epithelial spreading is a common and fundamental aspect of various developmental
and disease-related processes such as epithelial closure and wound healing. A
key challenge for epithelial tissues undergoing spreading is to increase their
surface area without disrupting epithelial integrity. Here we show that orienting
cell divisions by tension constitutes an efficient mechanism by which the enveloping
cell layer (EVL) releases anisotropic tension while undergoing spreading during
zebrafish epiboly. The control of EVL cell-division orientation by tension involves
cell elongation and requires myosin II activity to align the mitotic spindle with
the main tension axis. We also found that in the absence of tension-oriented cell
divisions and in the presence of increased tissue tension, EVL cells undergo ectopic
fusions, suggesting that the reduction of tension anisotropy by oriented cell
divisions is required to prevent EVL cells from fusing. We conclude that cell-division
orientation by tension constitutes a key mechanism for limiting tension anisotropy
and thus promoting tissue spreading during EVL epiboly.
acknowledged_ssus:
- _id: PreCl
- _id: Bio
acknowledgement: 'This work was supported by the IST Austria and MPI-CBG '
article_processing_charge: No
author:
- first_name: Pedro
full_name: Campinho, Pedro
id: 3AFBBC42-F248-11E8-B48F-1D18A9856A87
last_name: Campinho
orcid: 0000-0002-8526-5416
- first_name: Martin
full_name: Behrndt, Martin
id: 3ECECA3A-F248-11E8-B48F-1D18A9856A87
last_name: Behrndt
- first_name: Jonas
full_name: Ranft, Jonas
last_name: Ranft
- first_name: Thomas
full_name: Risler, Thomas
last_name: Risler
- first_name: Nicolas
full_name: Minc, Nicolas
last_name: Minc
- first_name: Carl-Philipp J
full_name: Heisenberg, Carl-Philipp J
id: 39427864-F248-11E8-B48F-1D18A9856A87
last_name: Heisenberg
orcid: 0000-0002-0912-4566
citation:
ama: Campinho P, Behrndt M, Ranft J, Risler T, Minc N, Heisenberg C-PJ. Tension-oriented
cell divisions limit anisotropic tissue tension in epithelial spreading during
zebrafish epiboly. Nature Cell Biology. 2013;15:1405-1414. doi:10.1038/ncb2869
apa: Campinho, P., Behrndt, M., Ranft, J., Risler, T., Minc, N., & Heisenberg,
C.-P. J. (2013). Tension-oriented cell divisions limit anisotropic tissue tension
in epithelial spreading during zebrafish epiboly. Nature Cell Biology.
Nature Publishing Group. https://doi.org/10.1038/ncb2869
chicago: Campinho, Pedro, Martin Behrndt, Jonas Ranft, Thomas Risler, Nicolas Minc,
and Carl-Philipp J Heisenberg. “Tension-Oriented Cell Divisions Limit Anisotropic
Tissue Tension in Epithelial Spreading during Zebrafish Epiboly.” Nature Cell
Biology. Nature Publishing Group, 2013. https://doi.org/10.1038/ncb2869.
ieee: P. Campinho, M. Behrndt, J. Ranft, T. Risler, N. Minc, and C.-P. J. Heisenberg,
“Tension-oriented cell divisions limit anisotropic tissue tension in epithelial
spreading during zebrafish epiboly,” Nature Cell Biology, vol. 15. Nature
Publishing Group, pp. 1405–1414, 2013.
ista: Campinho P, Behrndt M, Ranft J, Risler T, Minc N, Heisenberg C-PJ. 2013. Tension-oriented
cell divisions limit anisotropic tissue tension in epithelial spreading during
zebrafish epiboly. Nature Cell Biology. 15, 1405–1414.
mla: Campinho, Pedro, et al. “Tension-Oriented Cell Divisions Limit Anisotropic
Tissue Tension in Epithelial Spreading during Zebrafish Epiboly.” Nature Cell
Biology, vol. 15, Nature Publishing Group, 2013, pp. 1405–14, doi:10.1038/ncb2869.
short: P. Campinho, M. Behrndt, J. Ranft, T. Risler, N. Minc, C.-P.J. Heisenberg,
Nature Cell Biology 15 (2013) 1405–1414.
corr_author: '1'
date_created: 2018-12-11T11:56:45Z
date_published: 2013-11-10T00:00:00Z
date_updated: 2026-03-09T14:56:18Z
day: '10'
department:
- _id: CaHe
doi: 10.1038/ncb2869
external_id:
isi:
- '000327944200005'
intvolume: ' 15'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://hal.upmc.fr/hal-00983313/
month: '11'
oa: 1
oa_version: Submitted Version
page: 1405 - 1414
project:
- _id: 252ABD0A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I930-B20
name: Control of Epithelial Cell Layer Spreading in Zebrafish
publication: Nature Cell Biology
publication_status: published
publisher: Nature Publishing Group
publist_id: '4652'
quality_controlled: '1'
related_material:
record:
- id: '1403'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Tension-oriented cell divisions limit anisotropic tissue tension in epithelial
spreading during zebrafish epiboly
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 15
year: '2013'
...
---
_id: '2283'
abstract:
- lang: eng
text: Pathogens exert a strong selection pressure on organisms to evolve effective
immune defences. In addition to individual immunity, social organisms can act
cooperatively to produce collective defences. In many ant species, queens have
the option to found a colony alone or in groups with other, often unrelated, conspecifics.
These associations are transient, usually lasting only as long as each queen benefits
from the presence of others. In fact, once the first workers emerge, queens fight
to the death for dominance. One potential advantage of co-founding may be that
queens benefit from collective disease defences, such as mutual grooming, that
act against common soil pathogens. We test this hypothesis by exposing single
and co-founding queens to a fungal parasite, in order to assess whether queens
in co-founding associations have improved survival. Surprisingly, co-foundresses
exposed to the entomopathogenic fungus Metarhizium did not engage in cooperative
disease defences, and consequently, we find no direct benefit of multiple queens
on survival. However, an indirect benefit was observed, with parasite-exposed
queens producing more brood when they co-founded, than when they were alone. We
suggest this is due to a trade-off between reproduction and immunity. Additionally,
we report an extraordinary ability of the queens to tolerate an infection for
long periods after parasite exposure. Our study suggests that there are no social
immunity benefits for co-founding ant queens, but that in parasite-rich environments,
the presence of additional queens may nevertheless improve the chances of colony
founding success.
article_processing_charge: No
author:
- first_name: Christopher
full_name: Pull, Christopher
id: 3C7F4840-F248-11E8-B48F-1D18A9856A87
last_name: Pull
orcid: 0000-0003-1122-3982
- first_name: William
full_name: Hughes, William
last_name: Hughes
- first_name: Markus
full_name: Brown, Markus
id: 3DAB9AFC-F248-11E8-B48F-1D18A9856A87
last_name: Brown
citation:
ama: 'Pull C, Hughes W, Brown M. Tolerating an infection: an indirect benefit of
co-founding queen associations in the ant Lasius niger . Naturwissenschaften.
2013;100(12):1125-1136. doi:10.1007/s00114-013-1115-5'
apa: 'Pull, C., Hughes, W., & Brown, M. (2013). Tolerating an infection: an
indirect benefit of co-founding queen associations in the ant Lasius niger . Naturwissenschaften.
Springer. https://doi.org/10.1007/s00114-013-1115-5'
chicago: 'Pull, Christopher, William Hughes, and Markus Brown. “Tolerating an Infection:
An Indirect Benefit of Co-Founding Queen Associations in the Ant Lasius Niger
.” Naturwissenschaften. Springer, 2013. https://doi.org/10.1007/s00114-013-1115-5.'
ieee: 'C. Pull, W. Hughes, and M. Brown, “Tolerating an infection: an indirect benefit
of co-founding queen associations in the ant Lasius niger ,” Naturwissenschaften,
vol. 100, no. 12. Springer, pp. 1125–1136, 2013.'
ista: 'Pull C, Hughes W, Brown M. 2013. Tolerating an infection: an indirect benefit
of co-founding queen associations in the ant Lasius niger . Naturwissenschaften.
100(12), 1125–1136.'
mla: 'Pull, Christopher, et al. “Tolerating an Infection: An Indirect Benefit of
Co-Founding Queen Associations in the Ant Lasius Niger .” Naturwissenschaften,
vol. 100, no. 12, Springer, 2013, pp. 1125–36, doi:10.1007/s00114-013-1115-5.'
short: C. Pull, W. Hughes, M. Brown, Naturwissenschaften 100 (2013) 1125–1136.
corr_author: '1'
date_created: 2018-12-11T11:56:45Z
date_published: 2013-11-14T00:00:00Z
date_updated: 2025-09-29T14:24:42Z
day: '14'
department:
- _id: SyCr
doi: 10.1007/s00114-013-1115-5
external_id:
isi:
- '000328850200004'
intvolume: ' 100'
isi: 1
issue: '12'
language:
- iso: eng
month: '11'
oa_version: None
page: 1125 - 1136
publication: Naturwissenschaften
publication_status: published
publisher: Springer
publist_id: '4649'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Tolerating an infection: an indirect benefit of co-founding queen associations
in the ant Lasius niger '
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 100
year: '2013'
...