---
_id: '5434'
abstract:
- lang: eng
text: DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate
in an uncertain environment independently to achieve a joint objective. DEC-POMDPs
have been studied with finite-horizon and infinite-horizon discounted-sum objectives,
and there exist solvers both for exact and approximate solutions. In this work
we consider Goal-DEC-POMDPs, where given a set of target states, the objective
is to ensure that the target set is reached with minimal cost. We consider the
indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum,
where absorbing goal states have zero-cost) problem. We present a new method to
solve the problem that extends methods for finite-horizon DEC- POMDPs and the
RTDP-Bel approach for POMDPs. We present experimental results on several examples,
and show our approach presents promising results.
alternative_title:
- IST Austria Technical Report
author:
- first_name: '1'
full_name: Anonymous, 1
last_name: Anonymous
- first_name: '2'
full_name: Anonymous, 2
last_name: Anonymous
citation:
ama: Anonymous 1, Anonymous 2. Optimal Cost Indefinite-Horizon Reachability in
Goal DEC-POMDPs. IST Austria; 2015.
apa: Anonymous, 1, & Anonymous, 2. (2015). Optimal cost indefinite-horizon
reachability in goal DEC-POMDPs. IST Austria.
chicago: Anonymous, 1, and 2 Anonymous. Optimal Cost Indefinite-Horizon Reachability
in Goal DEC-POMDPs. IST Austria, 2015.
ieee: 1 Anonymous and 2 Anonymous, Optimal cost indefinite-horizon reachability
in goal DEC-POMDPs. IST Austria, 2015.
ista: Anonymous 1, Anonymous 2. 2015. Optimal cost indefinite-horizon reachability
in goal DEC-POMDPs, IST Austria, 16p.
mla: Anonymous, 1, and 2 Anonymous. Optimal Cost Indefinite-Horizon Reachability
in Goal DEC-POMDPs. IST Austria, 2015.
short: 1 Anonymous, 2 Anonymous, Optimal Cost Indefinite-Horizon Reachability in
Goal DEC-POMDPs, IST Austria, 2015.
date_created: 2018-12-12T11:39:18Z
date_published: 2015-02-19T00:00:00Z
date_updated: 2020-07-14T23:04:59Z
day: '19'
ddc:
- '000'
file:
- access_level: open_access
checksum: 8542fd0b10aed7811cd41077b8ccb632
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:14Z
date_updated: 2020-07-14T12:46:53Z
file_id: '5475'
file_name: IST-2015-326-v1+1_main.pdf
file_size: 378162
relation: main_file
- access_level: closed
checksum: 84c31c537bdaf7a91909f18d25d640ab
content_type: text/plain
creator: dernst
date_created: 2019-04-16T13:00:33Z
date_updated: 2020-07-14T12:46:53Z
file_id: '6317'
file_name: IST-2015-326-v1+2_authors.txt
file_size: 64
relation: main_file
file_date_updated: 2020-07-14T12:46:53Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '16'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '326'
status: public
title: Optimal cost indefinite-horizon reachability in goal DEC-POMDPs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5435'
abstract:
- lang: eng
text: "We consider Markov decision processes (MDPs) with multiple limit-average
(or mean-payoff) objectives. \r\nThere have been two different views: (i) the
expectation semantics, where the goal is to optimize the expected mean-payoff
objective, and (ii) the satisfaction semantics, where the goal is to maximize
the probability of runs such that the mean-payoff value stays above a given vector.
\ \r\nWe consider the problem where the goal is to optimize the expectation under
the constraint that the satisfaction semantics is ensured, and thus consider a
generalization that unifies the existing semantics. Our problem captures the notion
of optimization with respect to strategies that are risk-averse (i.e., ensures
certain probabilistic guarantee).\r\nOur main results are algorithms for the decision
problem which are always polynomial in the size of the MDP.\r\nWe also show that
an approximation of the Pareto-curve can be computed in time polynomial in the
size of the MDP, and the approximation factor, but exponential in the number of
dimensions. Finally, we present a complete characterization of the strategy complexity
(in terms of memory bounds and randomization) required to solve our problem."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Zuzana
full_name: Komarkova, Zuzana
last_name: Komarkova
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
citation:
ama: Chatterjee K, Komarkova Z, Kretinsky J. Unifying Two Views on Multiple Mean-Payoff
Objectives in Markov Decision Processes. IST Austria; 2015. doi:10.15479/AT:IST-2015-318-v2-1
apa: Chatterjee, K., Komarkova, Z., & Kretinsky, J. (2015). Unifying two
views on multiple mean-payoff objectives in Markov decision processes. IST
Austria. https://doi.org/10.15479/AT:IST-2015-318-v2-1
chicago: Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. Unifying
Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes.
IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-318-v2-1.
ieee: K. Chatterjee, Z. Komarkova, and J. Kretinsky, Unifying two views on multiple
mean-payoff objectives in Markov decision processes. IST Austria, 2015.
ista: Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple
mean-payoff objectives in Markov decision processes, IST Austria, 51p.
mla: Chatterjee, Krishnendu, et al. Unifying Two Views on Multiple Mean-Payoff
Objectives in Markov Decision Processes. IST Austria, 2015, doi:10.15479/AT:IST-2015-318-v2-1.
short: K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple
Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.
date_created: 2018-12-12T11:39:19Z
date_published: 2015-02-23T00:00:00Z
date_updated: 2025-09-29T11:00:42Z
day: '23'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-318-v2-1
file:
- access_level: open_access
checksum: 75284adec80baabdfe71ff9ebbc27445
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:03Z
date_updated: 2020-07-14T12:46:53Z
file_id: '5525'
file_name: IST-2015-318-v2+1_main.pdf
file_size: 717630
relation: main_file
file_date_updated: 2020-07-14T12:46:53Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '51'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '327'
related_material:
record:
- id: '5429'
relation: earlier_version
status: public
- id: '466'
relation: later_version
status: public
- id: '1657'
relation: later_version
status: public
status: public
title: Unifying two views on multiple mean-payoff objectives in Markov decision processes
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5436'
abstract:
- lang: eng
text: "Recently there has been a significant effort to handle quantitative properties
in formal verification and synthesis. While weighted automata over finite and
infinite words provide a natural and flexible framework to express quantitative
properties, perhaps surprisingly, some basic system properties such as average
response time cannot be expressed using weighted automata, nor in any other know
decidable formalism. In this work, we introduce nested weighted automata as a
natural extension of weighted automata which makes it possible to express important
quantitative properties such as average response time.\r\nIn nested weighted automata,
a master automaton spins off and collects results from weighted slave automata,
each of which computes a quantity along a finite portion of an infinite word.
Nested weighted automata can be viewed as the quantitative analogue of monitor
automata, which are used in run-time verification. We establish an almost complete
decidability picture for the basic decision problems about nested weighted automata,
and illustrate their applicability in several domains. In particular, nested weighted
automata can be used to decide average response time properties."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- 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: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: Chatterjee K, Henzinger TA, Otop J. Nested Weighted Automata. IST Austria;
2015. doi:10.15479/AT:IST-2015-170-v2-2
apa: Chatterjee, K., Henzinger, T. A., & Otop, J. (2015). Nested weighted
automata. IST Austria. https://doi.org/10.15479/AT:IST-2015-170-v2-2
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. Nested Weighted
Automata. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-170-v2-2.
ieee: K. Chatterjee, T. A. Henzinger, and J. Otop, Nested weighted automata.
IST Austria, 2015.
ista: Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata, IST Austria,
29p.
mla: Chatterjee, Krishnendu, et al. Nested Weighted Automata. IST Austria,
2015, doi:10.15479/AT:IST-2015-170-v2-2.
short: K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria,
2015.
date_created: 2018-12-12T11:39:19Z
date_published: 2015-04-24T00:00:00Z
date_updated: 2025-09-23T09:39:58Z
day: '24'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2015-170-v2-2
file:
- access_level: open_access
checksum: 3c402f47d3669c28d04d1af405a08e3f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:19Z
date_updated: 2020-07-14T12:46:54Z
file_id: '5541'
file_name: IST-2015-170-v2+2_report.pdf
file_size: 569991
relation: main_file
file_date_updated: 2020-07-14T12:46:54Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '29'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '331'
related_material:
record:
- id: '5415'
relation: earlier_version
status: public
- id: '467'
relation: later_version
status: public
- id: '1656'
relation: later_version
status: public
status: public
title: Nested weighted automata
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5437'
abstract:
- lang: eng
text: "We consider the core algorithmic problems related to verification of systems
with respect to three classical quantitative properties, namely, the mean-payoff
property, the ratio property, and the minimum initial credit for energy property.
\r\nThe algorithmic problem given a graph and a quantitative property asks to
compute the optimal value (the infimum value over all traces) from every node
of the graph. We consider graphs with constant treewidth, and it is well-known
that the control-flow graphs of most programs have constant treewidth. Let $n$
denote the number of nodes of a graph, $m$ the number of edges (for constant treewidth
graphs $m=O(n)$) and $W$ the largest absolute value of the weights.\r\nOur main
theoretical results are as follows.\r\nFirst, for constant treewidth graphs we
present an algorithm that approximates the mean-payoff value within a multiplicative
factor of $\\epsilon$ in time $O(n \\cdot \\log (n/\\epsilon))$ and linear space,
as compared to the classical algorithms that require quadratic time. Second, for
the ratio property we present an algorithm that for constant treewidth graphs
works in time $O(n \\cdot \\log (|a\\cdot b|))=O(n\\cdot\\log (n\\cdot W))$, when
the output is $\\frac{a}{b}$, as compared to the previously best known algorithm
with running time $O(n^2 \\cdot \\log (n\\cdot W))$. Third, for the minimum initial
credit problem we show that (i)~for general graphs the problem can be solved in
$O(n^2\\cdot m)$ time and the associated decision problem can be solved in $O(n\\cdot
m)$ time, improving the previous known $O(n^3\\cdot m\\cdot \\log (n\\cdot W))$
and $O(n^2 \\cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs
we present an algorithm that requires $O(n\\cdot \\log n)$ time, improving the
previous known $O(n^4 \\cdot \\log (n \\cdot W))$ bound.\r\nWe have implemented
some of our algorithms and show that they present a significant speedup on standard
benchmarks. "
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Faster Algorithms for Quantitative
Verification in Constant Treewidth Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-330-v2-1
apa: Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). Faster
algorithms for quantitative verification in constant treewidth graphs. IST
Austria. https://doi.org/10.15479/AT:IST-2015-330-v2-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.
Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs.
IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-330-v2-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Faster algorithms
for quantitative verification in constant treewidth graphs. IST Austria, 2015.
ista: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for
quantitative verification in constant treewidth graphs, IST Austria, 27p.
mla: Chatterjee, Krishnendu, et al. Faster Algorithms for Quantitative Verification
in Constant Treewidth Graphs. IST Austria, 2015, doi:10.15479/AT:IST-2015-330-v2-1.
short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative
Verification in Constant Treewidth Graphs, IST Austria, 2015.
date_created: 2018-12-12T11:39:19Z
date_published: 2015-04-27T00:00:00Z
date_updated: 2025-09-23T08:47:23Z
day: '27'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-330-v2-1
file:
- access_level: open_access
checksum: f5917c20f84018b362d385c000a2e123
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:12Z
date_updated: 2020-07-14T12:46:54Z
file_id: '5473'
file_name: IST-2015-330-v2+1_main.pdf
file_size: 1072137
relation: main_file
file_date_updated: 2020-07-14T12:46:54Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '27'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '333'
related_material:
record:
- id: '5430'
relation: earlier_version
status: public
- id: '1607'
relation: later_version
status: public
status: public
title: Faster algorithms for quantitative verification in constant treewidth graphs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5439'
abstract:
- lang: eng
text: 'The target discounted-sum problem is the following: Given a rational discount
factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite
or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals
t? The problem turns out to relate to many fields of mathematics and computer
science, and its decidability question is surprisingly hard to solve. We solve
the finite version of the problem, and show the hardness of the infinite version,
linking it to various areas and open problems in mathematics and computer science:
β-expansions, discounted-sum automata, piecewise affine maps, and generalizations
of the Cantor set. We provide some partial results to the infinite version, among
which are solutions to its restriction to eventually-periodic sequences and to
the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving
some open problems on discounted-sum automata, among which are the exact-value
problem for nondeterministic automata over finite words and the universality and
inclusion problems for functional automata. '
alternative_title:
- IST Austria Technical Report
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- 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: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: Boker U, Henzinger TA, Otop J. The Target Discounted-Sum Problem. IST
Austria; 2015. doi:10.15479/AT:IST-2015-335-v1-1
apa: Boker, U., Henzinger, T. A., & Otop, J. (2015). The target discounted-sum
problem. IST Austria. https://doi.org/10.15479/AT:IST-2015-335-v1-1
chicago: Boker, Udi, Thomas A Henzinger, and Jan Otop. The Target Discounted-Sum
Problem. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-335-v1-1.
ieee: U. Boker, T. A. Henzinger, and J. Otop, The target discounted-sum problem.
IST Austria, 2015.
ista: Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem, IST
Austria, 20p.
mla: Boker, Udi, et al. The Target Discounted-Sum Problem. IST Austria, 2015,
doi:10.15479/AT:IST-2015-335-v1-1.
short: U. Boker, T.A. Henzinger, J. Otop, The Target Discounted-Sum Problem, IST
Austria, 2015.
date_created: 2018-12-12T11:39:20Z
date_published: 2015-05-18T00:00:00Z
date_updated: 2025-04-15T08:11:50Z
day: '18'
ddc:
- '004'
- '512'
- '513'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2015-335-v1-1
file:
- access_level: open_access
checksum: 40405907aa012acece1bc26cf0be554d
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:55Z
date_updated: 2020-07-14T12:46:55Z
file_id: '5517'
file_name: IST-2015-335-v1+1_report.pdf
file_size: 589619
relation: main_file
file_date_updated: 2020-07-14T12:46:55Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '20'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '335'
related_material:
record:
- id: '1659'
relation: later_version
status: public
status: public
title: The target discounted-sum problem
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5440'
abstract:
- lang: eng
text: 'Evolution occurs in populations of reproducing individuals. The structure
of the population affects the outcome of the evolutionary process. Evolutionary
graph theory is a powerful approach to study this phenomenon. There are two graphs.
The interaction graph specifies who interacts with whom for payoff in the context
of evolution. The replacement graph specifies who competes with whom for reproduction.
The vertices of the two graphs are the same, and each vertex corresponds to an
individual of the population. The fitness (or the reproductive rate) is a non-negative
number, and depends on the payoff. A key quantity is the fixation probability
of a new mutant. It is defined as the probability that a newly introduced mutant
(on a single vertex) generates a lineage of offspring which eventually takes over
the entire population of resident individuals. The basic computational questions
are as follows: (i) the qualitative question asks whether the fixation probability
is positive; and (ii) the quantitative approximation question asks for an approximation
of the fixation probability. Our main results are as follows: First, we consider
a special case of the general problem, where the residents do not reproduce. We
show that the qualitative question is NP-complete, and the quantitative approximation
question is #P-complete, and the hardness results hold even in the special case
where the interaction and the replacement graphs coincide. Second, we show that
in general both the qualitative and the quantitative approximation questions are
PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds
even when the fitness is always positive.'
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Chatterjee K, Ibsen-Jensen R, Nowak M. The Complexity of Evolutionary Games
on Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-323-v2-2
apa: Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2015). The complexity
of evolutionary games on graphs. IST Austria. https://doi.org/10.15479/AT:IST-2015-323-v2-2
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. The Complexity
of Evolutionary Games on Graphs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-323-v2-2.
ieee: K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, The complexity of evolutionary
games on graphs. IST Austria, 2015.
ista: Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary
games on graphs, IST Austria, 18p.
mla: Chatterjee, Krishnendu, et al. The Complexity of Evolutionary Games on Graphs.
IST Austria, 2015, doi:10.15479/AT:IST-2015-323-v2-2.
short: K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary
Games on Graphs, IST Austria, 2015.
date_created: 2018-12-12T11:39:21Z
date_published: 2015-06-16T00:00:00Z
date_updated: 2023-02-23T12:26:10Z
day: '16'
ddc:
- '005'
- '576'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-323-v2-2
file:
- access_level: open_access
checksum: 66aace7d367032af97c15e35c9be9636
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:23Z
date_updated: 2020-07-14T12:46:56Z
file_id: '5484'
file_name: IST-2015-323-v2+2_main.pdf
file_size: 466161
relation: main_file
file_date_updated: 2020-07-14T12:46:56Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '18'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '338'
related_material:
record:
- id: '5421'
relation: earlier_version
status: public
- id: '5432'
relation: earlier_version
status: public
status: public
title: The complexity of evolutionary games on graphs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5441'
abstract:
- lang: eng
text: We study algorithmic questions for concurrent systems where the transitions
are labeled from a complete, closed semiring, and path properties are algebraic
with semiring operations. The algebraic path properties can model dataflow analysis
problems, the shortest path problem, and many other natural problems that arise
in program analysis. We consider that each component of the concurrent system
is a graph with constant treewidth, a property satisfied by the controlflow graphs
of most programs. We allow for multiple possible queries, which arise naturally
in demand driven dataflow analysis. The study of multiple queries allows us to
consider the tradeoff between the resource usage of the one-time preprocessing
and for each individual query. The traditional approach constructs the product
graph of all components and applies the best-known graph algorithm on the product.
In this approach, even the answer to a single query requires the transitive closure
(i.e., the results of all possible queries), which provides no room for tradeoff
between preprocessing and query time. Our main contributions are algorithms that
significantly improve the worst-case running time of the traditional approach,
and provide various tradeoffs depending on the number of queries. For example,
in a concurrent system of two components, the traditional approach requires hexic
time in the worst case for answering one query as well as computing the transitive
closure, whereas we show that with one-time preprocessing in almost cubic time,
each subsequent query can be answered in at most linear time, and even the transitive
closure can be computed in almost quartic time. Furthermore, we establish conditional
optimality results showing that the worst-case running time of our algorithms
cannot be improved without achieving major breakthroughs in graph algorithms (i.e.,
improving the worst-case bound for the shortest path problem in general graphs).
Preliminary experimental results show that our algorithms perform favorably on
several benchmarks.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Amir
full_name: Goharshady, Amir
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. Algorithms
for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components.
IST Austria; 2015. doi:10.15479/AT:IST-2015-340-v1-1
apa: Chatterjee, K., Ibsen-Jensen, R., Goharshady, A. K., & Pavlogiannis, A.
(2015). Algorithms for algebraic path properties in concurrent systems of constant
treewidth components. IST Austria. https://doi.org/10.15479/AT:IST-2015-340-v1-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Amir Kafshdar Goharshady,
and Andreas Pavlogiannis. Algorithms for Algebraic Path Properties in Concurrent
Systems of Constant Treewidth Components. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-340-v1-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, A. K. Goharshady, and A. Pavlogiannis, Algorithms
for algebraic path properties in concurrent systems of constant treewidth components.
IST Austria, 2015.
ista: Chatterjee K, Ibsen-Jensen R, Goharshady AK, Pavlogiannis A. 2015. Algorithms
for algebraic path properties in concurrent systems of constant treewidth components,
IST Austria, 24p.
mla: Chatterjee, Krishnendu, et al. Algorithms for Algebraic Path Properties
in Concurrent Systems of Constant Treewidth Components. IST Austria, 2015,
doi:10.15479/AT:IST-2015-340-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, A.K. Goharshady, A. Pavlogiannis, Algorithms
for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components,
IST Austria, 2015.
date_created: 2018-12-12T11:39:21Z
date_published: 2015-07-11T00:00:00Z
date_updated: 2025-04-15T08:11:48Z
day: '11'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-340-v1-1
file:
- access_level: open_access
checksum: df383dc62c94d7b2ea639aba088a76c6
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:09Z
date_updated: 2020-07-14T12:46:56Z
file_id: '5531'
file_name: IST-2015-340-v1+1_main.pdf
file_size: 861396
relation: main_file
file_date_updated: 2020-07-14T12:46:56Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '24'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '340'
related_material:
record:
- id: '5442'
relation: earlier_version
status: public
- id: '6009'
relation: later_version
status: public
- id: '1437'
relation: later_version
status: public
status: public
title: Algorithms for algebraic path properties in concurrent systems of constant
treewidth components
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5442'
abstract:
- lang: eng
text: "We study algorithmic questions for concurrent systems where the transitions
are labeled from a complete, closed semiring, and path properties are algebraic
with semiring operations. The algebraic path properties can model dataflow analysis
problems, the shortest path problem, and many other natural properties that arise
in program analysis.\r\nWe consider that each component of the concurrent system
is a graph with constant treewidth, and it is known that the controlflow graphs
of most programs have constant treewidth. We allow for multiple possible queries,
which arise naturally in demand driven dataflow analysis problems (e.g., alias
analysis). The study of multiple queries allows us to consider the tradeoff between
the resource usage of the \\emph{one-time} preprocessing and for \\emph{each individual}
query. The traditional approaches construct the product graph of all components
and apply the best-known graph algorithm on the product. In the traditional approach,
even the answer to a single query requires the transitive closure computation
(i.e., the results of all possible queries), which provides no room for tradeoff
between preprocessing and query time.\r\n\r\nOur main contributions are algorithms
that significantly improve the worst-case running time of the traditional approach,
and provide various tradeoffs depending on the number of queries. For example,
in a concurrent system of two components, the traditional approach requires hexic
time in the worst case for answering one query as well as computing the transitive
closure, whereas we show that with one-time preprocessing in almost cubic time,
\r\neach subsequent query can be answered in at most linear time, and even the
transitive closure can be computed in almost quartic time. Furthermore, we establish
conditional optimality results that show that the worst-case running times of
our algorithms cannot be improved without achieving major breakthroughs in graph
algorithms (such as improving \r\nthe worst-case bounds for the shortest path
problem in general graphs whose current best-known bound has not been improved
in five decades). Finally, we provide a prototype implementation of our algorithms
which significantly outperforms the existing algorithmic methods on several benchmarks."
alternative_title:
- IST Austria Technical Report
author:
- first_name: '1'
full_name: Anonymous, 1
last_name: Anonymous
- first_name: '2'
full_name: Anonymous, 2
last_name: Anonymous
- first_name: '3'
full_name: Anonymous, 3
last_name: Anonymous
- first_name: '4'
full_name: Anonymous, 4
last_name: Anonymous
citation:
ama: Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. Algorithms for Algebraic
Path Properties in Concurrent Systems of Constant Treewidth Components. IST
Austria; 2015.
apa: Anonymous, 1, Anonymous, 2, Anonymous, 3, & Anonymous, 4. (2015). Algorithms
for algebraic path properties in concurrent systems of constant treewidth components.
IST Austria.
chicago: Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. Algorithms
for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components.
IST Austria, 2015.
ieee: 1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, Algorithms for
algebraic path properties in concurrent systems of constant treewidth components.
IST Austria, 2015.
ista: Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2015. Algorithms for algebraic
path properties in concurrent systems of constant treewidth components, IST Austria,
22p.
mla: Anonymous, 1, et al. Algorithms for Algebraic Path Properties in Concurrent
Systems of Constant Treewidth Components. IST Austria, 2015.
short: 1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Algorithms for Algebraic
Path Properties in Concurrent Systems of Constant Treewidth Components, IST Austria,
2015.
date_created: 2018-12-12T11:39:21Z
date_published: 2015-07-14T00:00:00Z
date_updated: 2025-04-15T08:11:49Z
day: '14'
ddc:
- '000'
file:
- access_level: open_access
checksum: 98fd936102f3e057fc321ef6d316001d
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:37Z
date_updated: 2020-07-14T12:46:57Z
file_id: '5498'
file_name: IST-2015-343-v2+1_main.pdf
file_size: 658747
relation: main_file
- access_level: closed
checksum: b31d09b1241b59c75e1f42dadf09d258
content_type: text/plain
creator: dernst
date_created: 2019-04-16T12:36:08Z
date_updated: 2020-07-14T12:46:57Z
file_id: '6316'
file_name: IST-2015-343-v2+2_anonymous.txt
file_size: 139
relation: main_file
file_date_updated: 2020-07-14T12:46:57Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '22'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '344'
related_material:
record:
- id: '5441'
relation: later_version
status: public
- id: '6009'
relation: later_version
status: public
- id: '1437'
relation: later_version
status: public
scopus_import: 1
status: public
title: Algorithms for algebraic path properties in concurrent systems of constant
treewidth components
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5443'
abstract:
- lang: eng
text: POMDPs are standard models for probabilistic planning problems, where an agent
interacts with an uncertain environment. We study the problem of almost-sure reachability,
where given a set of target states, the question is to decide whether there is
a policy to ensure that the target set is reached with probability 1 (almost-surely).
While in general the problem is EXPTIME-complete, in many practical cases policies
with a small amount of memory suffice. Moreover, the existing solution to the
problem is explicit, which first requires to construct explicitly an exponential
reduction to a belief-support MDP. In this work, we first study the existence
of observation-stationary strategies, which is NP-complete, and then small-memory
strategies. We present a symbolic algorithm by an efficient encoding to SAT and
using a SAT solver for the problem. We report experimental results demonstrating
the scalability of our symbolic (SAT-based) approach.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Jessica
full_name: Davies, Jessica
id: 378E0060-F248-11E8-B48F-1D18A9856A87
last_name: Davies
citation:
ama: Chatterjee K, Chmelik M, Davies J. A Symbolic SAT-Based Algorithm for Almost-Sure
Reachability with Small Strategies in POMDPs. IST Austria; 2015. doi:10.15479/AT:IST-2015-325-v2-1
apa: Chatterjee, K., Chmelik, M., & Davies, J. (2015). A symbolic SAT-based
algorithm for almost-sure reachability with small strategies in POMDPs. IST
Austria. https://doi.org/10.15479/AT:IST-2015-325-v2-1
chicago: Chatterjee, Krishnendu, Martin Chmelik, and Jessica Davies. A Symbolic
SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs.
IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-325-v2-1.
ieee: K. Chatterjee, M. Chmelik, and J. Davies, A symbolic SAT-based algorithm
for almost-sure reachability with small strategies in POMDPs. IST Austria,
2015.
ista: Chatterjee K, Chmelik M, Davies J. 2015. A symbolic SAT-based algorithm for
almost-sure reachability with small strategies in POMDPs, IST Austria, 23p.
mla: Chatterjee, Krishnendu, et al. A Symbolic SAT-Based Algorithm for Almost-Sure
Reachability with Small Strategies in POMDPs. IST Austria, 2015, doi:10.15479/AT:IST-2015-325-v2-1.
short: K. Chatterjee, M. Chmelik, J. Davies, A Symbolic SAT-Based Algorithm for
Almost-Sure Reachability with Small Strategies in POMDPs, IST Austria, 2015.
date_created: 2018-12-12T11:39:22Z
date_published: 2015-11-06T00:00:00Z
date_updated: 2025-06-25T11:52:13Z
day: '06'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-325-v2-1
file:
- access_level: open_access
checksum: f0fa31ad8161ed655137e94012123ef9
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:05Z
date_updated: 2020-07-14T12:46:57Z
file_id: '5466'
file_name: IST-2015-325-v2+1_main.pdf
file_size: 412379
relation: main_file
file_date_updated: 2020-07-14T12:46:57Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: '23'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '362'
related_material:
record:
- id: '1166'
relation: later_version
status: public
status: public
title: A symbolic SAT-based algorithm for almost-sure reachability with small strategies
in POMDPs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5444'
abstract:
- lang: eng
text: A comprehensive understanding of the clonal evolution of cancer is critical
for understanding neoplasia. Genome-wide sequencing data enables evolutionary
studies at unprecedented depth. However, classical phylogenetic methods often
struggle with noisy sequencing data of impure DNA samples and fail to detect subclones
that have different evolutionary trajectories. We have developed a tool, called
Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly
available sequencing technologies. Using Bayesian inference and Integer Linear
Programming, robust phylogenies consistent with the biological processes underlying
cancer evolution were obtained for pancreatic, ovarian, and prostate cancers.
Furthermore, Treeomics correctly identified sequencing artifacts such as those
resulting from low statistical power; nearly 7% of variants were misclassified
by conventional statistical methods. These artifacts can skew phylogenies by creating
illusory tumor heterogeneity among distinct samples. Importantly, we show that
the evolutionary trees generated with Treeomics are mathematically optimal.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Johannes
full_name: Reiter, Johannes
id: 4A918E98-F248-11E8-B48F-1D18A9856A87
last_name: Reiter
orcid: 0000-0002-0170-7353
- first_name: Alvin
full_name: Makohon-Moore, Alvin
last_name: Makohon-Moore
- first_name: Jeffrey
full_name: Gerold, Jeffrey
last_name: Gerold
- first_name: Ivana
full_name: Bozic, Ivana
last_name: Bozic
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Christine
full_name: Iacobuzio-Donahue, Christine
last_name: Iacobuzio-Donahue
- first_name: Bert
full_name: Vogelstein, Bert
last_name: Vogelstein
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Reiter J, Makohon-Moore A, Gerold J, et al. Reconstructing Robust Phylogenies
of Metastatic Cancers. IST Austria; 2015. doi:10.15479/AT:IST-2015-399-v1-1
apa: Reiter, J., Makohon-Moore, A., Gerold, J., Bozic, I., Chatterjee, K., Iacobuzio-Donahue,
C., … Nowak, M. (2015). Reconstructing robust phylogenies of metastatic cancers.
IST Austria. https://doi.org/10.15479/AT:IST-2015-399-v1-1
chicago: Reiter, Johannes, Alvin Makohon-Moore, Jeffrey Gerold, Ivana Bozic, Krishnendu
Chatterjee, Christine Iacobuzio-Donahue, Bert Vogelstein, and Martin Nowak. Reconstructing
Robust Phylogenies of Metastatic Cancers. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-399-v1-1.
ieee: J. Reiter et al., Reconstructing robust phylogenies of metastatic
cancers. IST Austria, 2015.
ista: Reiter J, Makohon-Moore A, Gerold J, Bozic I, Chatterjee K, Iacobuzio-Donahue
C, Vogelstein B, Nowak M. 2015. Reconstructing robust phylogenies of metastatic
cancers, IST Austria, 25p.
mla: Reiter, Johannes, et al. Reconstructing Robust Phylogenies of Metastatic
Cancers. IST Austria, 2015, doi:10.15479/AT:IST-2015-399-v1-1.
short: J. Reiter, A. Makohon-Moore, J. Gerold, I. Bozic, K. Chatterjee, C. Iacobuzio-Donahue,
B. Vogelstein, M. Nowak, Reconstructing Robust Phylogenies of Metastatic Cancers,
IST Austria, 2015.
date_created: 2018-12-12T11:39:22Z
date_published: 2015-12-30T00:00:00Z
date_updated: 2020-07-14T23:05:07Z
day: '30'
ddc:
- '000'
- '576'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-399-v1-1
file:
- access_level: open_access
checksum: c47d33bdda06181753c0af36f16e7b5d
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:24Z
date_updated: 2020-07-14T12:46:58Z
file_id: '5485'
file_name: IST-2015-399-v1+1_treeomics.pdf
file_size: 3533200
relation: main_file
file_date_updated: 2020-07-14T12:46:58Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: '25'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '399'
status: public
title: Reconstructing robust phylogenies of metastatic cancers
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5549'
abstract:
- lang: eng
text: "This repository contains the experimental part of the CAV 2015 publication
Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.\r\nWe
extended the probabilistic model checker PRISM to represent strategies of Markov
Decision Processes as Decision Trees.\r\nThe archive contains a java executable
version of the extended tool (prism_dectree.jar) together with a few examples
of the PRISM benchmark library.\r\nTo execute the program, please have a look
at the README.txt, which provides instructions and further information on the
archive.\r\nThe archive contains scripts that (if run often enough) reproduces
the data presented in the publication."
article_processing_charge: No
author:
- first_name: Andreas
full_name: Fellner, Andreas
id: 42BABFB4-F248-11E8-B48F-1D18A9856A87
last_name: Fellner
citation:
ama: 'Fellner A. Experimental part of CAV 2015 publication: Counterexample Explanation
by Learning Small Strategies in Markov Decision Processes. 2015. doi:10.15479/AT:ISTA:28'
apa: 'Fellner, A. (2015). Experimental part of CAV 2015 publication: Counterexample
Explanation by Learning Small Strategies in Markov Decision Processes. Institute
of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:28'
chicago: 'Fellner, Andreas. “Experimental Part of CAV 2015 Publication: Counterexample
Explanation by Learning Small Strategies in Markov Decision Processes.” Institute
of Science and Technology Austria, 2015. https://doi.org/10.15479/AT:ISTA:28.'
ieee: 'A. Fellner, “Experimental part of CAV 2015 publication: Counterexample Explanation
by Learning Small Strategies in Markov Decision Processes.” Institute of Science
and Technology Austria, 2015.'
ista: 'Fellner A. 2015. Experimental part of CAV 2015 publication: Counterexample
Explanation by Learning Small Strategies in Markov Decision Processes, Institute
of Science and Technology Austria, 10.15479/AT:ISTA:28.'
mla: 'Fellner, Andreas. Experimental Part of CAV 2015 Publication: Counterexample
Explanation by Learning Small Strategies in Markov Decision Processes. Institute
of Science and Technology Austria, 2015, doi:10.15479/AT:ISTA:28.'
short: A. Fellner, (2015).
contributor:
- first_name: Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
datarep_id: '28'
date_created: 2018-12-12T12:31:29Z
date_published: 2015-08-13T00:00:00Z
date_updated: 2025-09-23T08:23:15Z
day: '13'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:ISTA:28
ec_funded: 1
file:
- access_level: open_access
checksum: b8bcb43c0893023cda66c1b69c16ac62
content_type: application/zip
creator: system
date_created: 2018-12-12T13:02:31Z
date_updated: 2020-07-14T12:47:00Z
file_id: '5597'
file_name: IST-2015-28-v1+2_Fellner_DataRep.zip
file_size: 49557109
relation: main_file
file_date_updated: 2020-07-14T12:47:00Z
has_accepted_license: '1'
keyword:
- Markov Decision Process
- Decision Tree
- Probabilistic Verification
- Counterexample Explanation
license: https://creativecommons.org/publicdomain/zero/1.0/
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publisher: Institute of Science and Technology Austria
publist_id: '5564'
related_material:
record:
- id: '1603'
relation: popular_science
status: public
status: public
title: 'Experimental part of CAV 2015 publication: Counterexample Explanation by Learning
Small Strategies in Markov Decision Processes'
tmp:
image: /images/cc_0.png
legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode
name: Creative Commons Public Domain Dedication (CC0 1.0)
short: CC0 (1.0)
type: research_data
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5804'
abstract:
- lang: eng
text: We present here the first integer-based algorithm for constructing a well-defined
lattice sphere specified by integer radius and integer center. The algorithm evolves
from a unique correspondence between the lattice points comprising the sphere
and the distribution of sum of three square numbers in integer intervals. We characterize
these intervals to derive a useful set of recurrences, which, in turn, aids in
efficient computation. Each point of the lattice sphere is determined by resorting
to only a few primitive operations in the integer domain. The symmetry of its
quadraginta octants provides an added advantage by confining the computation to
its prima quadraginta octant. Detailed theoretical analysis and experimental results
have been furnished to demonstrate its simplicity and elegance.
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Partha
full_name: Bhowmick, Partha
last_name: Bhowmick
citation:
ama: Biswas R, Bhowmick P. From prima quadraginta octant to lattice sphere through
primitive integer operations. Theoretical Computer Science. 2015;624(4):56-72.
doi:10.1016/j.tcs.2015.11.018
apa: Biswas, R., & Bhowmick, P. (2015). From prima quadraginta octant to lattice
sphere through primitive integer operations. Theoretical Computer Science.
Elsevier. https://doi.org/10.1016/j.tcs.2015.11.018
chicago: Biswas, Ranita, and Partha Bhowmick. “From Prima Quadraginta Octant to
Lattice Sphere through Primitive Integer Operations.” Theoretical Computer
Science. Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.11.018.
ieee: R. Biswas and P. Bhowmick, “From prima quadraginta octant to lattice sphere
through primitive integer operations,” Theoretical Computer Science, vol.
624, no. 4. Elsevier, pp. 56–72, 2015.
ista: Biswas R, Bhowmick P. 2015. From prima quadraginta octant to lattice sphere
through primitive integer operations. Theoretical Computer Science. 624(4), 56–72.
mla: Biswas, Ranita, and Partha Bhowmick. “From Prima Quadraginta Octant to Lattice
Sphere through Primitive Integer Operations.” Theoretical Computer Science,
vol. 624, no. 4, Elsevier, 2015, pp. 56–72, doi:10.1016/j.tcs.2015.11.018.
short: R. Biswas, P. Bhowmick, Theoretical Computer Science 624 (2015) 56–72.
date_created: 2019-01-08T20:44:06Z
date_published: 2015-04-18T00:00:00Z
date_updated: 2021-01-12T08:03:36Z
day: '18'
doi: 10.1016/j.tcs.2015.11.018
extern: '1'
intvolume: ' 624'
issue: '4'
language:
- iso: eng
month: '04'
oa_version: None
page: 56-72
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: From prima quadraginta octant to lattice sphere through primitive integer operations
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 624
year: '2015'
...
---
_id: '5807'
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Partha
full_name: Bhowmick, Partha
last_name: Bhowmick
citation:
ama: Biswas R, Bhowmick P. On different topological classes of spherical geodesic
paths and circles inZ3. Theoretical Computer Science. 2015;605(11):146-163.
doi:10.1016/j.tcs.2015.09.003
apa: Biswas, R., & Bhowmick, P. (2015). On different topological classes of
spherical geodesic paths and circles inZ3. Theoretical Computer Science.
Elsevier. https://doi.org/10.1016/j.tcs.2015.09.003
chicago: Biswas, Ranita, and Partha Bhowmick. “On Different Topological Classes
of Spherical Geodesic Paths and Circles InZ3.” Theoretical Computer Science.
Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.09.003.
ieee: R. Biswas and P. Bhowmick, “On different topological classes of spherical
geodesic paths and circles inZ3,” Theoretical Computer Science, vol. 605,
no. 11. Elsevier, pp. 146–163, 2015.
ista: Biswas R, Bhowmick P. 2015. On different topological classes of spherical
geodesic paths and circles inZ3. Theoretical Computer Science. 605(11), 146–163.
mla: Biswas, Ranita, and Partha Bhowmick. “On Different Topological Classes of Spherical
Geodesic Paths and Circles InZ3.” Theoretical Computer Science, vol. 605,
no. 11, Elsevier, 2015, pp. 146–63, doi:10.1016/j.tcs.2015.09.003.
short: R. Biswas, P. Bhowmick, Theoretical Computer Science 605 (2015) 146–163.
date_created: 2019-01-08T20:44:52Z
date_published: 2015-11-09T00:00:00Z
date_updated: 2021-01-12T08:03:37Z
day: '09'
doi: 10.1016/j.tcs.2015.09.003
extern: '1'
intvolume: ' 605'
issue: '11'
language:
- iso: eng
month: '11'
oa_version: None
page: 146-163
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: On different topological classes of spherical geodesic paths and circles inZ3
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 605
year: '2015'
...
---
_id: '5808'
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Partha
full_name: Bhowmick, Partha
last_name: Bhowmick
citation:
ama: Biswas R, Bhowmick P. Layer the sphere. The Visual Computer. 2015;31(6-8):787-797.
doi:10.1007/s00371-015-1101-3
apa: Biswas, R., & Bhowmick, P. (2015). Layer the sphere. The Visual Computer.
Springer Nature. https://doi.org/10.1007/s00371-015-1101-3
chicago: Biswas, Ranita, and Partha Bhowmick. “Layer the Sphere.” The Visual
Computer. Springer Nature, 2015. https://doi.org/10.1007/s00371-015-1101-3.
ieee: R. Biswas and P. Bhowmick, “Layer the sphere,” The Visual Computer,
vol. 31, no. 6–8. Springer Nature, pp. 787–797, 2015.
ista: Biswas R, Bhowmick P. 2015. Layer the sphere. The Visual Computer. 31(6–8),
787–797.
mla: Biswas, Ranita, and Partha Bhowmick. “Layer the Sphere.” The Visual Computer,
vol. 31, no. 6–8, Springer Nature, 2015, pp. 787–97, doi:10.1007/s00371-015-1101-3.
short: R. Biswas, P. Bhowmick, The Visual Computer 31 (2015) 787–797.
date_created: 2019-01-08T20:45:05Z
date_published: 2015-05-08T00:00:00Z
date_updated: 2021-01-12T08:03:37Z
day: '08'
doi: 10.1007/s00371-015-1101-3
extern: '1'
intvolume: ' 31'
issue: 6-8
language:
- iso: eng
month: '05'
oa_version: None
page: 787-797
publication: The Visual Computer
publication_identifier:
issn:
- 0178-2789
- 1432-2315
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Layer the sphere
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 31
year: '2015'
...
---
_id: '594'
abstract:
- lang: eng
text: Transcription of eukaryotic protein-coding genes commences with the assembly
of a conserved initiation complex, which consists of RNA polymerase II (Pol II)
and the general transcription factors, at promoter DNA. After two decades of research,
the structural basis of transcription initiation is emerging. Crystal structures
of many components of the initiation complex have been resolved, and structural
information on Pol II complexes with general transcription factors has recently
been obtained. Although mechanistic details await elucidation, available data
outline how Pol II cooperates with the general transcription factors to bind to
and open promoter DNA, and how Pol II directs RNA synthesis and escapes from the
promoter.
article_processing_charge: No
author:
- first_name: Sarah
full_name: Sainsbury, Sarah
last_name: Sainsbury
- first_name: Carrie A
full_name: Bernecky, Carrie A
id: 2CB9DFE2-F248-11E8-B48F-1D18A9856A87
last_name: Bernecky
orcid: 0000-0003-0893-7036
- first_name: Patrick
full_name: Cramer, Patrick
last_name: Cramer
citation:
ama: Sainsbury S, Bernecky C, Cramer P. Structural basis of transcription initiation
by RNA polymerase II. Nature Reviews Molecular Cell Biology. 2015;16(3):129-143.
doi:10.1038/nrm3952
apa: Sainsbury, S., Bernecky, C., & Cramer, P. (2015). Structural basis of transcription
initiation by RNA polymerase II. Nature Reviews Molecular Cell Biology.
Nature Publishing Group. https://doi.org/10.1038/nrm3952
chicago: Sainsbury, Sarah, Carrie Bernecky, and Patrick Cramer. “Structural Basis
of Transcription Initiation by RNA Polymerase II.” Nature Reviews Molecular
Cell Biology. Nature Publishing Group, 2015. https://doi.org/10.1038/nrm3952.
ieee: S. Sainsbury, C. Bernecky, and P. Cramer, “Structural basis of transcription
initiation by RNA polymerase II,” Nature Reviews Molecular Cell Biology,
vol. 16, no. 3. Nature Publishing Group, pp. 129–143, 2015.
ista: Sainsbury S, Bernecky C, Cramer P. 2015. Structural basis of transcription
initiation by RNA polymerase II. Nature Reviews Molecular Cell Biology. 16(3),
129–143.
mla: Sainsbury, Sarah, et al. “Structural Basis of Transcription Initiation by RNA
Polymerase II.” Nature Reviews Molecular Cell Biology, vol. 16, no. 3,
Nature Publishing Group, 2015, pp. 129–43, doi:10.1038/nrm3952.
short: S. Sainsbury, C. Bernecky, P. Cramer, Nature Reviews Molecular Cell Biology
16 (2015) 129–143.
date_created: 2018-12-11T11:47:23Z
date_published: 2015-03-26T00:00:00Z
date_updated: 2021-01-12T08:05:16Z
day: '26'
doi: 10.1038/nrm3952
extern: '1'
intvolume: ' 16'
issue: '3'
language:
- iso: eng
month: '03'
oa_version: None
page: 129 - 143
publication: Nature Reviews Molecular Cell Biology
publication_status: published
publisher: Nature Publishing Group
publist_id: '7206'
status: public
title: Structural basis of transcription initiation by RNA polymerase II
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2015'
...
---
_id: '6118'
abstract:
- lang: eng
text: 'Carbon dioxide (CO2) gradients are ubiquitous and provide animals with information
about their environment, such as the potential presence of prey or predators.
The nematode Caenorhabditis elegans avoids elevated CO2, and previous work identified
three neuron pairs called “BAG,” “AFD,” and “ASE” that respond to CO2 stimuli.
Using in vivo Ca2+ imaging and behavioral analysis, we show that C. elegans can
detect CO2 independently of these sensory pathways. Many of the C. elegans sensory
neurons we examined, including the AWC olfactory neurons, the ASJ and ASK gustatory
neurons, and the ASH and ADL nociceptors, respond to a rise in CO2 with a rise
in Ca2+. In contrast, glial sheath cells harboring the sensory endings of C. elegans’
major chemosensory neurons exhibit strong and sustained decreases in Ca2+ in response
to high CO2. Some of these CO2 responses appear to be cell intrinsic. Worms therefore
may couple detection of CO2 to that of other cues at the earliest stages of sensory
processing. We show that C. elegans persistently suppresses oviposition at high
CO2. Hermaphrodite-specific neurons (HSNs), the executive neurons driving egg-laying,
are tonically inhibited when CO2 is elevated. CO2 modulates the egg-laying system
partly through the AWC olfactory neurons: High CO2 tonically activates AWC by
a cGMP-dependent mechanism, and AWC output inhibits the HSNs. Our work shows that
CO2 is a more complex sensory cue for C. elegans than previously thought, both
in terms of behavior and neural circuitry.'
author:
- first_name: Lorenz A.
full_name: Fenk, Lorenz A.
last_name: Fenk
- first_name: Mario
full_name: de Bono, Mario
id: 4E3FF80E-F248-11E8-B48F-1D18A9856A87
last_name: de Bono
orcid: 0000-0001-8347-0443
citation:
ama: Fenk LA, de Bono M. Environmental CO2 inhibits Caenorhabditis elegans egg-laying
by modulating olfactory neurons and evokes widespread changes in neural activity.
Proceedings of the National Academy of Sciences. 2015;112(27):E3525-E3534.
doi:10.1073/pnas.1423808112
apa: Fenk, L. A., & de Bono, M. (2015). Environmental CO2 inhibits Caenorhabditis
elegans egg-laying by modulating olfactory neurons and evokes widespread changes
in neural activity. Proceedings of the National Academy of Sciences. National
Academy of Sciences. https://doi.org/10.1073/pnas.1423808112
chicago: Fenk, Lorenz A., and Mario de Bono. “Environmental CO2 Inhibits Caenorhabditis
Elegans Egg-Laying by Modulating Olfactory Neurons and Evokes Widespread Changes
in Neural Activity.” Proceedings of the National Academy of Sciences. National
Academy of Sciences, 2015. https://doi.org/10.1073/pnas.1423808112.
ieee: L. A. Fenk and M. de Bono, “Environmental CO2 inhibits Caenorhabditis elegans
egg-laying by modulating olfactory neurons and evokes widespread changes in neural
activity,” Proceedings of the National Academy of Sciences, vol. 112, no.
27. National Academy of Sciences, pp. E3525–E3534, 2015.
ista: Fenk LA, de Bono M. 2015. Environmental CO2 inhibits Caenorhabditis elegans
egg-laying by modulating olfactory neurons and evokes widespread changes in neural
activity. Proceedings of the National Academy of Sciences. 112(27), E3525–E3534.
mla: Fenk, Lorenz A., and Mario de Bono. “Environmental CO2 Inhibits Caenorhabditis
Elegans Egg-Laying by Modulating Olfactory Neurons and Evokes Widespread Changes
in Neural Activity.” Proceedings of the National Academy of Sciences, vol.
112, no. 27, National Academy of Sciences, 2015, pp. E3525–34, doi:10.1073/pnas.1423808112.
short: L.A. Fenk, M. de Bono, Proceedings of the National Academy of Sciences 112
(2015) E3525–E3534.
date_created: 2019-03-19T14:15:50Z
date_published: 2015-07-07T00:00:00Z
date_updated: 2021-01-12T08:06:12Z
day: '07'
ddc:
- '570'
doi: 10.1073/pnas.1423808112
extern: '1'
external_id:
pmid:
- '26100886'
file:
- access_level: open_access
checksum: 3d2da5af8d72467e382a565abc2e003d
content_type: application/pdf
creator: kschuh
date_created: 2019-03-19T14:21:07Z
date_updated: 2020-07-14T12:47:20Z
file_id: '6119'
file_name: 2015_PNAS_Fenk.pdf
file_size: 2822681
relation: main_file
file_date_updated: 2020-07-14T12:47:20Z
has_accepted_license: '1'
intvolume: ' 112'
issue: '27'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: E3525-E3534
pmid: 1
publication: Proceedings of the National Academy of Sciences
publication_identifier:
issn:
- 0027-8424
- 1091-6490
publication_status: published
publisher: National Academy of Sciences
quality_controlled: '1'
status: public
title: Environmental CO2 inhibits Caenorhabditis elegans egg-laying by modulating
olfactory neurons and evokes widespread changes in neural activity
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 112
year: '2015'
...
---
_id: '6120'
abstract:
- lang: eng
text: Brains organize behavior and physiology to optimize the response to threats
or opportunities. We dissect how 21% O2, an indicator of surface exposure, reprograms
C. elegans' global state, inducing sustained locomotory arousal and altering expression
of neuropeptides, metabolic enzymes, and other non-neural genes. The URX O2-sensing
neurons drive arousal at 21% O2 by tonically activating the RMG interneurons.
Stimulating RMG is sufficient to switch behavioral state. Ablating the ASH, ADL,
or ASK sensory neurons connected to RMG by gap junctions does not disrupt arousal.
However, disrupting cation currents in these neurons curtails RMG neurosecretion
and arousal. RMG signals high O2 by peptidergic secretion. Neuropeptide reporters
reveal neural circuit state, as neurosecretion stimulates neuropeptide expression.
Neural imaging in unrestrained animals shows that URX and RMG encode O2 concentration
rather than behavior, while the activity of downstream interneurons such as AVB
and AIY reflect both O2 levels and the behavior being executed.
article_number: e04241
author:
- first_name: Patrick
full_name: Laurent, Patrick
last_name: Laurent
- first_name: Zoltan
full_name: Soltesz, Zoltan
last_name: Soltesz
- first_name: Geoffrey M
full_name: Nelson, Geoffrey M
last_name: Nelson
- first_name: Changchun
full_name: Chen, Changchun
last_name: Chen
- first_name: Fausto
full_name: Arellano-Carbajal, Fausto
last_name: Arellano-Carbajal
- first_name: Emmanuel
full_name: Levy, Emmanuel
last_name: Levy
- first_name: Mario
full_name: de Bono, Mario
id: 4E3FF80E-F248-11E8-B48F-1D18A9856A87
last_name: de Bono
orcid: 0000-0001-8347-0443
citation:
ama: Laurent P, Soltesz Z, Nelson GM, et al. Decoding a neural circuit controlling
global animal state in C. elegans. eLife. 2015;4. doi:10.7554/elife.04241
apa: Laurent, P., Soltesz, Z., Nelson, G. M., Chen, C., Arellano-Carbajal, F., Levy,
E., & de Bono, M. (2015). Decoding a neural circuit controlling global animal
state in C. elegans. ELife. eLife Sciences Publications. https://doi.org/10.7554/elife.04241
chicago: Laurent, Patrick, Zoltan Soltesz, Geoffrey M Nelson, Changchun Chen, Fausto
Arellano-Carbajal, Emmanuel Levy, and Mario de Bono. “Decoding a Neural Circuit
Controlling Global Animal State in C. Elegans.” ELife. eLife Sciences Publications,
2015. https://doi.org/10.7554/elife.04241.
ieee: P. Laurent et al., “Decoding a neural circuit controlling global animal
state in C. elegans,” eLife, vol. 4. eLife Sciences Publications, 2015.
ista: Laurent P, Soltesz Z, Nelson GM, Chen C, Arellano-Carbajal F, Levy E, de Bono
M. 2015. Decoding a neural circuit controlling global animal state in C. elegans.
eLife. 4, e04241.
mla: Laurent, Patrick, et al. “Decoding a Neural Circuit Controlling Global Animal
State in C. Elegans.” ELife, vol. 4, e04241, eLife Sciences Publications,
2015, doi:10.7554/elife.04241.
short: P. Laurent, Z. Soltesz, G.M. Nelson, C. Chen, F. Arellano-Carbajal, E. Levy,
M. de Bono, ELife 4 (2015).
date_created: 2019-03-19T14:23:51Z
date_published: 2015-03-11T00:00:00Z
date_updated: 2021-01-12T08:06:13Z
day: '11'
ddc:
- '570'
doi: 10.7554/elife.04241
extern: '1'
external_id:
pmid:
- '25760081'
file:
- access_level: open_access
checksum: cf641b7a363aecd0a101755d23dee7e0
content_type: application/pdf
creator: kschuh
date_created: 2019-03-19T14:29:43Z
date_updated: 2020-07-14T12:47:20Z
file_id: '6121'
file_name: 2015_elife_Laurent.pdf
file_size: 6723528
relation: main_file
file_date_updated: 2020-07-14T12:47:20Z
has_accepted_license: '1'
intvolume: ' 4'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
pmid: 1
publication: eLife
publication_identifier:
issn:
- 2050-084X
publication_status: published
publisher: eLife Sciences Publications
quality_controlled: '1'
status: public
title: Decoding a neural circuit controlling global animal state in C. elegans
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2015'
...
---
_id: '6507'
abstract:
- lang: eng
text: The osteoclast-associated receptor (OSCAR) is a collagen-binding immune receptor
with important roles in dendritic cell maturation and activation of inflammatory
monocytes as well as in osteoclastogenesis. The crystal structure of the OSCAR
ectodomain is presented, both free and in complex with a consensus triple-helical
peptide (THP). The structures revealed a collagen-binding site in each immunoglobulin-like
domain (D1 and D2). The THP binds near a predicted collagen-binding groove in
D1, but a more extensive interaction with D2 is facilitated by the unusually wide
D1-D2 interdomain angle in OSCAR. Direct binding assays, combined with site-directed
mutagenesis, confirm that the primary collagen-binding site in OSCAR resides in
D2, in marked contrast to the related collagen receptors, glycoprotein VI (GPVI)
and leukocyte-associated immunoglobulin-like receptor-1 (LAIR-1). Monomeric OSCAR
D1D2 binds to the consensus THP with a KD of 28 µM measured in solution, but shows
a higher affinity (KD 1.5 μM) when binding to a solid-phase THP, most likely due
to an avidity effect. These data suggest a 2-stage model for the interaction of
OSCAR with a collagen fibril, with transient, low-affinity interactions initiated
by the membrane-distal D1, followed by firm adhesion to the primary binding site
in D2.
author:
- first_name: Long
full_name: Zhou, Long
id: 3E751364-F248-11E8-B48F-1D18A9856A87
last_name: Zhou
orcid: 0000-0002-1864-8951
- first_name: J. M.
full_name: Hinerman, J. M.
last_name: Hinerman
- first_name: M.
full_name: Blaszczyk, M.
last_name: Blaszczyk
- first_name: J. L. C.
full_name: Miller, J. L. C.
last_name: Miller
- first_name: D. G.
full_name: Conrady, D. G.
last_name: Conrady
- first_name: A. D.
full_name: Barrow, A. D.
last_name: Barrow
- first_name: D. Y.
full_name: Chirgadze, D. Y.
last_name: Chirgadze
- first_name: D.
full_name: Bihan, D.
last_name: Bihan
- first_name: R. W.
full_name: Farndale, R. W.
last_name: Farndale
- first_name: A. B.
full_name: Herr, A. B.
last_name: Herr
citation:
ama: Zhou L, Hinerman JM, Blaszczyk M, et al. Structural basis for collagen recognition
by the immune receptor OSCAR. Blood. 2015;127(5):529-537. doi:10.1182/blood-2015-08-667055
apa: Zhou, L., Hinerman, J. M., Blaszczyk, M., Miller, J. L. C., Conrady, D. G.,
Barrow, A. D., … Herr, A. B. (2015). Structural basis for collagen recognition
by the immune receptor OSCAR. Blood. American Society of Hematology. https://doi.org/10.1182/blood-2015-08-667055
chicago: Zhou, Long, J. M. Hinerman, M. Blaszczyk, J. L. C. Miller, D. G. Conrady,
A. D. Barrow, D. Y. Chirgadze, D. Bihan, R. W. Farndale, and A. B. Herr. “Structural
Basis for Collagen Recognition by the Immune Receptor OSCAR.” Blood. American
Society of Hematology, 2015. https://doi.org/10.1182/blood-2015-08-667055.
ieee: L. Zhou et al., “Structural basis for collagen recognition by the immune
receptor OSCAR,” Blood, vol. 127, no. 5. American Society of Hematology,
pp. 529–537, 2015.
ista: Zhou L, Hinerman JM, Blaszczyk M, Miller JLC, Conrady DG, Barrow AD, Chirgadze
DY, Bihan D, Farndale RW, Herr AB. 2015. Structural basis for collagen recognition
by the immune receptor OSCAR. Blood. 127(5), 529–537.
mla: Zhou, Long, et al. “Structural Basis for Collagen Recognition by the Immune
Receptor OSCAR.” Blood, vol. 127, no. 5, American Society of Hematology,
2015, pp. 529–37, doi:10.1182/blood-2015-08-667055.
short: L. Zhou, J.M. Hinerman, M. Blaszczyk, J.L.C. Miller, D.G. Conrady, A.D. Barrow,
D.Y. Chirgadze, D. Bihan, R.W. Farndale, A.B. Herr, Blood 127 (2015) 529–537.
date_created: 2019-05-31T09:38:50Z
date_published: 2015-11-02T00:00:00Z
date_updated: 2021-01-12T08:07:47Z
day: '02'
doi: 10.1182/blood-2015-08-667055
extern: '1'
external_id:
pmid:
- '26552697'
intvolume: ' 127'
issue: '5'
language:
- iso: eng
month: '11'
oa_version: None
page: 529-537
pmid: 1
publication: Blood
publication_identifier:
issn:
- 0006-4971
- 1528-0020
publication_status: published
publisher: American Society of Hematology
quality_controlled: '1'
status: public
title: Structural basis for collagen recognition by the immune receptor OSCAR
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 127
year: '2015'
...
---
_id: '6736'
abstract:
- lang: eng
text: Motivated by the significant performance gains which polar codes experience
under successive cancellation list decoding, their scaling exponent is studied
as a function of the list size. In particular, the error probability is fixed,
and the tradeoff between the block length and back-off from capacity is analyzed.
A lower bound is provided on the error probability under MAP decoding with list
size L for any binary-input memoryless output-symmetric channel and for any class
of linear codes such that their minimum distance is unbounded as the block length
grows large. Then, it is shown that under MAP decoding, although the introduction
of a list can significantly improve the involved constants, the scaling exponent
itself, i.e., the speed at which capacity is approached, stays unaffected for
any finite list size. In particular, this result applies to polar codes, since
their minimum distance tends to infinity as the block length increases. A similar
result is proved for genie-aided successive cancellation decoding when transmission
takes place over the binary erasure channel, namely, the scaling exponent remains
constant for any fixed number of helps from the genie. Note that since genie-aided
successive cancellation decoding might be strictly worse than successive cancellation
list decoding, the problem of establishing the scaling exponent of the latter
remains open.
arxiv: 1
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Rudiger
full_name: Urbanke, Rudiger
last_name: Urbanke
citation:
ama: Mondelli M, Hassani H, Urbanke R. Scaling exponent of list decoders with applications
to polar codes. IEEE Transactions on Information Theory. 2015;61(9):4838-4851.
doi:10.1109/tit.2015.2453315
apa: Mondelli, M., Hassani, H., & Urbanke, R. (2015). Scaling exponent of list
decoders with applications to polar codes. IEEE Transactions on Information
Theory. IEEE. https://doi.org/10.1109/tit.2015.2453315
chicago: Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “Scaling Exponent
of List Decoders with Applications to Polar Codes.” IEEE Transactions on Information
Theory. IEEE, 2015. https://doi.org/10.1109/tit.2015.2453315.
ieee: M. Mondelli, H. Hassani, and R. Urbanke, “Scaling exponent of list decoders
with applications to polar codes,” IEEE Transactions on Information Theory,
vol. 61, no. 9. IEEE, pp. 4838–4851, 2015.
ista: Mondelli M, Hassani H, Urbanke R. 2015. Scaling exponent of list decoders
with applications to polar codes. IEEE Transactions on Information Theory. 61(9),
4838–4851.
mla: Mondelli, Marco, et al. “Scaling Exponent of List Decoders with Applications
to Polar Codes.” IEEE Transactions on Information Theory, vol. 61, no.
9, IEEE, 2015, pp. 4838–51, doi:10.1109/tit.2015.2453315.
short: M. Mondelli, H. Hassani, R. Urbanke, IEEE Transactions on Information Theory
61 (2015) 4838–4851.
date_created: 2019-07-31T06:50:34Z
date_published: 2015-09-01T00:00:00Z
date_updated: 2021-01-12T08:08:45Z
day: '01'
doi: 10.1109/tit.2015.2453315
extern: '1'
external_id:
arxiv:
- '1304.5220'
intvolume: ' 61'
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1304.5220
month: '09'
oa: 1
oa_version: Preprint
page: 4838-4851
publication: IEEE Transactions on Information Theory
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: Scaling exponent of list decoders with applications to polar codes
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2015'
...
---
_id: '6737'
abstract:
- lang: eng
text: This paper presents polar coding schemes for the two-user discrete memoryless
broadcast channel (DM-BC) which achieve Marton's region with both common and private
messages. This is the best achievable rate region known to date, and it is tight
for all classes of two-user DM-BCs whose capacity regions are known. To accomplish
this task, we first construct polar codes for both the superposition as well as
binning strategy. By combining these two schemes, we obtain Marton's region with
private messages only. Finally, we show how to handle the case of common information.
The proposed coding schemes possess the usual advantages of polar codes, i.e.,
they have low encoding and decoding complexity and a superpolynomial decay rate
of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who
recently introduced polar codes emulating the superposition and binning schemes.
To align the polar indices, for both schemes, their solution involves some degradedness
constraints that are assumed to hold between the auxiliary random variables and
channel outputs. To remove these constraints, we consider the transmission of
k blocks and employ a chaining construction that guarantees the proper alignment
of the polarized indices. The techniques described in this paper are quite general,
and they can be adopted to many other multiterminal scenarios whenever there polar
indices need to be aligned.
arxiv: 1
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
- first_name: Igal
full_name: Sason, Igal
last_name: Sason
- first_name: Rudiger
full_name: Urbanke, Rudiger
last_name: Urbanke
citation:
ama: Mondelli M, Hassani H, Sason I, Urbanke R. Achieving Marton’s region for broadcast
channels using polar codes. IEEE Transactions on Information Theory. 2015;61(2):783-800.
doi:10.1109/tit.2014.2368555
apa: Mondelli, M., Hassani, H., Sason, I., & Urbanke, R. (2015). Achieving Marton’s
region for broadcast channels using polar codes. IEEE Transactions on Information
Theory. IEEE. https://doi.org/10.1109/tit.2014.2368555
chicago: Mondelli, Marco, Hamed Hassani, Igal Sason, and Rudiger Urbanke. “Achieving
Marton’s Region for Broadcast Channels Using Polar Codes.” IEEE Transactions
on Information Theory. IEEE, 2015. https://doi.org/10.1109/tit.2014.2368555.
ieee: M. Mondelli, H. Hassani, I. Sason, and R. Urbanke, “Achieving Marton’s region
for broadcast channels using polar codes,” IEEE Transactions on Information
Theory, vol. 61, no. 2. IEEE, pp. 783–800, 2015.
ista: Mondelli M, Hassani H, Sason I, Urbanke R. 2015. Achieving Marton’s region
for broadcast channels using polar codes. IEEE Transactions on Information Theory.
61(2), 783–800.
mla: Mondelli, Marco, et al. “Achieving Marton’s Region for Broadcast Channels Using
Polar Codes.” IEEE Transactions on Information Theory, vol. 61, no. 2,
IEEE, 2015, pp. 783–800, doi:10.1109/tit.2014.2368555.
short: M. Mondelli, H. Hassani, I. Sason, R. Urbanke, IEEE Transactions on Information
Theory 61 (2015) 783–800.
date_created: 2019-07-31T07:03:38Z
date_published: 2015-02-01T00:00:00Z
date_updated: 2021-01-12T08:08:46Z
day: '01'
doi: 10.1109/tit.2014.2368555
extern: '1'
external_id:
arxiv:
- '1401.6060'
intvolume: ' 61'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1401.6060
month: '02'
oa: 1
oa_version: Preprint
page: 783-800
publication: IEEE Transactions on Information Theory
publication_status: published
publisher: IEEE
quality_controlled: '1'
status: public
title: Achieving Marton’s region for broadcast channels using polar codes
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2015'
...