---
_id: '7402'
abstract:
- lang: eng
text: Graph planning gives rise to fundamental algorithmic questions such as shortest
path, traveling salesman problem, etc. A classical problem in discrete planning
is to consider a weighted graph and construct a path that maximizes the sum of
weights for a given time horizon T. However, in many scenarios, the time horizon
is not fixed, but the stopping time is chosen according to some distribution such
that the expected stopping time is T. If the stopping time distribution is not
known, then to ensure robustness, the distribution is chosen by an adversary,
to represent the worst-case scenario. A stationary plan for every vertex always
chooses the same outgoing edge. For fixed horizon or fixed stopping-time distribution,
stationary plans are not sufficient for optimality. Quite surprisingly we show
that when an adversary chooses the stopping-time distribution with expected stopping
time T, then stationary plans are sufficient. While computing optimal stationary
plans for fixed horizon is NP-complete, we show that computing optimal stationary
plans under adversarial stopping-time distribution can be achieved in polynomial
time. Consequently, our polynomial-time algorithm for adversarial stopping time
also computes an optimal plan among all possible plans.
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: 'Chatterjee K, Doyen L. Graph planning with expected finite horizon. In: 34th
Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE; 2019:1-13. doi:10.1109/lics.2019.8785706'
apa: 'Chatterjee, K., & Doyen, L. (2019). Graph planning with expected finite
horizon. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science
(pp. 1–13). Vancouver, BC, Canada: IEEE. https://doi.org/10.1109/lics.2019.8785706'
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Graph Planning with Expected
Finite Horizon.” In 34th Annual ACM/IEEE Symposium on Logic in Computer Science,
1–13. IEEE, 2019. https://doi.org/10.1109/lics.2019.8785706.
ieee: K. Chatterjee and L. Doyen, “Graph planning with expected finite horizon,”
in 34th Annual ACM/IEEE Symposium on Logic in Computer Science, Vancouver,
BC, Canada, 2019, pp. 1–13.
ista: 'Chatterjee K, Doyen L. 2019. Graph planning with expected finite horizon.
34th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Symposium on
Logic in Computer Science, 1–13.'
mla: Chatterjee, Krishnendu, and Laurent Doyen. “Graph Planning with Expected Finite
Horizon.” 34th Annual ACM/IEEE Symposium on Logic in Computer Science,
IEEE, 2019, pp. 1–13, doi:10.1109/lics.2019.8785706.
short: K. Chatterjee, L. Doyen, in:, 34th Annual ACM/IEEE Symposium on Logic in
Computer Science, IEEE, 2019, pp. 1–13.
conference:
end_date: 2019-06-27
location: Vancouver, BC, Canada
name: 'LICS: Symposium on Logic in Computer Science'
start_date: 2019-06-24
date_created: 2020-01-29T16:18:33Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T14:48:11Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/lics.2019.8785706
external_id:
arxiv:
- '1802.03642'
isi:
- '000805002800001'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1802.03642
month: '06'
oa: 1
oa_version: Preprint
page: 1-13
publication: 34th Annual ACM/IEEE Symposium on Logic in Computer Science
publication_identifier:
isbn:
- '9781728136080'
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '11402'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Graph planning with expected finite horizon
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...
---
_id: '7451'
abstract:
- lang: eng
text: We prove that the observable telegraph signal accompanying the bistability
in the photon-blockade-breakdown regime of the driven and lossy Jaynes–Cummings
model is the finite-size precursor of what in the thermodynamic limit is a genuine
first-order phase transition. We construct a finite-size scaling of the system
parameters to a well-defined thermodynamic limit, in which the system remains
the same microscopic system, but the telegraph signal becomes macroscopic both
in its timescale and intensity. The existence of such a finite-size scaling completes
and justifies the classification of the photon-blockade-breakdown effect as a
first-order dissipative quantum phase transition.
article_number: '150'
article_processing_charge: No
article_type: original
author:
- first_name: A.
full_name: Vukics, A.
last_name: Vukics
- first_name: A.
full_name: Dombi, A.
last_name: Dombi
- first_name: Johannes M
full_name: Fink, Johannes M
id: 4B591CBA-F248-11E8-B48F-1D18A9856A87
last_name: Fink
orcid: 0000-0001-8112-028X
- first_name: P.
full_name: Domokos, P.
last_name: Domokos
citation:
ama: Vukics A, Dombi A, Fink JM, Domokos P. Finite-size scaling of the photon-blockade
breakdown dissipative quantum phase transition. Quantum. 2019;3. doi:10.22331/q-2019-06-03-150
apa: Vukics, A., Dombi, A., Fink, J. M., & Domokos, P. (2019). Finite-size scaling
of the photon-blockade breakdown dissipative quantum phase transition. Quantum.
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften.
https://doi.org/10.22331/q-2019-06-03-150
chicago: Vukics, A., A. Dombi, Johannes M Fink, and P. Domokos. “Finite-Size Scaling
of the Photon-Blockade Breakdown Dissipative Quantum Phase Transition.” Quantum.
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften,
2019. https://doi.org/10.22331/q-2019-06-03-150.
ieee: A. Vukics, A. Dombi, J. M. Fink, and P. Domokos, “Finite-size scaling of the
photon-blockade breakdown dissipative quantum phase transition,” Quantum,
vol. 3. Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften,
2019.
ista: Vukics A, Dombi A, Fink JM, Domokos P. 2019. Finite-size scaling of the photon-blockade
breakdown dissipative quantum phase transition. Quantum. 3, 150.
mla: Vukics, A., et al. “Finite-Size Scaling of the Photon-Blockade Breakdown Dissipative
Quantum Phase Transition.” Quantum, vol. 3, 150, Verein zur Förderung des
Open Access Publizierens in den Quantenwissenschaften, 2019, doi:10.22331/q-2019-06-03-150.
short: A. Vukics, A. Dombi, J.M. Fink, P. Domokos, Quantum 3 (2019).
date_created: 2020-02-05T09:57:57Z
date_published: 2019-06-03T00:00:00Z
date_updated: 2023-09-07T14:57:39Z
day: '03'
ddc:
- '530'
department:
- _id: JoFi
doi: 10.22331/q-2019-06-03-150
external_id:
arxiv:
- '1809.09737'
isi:
- '000469987500004'
file:
- access_level: open_access
checksum: 26b9ba8f0155d183f1ee55295934a17f
content_type: application/pdf
creator: dernst
date_created: 2020-02-11T09:25:23Z
date_updated: 2020-07-14T12:47:58Z
file_id: '7483'
file_name: 2019_Quantum_Vukics.pdf
file_size: 5805248
relation: main_file
file_date_updated: 2020-07-14T12:47:58Z
has_accepted_license: '1'
intvolume: ' 3'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
publication: Quantum
publication_identifier:
issn:
- 2521-327X
publication_status: published
publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
quality_controlled: '1'
status: public
title: Finite-size scaling of the photon-blockade breakdown dissipative quantum phase
transition
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 3
year: '2019'
...
---
_id: '7468'
abstract:
- lang: eng
text: We present a new proximal bundle method for Maximum-A-Posteriori (MAP) inference
in structured energy minimization problems. The method optimizes a Lagrangean
relaxation of the original energy minimization problem using a multi plane block-coordinate
Frank-Wolfe method that takes advantage of the specific structure of the Lagrangean
decomposition. We show empirically that our method outperforms state-of-the-art
Lagrangean decomposition based algorithms on some challenging Markov Random Field,
multi-label discrete tomography and graph matching problems.
article_number: 11138-11147
article_processing_charge: No
author:
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Swoboda P, Kolmogorov V. Map inference via block-coordinate Frank-Wolfe algorithm.
In: Proceedings of the IEEE Computer Society Conference on Computer Vision
and Pattern Recognition. Vol 2019-June. IEEE; 2019. doi:10.1109/CVPR.2019.01140'
apa: 'Swoboda, P., & Kolmogorov, V. (2019). Map inference via block-coordinate
Frank-Wolfe algorithm. In Proceedings of the IEEE Computer Society Conference
on Computer Vision and Pattern Recognition (Vol. 2019–June). Long Beach, CA,
United States: IEEE. https://doi.org/10.1109/CVPR.2019.01140'
chicago: Swoboda, Paul, and Vladimir Kolmogorov. “Map Inference via Block-Coordinate
Frank-Wolfe Algorithm.” In Proceedings of the IEEE Computer Society Conference
on Computer Vision and Pattern Recognition, Vol. 2019–June. IEEE, 2019. https://doi.org/10.1109/CVPR.2019.01140.
ieee: P. Swoboda and V. Kolmogorov, “Map inference via block-coordinate Frank-Wolfe
algorithm,” in Proceedings of the IEEE Computer Society Conference on Computer
Vision and Pattern Recognition, Long Beach, CA, United States, 2019, vol.
2019–June.
ista: 'Swoboda P, Kolmogorov V. 2019. Map inference via block-coordinate Frank-Wolfe
algorithm. Proceedings of the IEEE Computer Society Conference on Computer Vision
and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition
vol. 2019–June, 11138–11147.'
mla: Swoboda, Paul, and Vladimir Kolmogorov. “Map Inference via Block-Coordinate
Frank-Wolfe Algorithm.” Proceedings of the IEEE Computer Society Conference
on Computer Vision and Pattern Recognition, vol. 2019–June, 11138–11147, IEEE,
2019, doi:10.1109/CVPR.2019.01140.
short: P. Swoboda, V. Kolmogorov, in:, Proceedings of the IEEE Computer Society
Conference on Computer Vision and Pattern Recognition, IEEE, 2019.
conference:
end_date: 2019-06-20
location: Long Beach, CA, United States
name: 'CVPR: Conference on Computer Vision and Pattern Recognition'
start_date: 2019-06-15
date_created: 2020-02-09T23:00:52Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T14:54:24Z
day: '01'
department:
- _id: VlKo
doi: 10.1109/CVPR.2019.01140
ec_funded: 1
external_id:
arxiv:
- '1806.05049'
isi:
- '000542649304076'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1806.05049
month: '06'
oa: 1
oa_version: Preprint
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Proceedings of the IEEE Computer Society Conference on Computer Vision
and Pattern Recognition
publication_identifier:
isbn:
- '9781728132938'
issn:
- '10636919'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Map inference via block-coordinate Frank-Wolfe algorithm
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2019-June
year: '2019'
...
---
_id: '7415'
article_processing_charge: No
article_type: original
author:
- first_name: Jasmin
full_name: Morandell, Jasmin
id: 4739D480-F248-11E8-B48F-1D18A9856A87
last_name: Morandell
- first_name: Armel
full_name: Nicolas, Armel
id: 2A103192-F248-11E8-B48F-1D18A9856A87
last_name: Nicolas
- first_name: Lena A
full_name: Schwarz, Lena A
id: 29A8453C-F248-11E8-B48F-1D18A9856A87
last_name: Schwarz
- first_name: Gaia
full_name: Novarino, Gaia
id: 3E57A680-F248-11E8-B48F-1D18A9856A87
last_name: Novarino
orcid: 0000-0002-7673-7178
citation:
ama: Morandell J, Nicolas A, Schwarz LA, Novarino G. S.16.05 Illuminating the role
of the e3 ubiquitin ligase cullin3 in brain development and autism. European
Neuropsychopharmacology. 2019;29(Supplement 6):S11-S12. doi:10.1016/j.euroneuro.2019.09.040
apa: Morandell, J., Nicolas, A., Schwarz, L. A., & Novarino, G. (2019). S.16.05
Illuminating the role of the e3 ubiquitin ligase cullin3 in brain development
and autism. European Neuropsychopharmacology. Elsevier. https://doi.org/10.1016/j.euroneuro.2019.09.040
chicago: Morandell, Jasmin, Armel Nicolas, Lena A Schwarz, and Gaia Novarino. “S.16.05
Illuminating the Role of the E3 Ubiquitin Ligase Cullin3 in Brain Development
and Autism.” European Neuropsychopharmacology. Elsevier, 2019. https://doi.org/10.1016/j.euroneuro.2019.09.040.
ieee: J. Morandell, A. Nicolas, L. A. Schwarz, and G. Novarino, “S.16.05 Illuminating
the role of the e3 ubiquitin ligase cullin3 in brain development and autism,”
European Neuropsychopharmacology, vol. 29, no. Supplement 6. Elsevier,
pp. S11–S12, 2019.
ista: Morandell J, Nicolas A, Schwarz LA, Novarino G. 2019. S.16.05 Illuminating
the role of the e3 ubiquitin ligase cullin3 in brain development and autism. European
Neuropsychopharmacology. 29(Supplement 6), S11–S12.
mla: Morandell, Jasmin, et al. “S.16.05 Illuminating the Role of the E3 Ubiquitin
Ligase Cullin3 in Brain Development and Autism.” European Neuropsychopharmacology,
vol. 29, no. Supplement 6, Elsevier, 2019, pp. S11–12, doi:10.1016/j.euroneuro.2019.09.040.
short: J. Morandell, A. Nicolas, L.A. Schwarz, G. Novarino, European Neuropsychopharmacology
29 (2019) S11–S12.
date_created: 2020-01-30T10:07:41Z
date_published: 2019-12-13T00:00:00Z
date_updated: 2023-09-07T14:56:17Z
day: '13'
department:
- _id: GaNo
- _id: LifeSc
doi: 10.1016/j.euroneuro.2019.09.040
external_id:
isi:
- '000502657500021'
intvolume: ' 29'
isi: 1
issue: Supplement 6
language:
- iso: eng
month: '12'
oa_version: None
page: S11-S12
publication: European Neuropsychopharmacology
publication_identifier:
issn:
- 0924-977X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: S.16.05 Illuminating the role of the e3 ubiquitin ligase cullin3 in brain development
and autism
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 29
year: '2019'
...
---
_id: '7414'
article_processing_charge: No
article_type: original
author:
- first_name: Lisa
full_name: Knaus, Lisa
id: 3B2ABCF4-F248-11E8-B48F-1D18A9856A87
last_name: Knaus
- first_name: Dora-Clara
full_name: Tarlungeanu, Dora-Clara
id: 2ABCE612-F248-11E8-B48F-1D18A9856A87
last_name: Tarlungeanu
- first_name: Gaia
full_name: Novarino, Gaia
id: 3E57A680-F248-11E8-B48F-1D18A9856A87
last_name: Novarino
orcid: 0000-0002-7673-7178
citation:
ama: Knaus L, Tarlungeanu D-C, Novarino G. S.16.03 A homozygous missense mutation
in SLC7A5 leads to autism spectrum disorder and microcephaly. European Neuropsychopharmacology.
2019;29(Supplement 6):S11. doi:10.1016/j.euroneuro.2019.09.039
apa: Knaus, L., Tarlungeanu, D.-C., & Novarino, G. (2019). S.16.03 A homozygous
missense mutation in SLC7A5 leads to autism spectrum disorder and microcephaly.
European Neuropsychopharmacology. Elsevier. https://doi.org/10.1016/j.euroneuro.2019.09.039
chicago: Knaus, Lisa, Dora-Clara Tarlungeanu, and Gaia Novarino. “S.16.03 A Homozygous
Missense Mutation in SLC7A5 Leads to Autism Spectrum Disorder and Microcephaly.”
European Neuropsychopharmacology. Elsevier, 2019. https://doi.org/10.1016/j.euroneuro.2019.09.039.
ieee: L. Knaus, D.-C. Tarlungeanu, and G. Novarino, “S.16.03 A homozygous missense
mutation in SLC7A5 leads to autism spectrum disorder and microcephaly,” European
Neuropsychopharmacology, vol. 29, no. Supplement 6. Elsevier, p. S11, 2019.
ista: Knaus L, Tarlungeanu D-C, Novarino G. 2019. S.16.03 A homozygous missense
mutation in SLC7A5 leads to autism spectrum disorder and microcephaly. European
Neuropsychopharmacology. 29(Supplement 6), S11.
mla: Knaus, Lisa, et al. “S.16.03 A Homozygous Missense Mutation in SLC7A5 Leads
to Autism Spectrum Disorder and Microcephaly.” European Neuropsychopharmacology,
vol. 29, no. Supplement 6, Elsevier, 2019, p. S11, doi:10.1016/j.euroneuro.2019.09.039.
short: L. Knaus, D.-C. Tarlungeanu, G. Novarino, European Neuropsychopharmacology
29 (2019) S11.
date_created: 2020-01-30T10:06:15Z
date_published: 2019-12-13T00:00:00Z
date_updated: 2023-09-07T14:55:23Z
day: '13'
department:
- _id: GaNo
doi: 10.1016/j.euroneuro.2019.09.039
external_id:
isi:
- '000502657500020'
intvolume: ' 29'
isi: 1
issue: Supplement 6
language:
- iso: eng
month: '12'
oa_version: None
page: S11
publication: European Neuropsychopharmacology
publication_identifier:
issn:
- 0924-977X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: S.16.03 A homozygous missense mutation in SLC7A5 leads to autism spectrum disorder
and microcephaly
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 29
year: '2019'
...