---
_id: '18371'
abstract:
- lang: eng
text: We consider the problem of exact and inexact matching of weighted undirected
graphs, in which a bijective correspondence is sought to minimize a quadratic
weight disagreement. This computationally challenging problem is often relaxed
as a convex quadratic program, in which the space of permutations is replaced
by the space of doubly stochastic matrices. However, the applicability of such
a relaxation is poorly understood. We define a broad class of friendly graphs
characterized by an easily verifiable spectral property. We prove that for friendly
graphs, the convex relaxation is guaranteed to find the exact isomorphism or certify
its inexistence. This result is further extended to approximately isomorphic graphs,
for which we develop an explicit bound on the amount of weight disagreement under
which the relaxation is guaranteed to find the globally optimal approximate isomorphism.
We also show that in many cases, the graph matching problem can be further harmlessly
relaxed to a convex quadratic program with only n separable linear equality constraints,
which is substantially more efficient than the standard relaxation involving 2n
equality and n2 inequality constraints. Finally, we show that our results are
still valid for unfriendly graphs if additional information in the form of seeds
or attributes is allowed, with the latter satisfying an easy to verify spectral
characteristic.
article_processing_charge: No
article_type: original
author:
- first_name: Yonathan
full_name: Aflalo, Yonathan
last_name: Aflalo
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: Ron
full_name: Kimmel, Ron
last_name: Kimmel
citation:
ama: Aflalo Y, Bronstein AM, Kimmel R. On convex relaxation of graph isomorphism.
Proceedings of the National Academy of Sciences. 2015;112(10):2942-2947.
doi:10.1073/pnas.1401651112
apa: Aflalo, Y., Bronstein, A. M., & Kimmel, R. (2015). On convex relaxation
of graph isomorphism. Proceedings of the National Academy of Sciences.
National Academy of Sciences. https://doi.org/10.1073/pnas.1401651112
chicago: Aflalo, Yonathan, Alex M. Bronstein, and Ron Kimmel. “On Convex Relaxation
of Graph Isomorphism.” Proceedings of the National Academy of Sciences.
National Academy of Sciences, 2015. https://doi.org/10.1073/pnas.1401651112.
ieee: Y. Aflalo, A. M. Bronstein, and R. Kimmel, “On convex relaxation of graph
isomorphism,” Proceedings of the National Academy of Sciences, vol. 112,
no. 10. National Academy of Sciences, pp. 2942–2947, 2015.
ista: Aflalo Y, Bronstein AM, Kimmel R. 2015. On convex relaxation of graph isomorphism.
Proceedings of the National Academy of Sciences. 112(10), 2942–2947.
mla: Aflalo, Yonathan, et al. “On Convex Relaxation of Graph Isomorphism.” Proceedings
of the National Academy of Sciences, vol. 112, no. 10, National Academy of
Sciences, 2015, pp. 2942–47, doi:10.1073/pnas.1401651112.
short: Y. Aflalo, A.M. Bronstein, R. Kimmel, Proceedings of the National Academy
of Sciences 112 (2015) 2942–2947.
date_created: 2024-10-15T11:20:54Z
date_published: 2015-03-10T00:00:00Z
date_updated: 2024-11-12T08:54:37Z
day: '10'
doi: 10.1073/pnas.1401651112
extern: '1'
external_id:
pmid:
- '25713342'
fulldoi: https://doi.org/10.1073/pnas.1401651112
intvolume: ' 112'
issue: '10'
language:
- iso: eng
month: '03'
oa_version: None
page: 2942-2947
pmid: 1
publication: Proceedings of the National Academy of Sciences
publication_identifier:
eissn:
- 1091-6490
issn:
- 0027-8424
publication_status: published
publisher: National Academy of Sciences
quality_controlled: '1'
scopus_import: '1'
status: public
title: On convex relaxation of graph isomorphism
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 112
year: '2015'
...
---
_id: '1838'
abstract:
- lang: eng
text: Synthesis of program parts is particularly useful for concurrent systems.
However, most approaches do not support common design tasks, like modifying a
single process without having to re-synthesize or verify the whole system. Assume-guarantee
synthesis (AGS) provides robustness against modifications of system parts, but
thus far has been limited to the perfect information setting. This means that
local variables cannot be hidden from other processes, which renders synthesis
results cumbersome or even impossible to realize.We resolve this shortcoming by
defining AGS under partial information. We analyze the complexity and decidability
in different settings, showing that the problem has a high worstcase complexity
and is undecidable in many interesting cases. Based on these observations, we
present a pragmatic algorithm based on bounded synthesis, and demonstrate its
practical applicability on several examples.
acknowledgement: 'This work was supported by the Austrian Science Fund (FWF) through
the research network RiSE (S11406-N23, S11407-N23) and grant nr. P23499-N23, by
the European Commission through an ERC Start grant (279307: Graph Games) and project
STANCE (317753), as well as by the German Research Foundation (DFG) through SFB/TR
14 AVACS and project ASDPS(JA 2357/2-1).'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Roderick
full_name: Bloem, Roderick
last_name: Bloem
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Swen
full_name: Jacobs, Swen
last_name: Jacobs
- first_name: Robert
full_name: Könighofer, Robert
last_name: Könighofer
citation:
ama: 'Bloem R, Chatterjee K, Jacobs S, Könighofer R. Assume-guarantee synthesis
for concurrent reactive programs with partial information. In: Vol 9035. Springer;
2015:517-532. doi:10.1007/978-3-662-46681-0_50'
apa: 'Bloem, R., Chatterjee, K., Jacobs, S., & Könighofer, R. (2015). Assume-guarantee
synthesis for concurrent reactive programs with partial information (Vol. 9035,
pp. 517–532). Presented at the TACAS: Tools and Algorithms for the Construction
and Analysis of Systems, London, United Kingdom: Springer. https://doi.org/10.1007/978-3-662-46681-0_50'
chicago: Bloem, Roderick, Krishnendu Chatterjee, Swen Jacobs, and Robert Könighofer.
“Assume-Guarantee Synthesis for Concurrent Reactive Programs with Partial Information,”
9035:517–32. Springer, 2015. https://doi.org/10.1007/978-3-662-46681-0_50.
ieee: 'R. Bloem, K. Chatterjee, S. Jacobs, and R. Könighofer, “Assume-guarantee
synthesis for concurrent reactive programs with partial information,” presented
at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems,
London, United Kingdom, 2015, vol. 9035, pp. 517–532.'
ista: 'Bloem R, Chatterjee K, Jacobs S, Könighofer R. 2015. Assume-guarantee synthesis
for concurrent reactive programs with partial information. TACAS: Tools and Algorithms
for the Construction and Analysis of Systems, LNCS, vol. 9035, 517–532.'
mla: Bloem, Roderick, et al. Assume-Guarantee Synthesis for Concurrent Reactive
Programs with Partial Information. Vol. 9035, Springer, 2015, pp. 517–32,
doi:10.1007/978-3-662-46681-0_50.
short: R. Bloem, K. Chatterjee, S. Jacobs, R. Könighofer, in:, Springer, 2015, pp.
517–532.
conference:
end_date: 2015-04-18
location: London, United Kingdom
name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
start_date: 2015-04-11
date_created: 2018-12-11T11:54:17Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2025-06-11T07:09:03Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-662-46681-0_50
ec_funded: 1
external_id:
arxiv:
- '1411.4604'
fulldoi: https://doi.org/10.1007/978-3-662-46681-0_50
intvolume: ' 9035'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1411.4604
month: '01'
oa: 1
oa_version: Preprint
page: 517 - 532
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication_status: published
publisher: Springer
publist_id: '5264'
scopus_import: '1'
status: public
title: Assume-guarantee synthesis for concurrent reactive programs with partial information
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9035
year: '2015'
...
---
_id: '18380'
abstract:
- lang: eng
text: This work presents a novel approach for detecting inliers in a given set of
correspondences (matches). It does so without explicitly identifying any consensus
set, based on a method for inlier rate estimation (IRE). Given such an estimator
for the inlier rate, we also present an algorithm that detects a globally optimal
transformation. We provide a theoretical analysis of the IRE method using a stochastic
generative model on the continuous spaces of matches and transformations. This
model allows rigorous investigation of the limits of our IRE method for the case
of 2D-translation, further giving bounds and insights for the more general case.
Our theoretical analysis is validated empirically and is shown to hold in practice
for the more general case of 2D-affinities. In addition, we show that the combined
framework works on challenging cases of 2D-homography estimation, with very few
and possibly noisy inliers, where RANSAC generally fails.
article_number: '7299161'
article_processing_charge: No
author:
- first_name: Roee
full_name: Litman, Roee
last_name: Litman
- first_name: Simon
full_name: Korman, Simon
last_name: Korman
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: Shai
full_name: Avidan, Shai
last_name: Avidan
citation:
ama: 'Litman R, Korman S, Bronstein AM, Avidan S. Inverting RANSAC: Global model
detection via inlier rate estimation. In: 2015 IEEE Conference on Computer
Vision and Pattern Recognition (CVPR). IEEE; 2015. doi:10.1109/cvpr.2015.7299161'
apa: 'Litman, R., Korman, S., Bronstein, A. M., & Avidan, S. (2015). Inverting
RANSAC: Global model detection via inlier rate estimation. In 2015 IEEE Conference
on Computer Vision and Pattern Recognition (CVPR). Boston, MA, United States:
IEEE. https://doi.org/10.1109/cvpr.2015.7299161'
chicago: 'Litman, Roee, Simon Korman, Alex M. Bronstein, and Shai Avidan. “Inverting
RANSAC: Global Model Detection via Inlier Rate Estimation.” In 2015 IEEE Conference
on Computer Vision and Pattern Recognition (CVPR). IEEE, 2015. https://doi.org/10.1109/cvpr.2015.7299161.'
ieee: 'R. Litman, S. Korman, A. M. Bronstein, and S. Avidan, “Inverting RANSAC:
Global model detection via inlier rate estimation,” in 2015 IEEE Conference
on Computer Vision and Pattern Recognition (CVPR), Boston, MA, United States,
2015.'
ista: 'Litman R, Korman S, Bronstein AM, Avidan S. 2015. Inverting RANSAC: Global
model detection via inlier rate estimation. 2015 IEEE Conference on Computer Vision
and Pattern Recognition (CVPR). IEEE Conference on Computer Vision and Pattern
Recognition, 7299161.'
mla: 'Litman, Roee, et al. “Inverting RANSAC: Global Model Detection via Inlier
Rate Estimation.” 2015 IEEE Conference on Computer Vision and Pattern Recognition
(CVPR), 7299161, IEEE, 2015, doi:10.1109/cvpr.2015.7299161.'
short: R. Litman, S. Korman, A.M. Bronstein, S. Avidan, in:, 2015 IEEE Conference
on Computer Vision and Pattern Recognition (CVPR), IEEE, 2015.
conference:
end_date: 2015-06-12
location: Boston, MA, United States
name: IEEE Conference on Computer Vision and Pattern Recognition
start_date: 2015-06-07
date_created: 2024-10-15T11:20:54Z
date_published: 2015-10-15T00:00:00Z
date_updated: 2024-12-04T14:06:06Z
day: '15'
doi: 10.1109/cvpr.2015.7299161
extern: '1'
fulldoi: https://doi.org/10.1109/cvpr.2015.7299161
language:
- iso: eng
month: '10'
oa_version: None
publication: 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
publication_identifier:
eissn:
- 1063-6919
isbn:
- '9781467369640'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Inverting RANSAC: Global model detection via inlier rate estimation'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '18387'
abstract:
- lang: eng
text: Sparse models in dictionary learning have been successfully applied in a wide
variety of machine learning and computer vision problems, and have also recently
been of increasing research interest. Another interesting related problem based
on a linear equality constraint, namely the sparse null space problem (SNS), first
appeared in 1986, and has since inspired results on sparse basis pursuit. In this
paper, we investigate the relation between the SNS problem and the analysis dictionary
learning problem, and show that the SNS problem plays a central role, and may
be utilized to solve dictionary learning problems. Moreover, we propose an efficient
algorithm of sparse null space basis pursuit, and extend it to a solution of analysis
dictionary learning. Experimental results on numerical synthetic data and real-world
data are further presented to validate the performance of our method.
article_number: '7178678'
article_processing_charge: No
author:
- first_name: Xiao
full_name: Bian, Xiao
last_name: Bian
- first_name: Hamid
full_name: Krim, Hamid
last_name: Krim
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: Liyi
full_name: Dai, Liyi
last_name: Dai
citation:
ama: 'Bian X, Krim H, Bronstein AM, Dai L. Sparse null space basis pursuit and analysis
dictionary learning for high-dimensional data analysis. In: 2015 IEEE International
Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE; 2015.
doi:10.1109/icassp.2015.7178678'
apa: 'Bian, X., Krim, H., Bronstein, A. M., & Dai, L. (2015). Sparse null space
basis pursuit and analysis dictionary learning for high-dimensional data analysis.
In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing
(ICASSP). South Brisbane, QLD, Australia: IEEE. https://doi.org/10.1109/icassp.2015.7178678'
chicago: Bian, Xiao, Hamid Krim, Alex M. Bronstein, and Liyi Dai. “Sparse Null Space
Basis Pursuit and Analysis Dictionary Learning for High-Dimensional Data Analysis.”
In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing
(ICASSP). IEEE, 2015. https://doi.org/10.1109/icassp.2015.7178678.
ieee: X. Bian, H. Krim, A. M. Bronstein, and L. Dai, “Sparse null space basis pursuit
and analysis dictionary learning for high-dimensional data analysis,” in 2015
IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),
South Brisbane, QLD, Australia, 2015.
ista: Bian X, Krim H, Bronstein AM, Dai L. 2015. Sparse null space basis pursuit
and analysis dictionary learning for high-dimensional data analysis. 2015 IEEE
International Conference on Acoustics, Speech and Signal Processing (ICASSP).
40th IEEE International Conference on Acoustics, Speech, and Signal Processing,
7178678.
mla: Bian, Xiao, et al. “Sparse Null Space Basis Pursuit and Analysis Dictionary
Learning for High-Dimensional Data Analysis.” 2015 IEEE International Conference
on Acoustics, Speech and Signal Processing (ICASSP), 7178678, IEEE, 2015,
doi:10.1109/icassp.2015.7178678.
short: X. Bian, H. Krim, A.M. Bronstein, L. Dai, in:, 2015 IEEE International Conference
on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2015.
conference:
end_date: 2015-04-24
location: South Brisbane, QLD, Australia
name: 40th IEEE International Conference on Acoustics, Speech, and Signal Processing
start_date: 2015-04-19
date_created: 2024-10-15T11:20:54Z
date_published: 2015-08-06T00:00:00Z
date_updated: 2024-12-04T14:01:05Z
day: '06'
doi: 10.1109/icassp.2015.7178678
extern: '1'
fulldoi: https://doi.org/10.1109/icassp.2015.7178678
language:
- iso: eng
month: '08'
oa_version: None
publication: 2015 IEEE International Conference on Acoustics, Speech and Signal Processing
(ICASSP)
publication_identifier:
eisbn:
- '9781467369978'
eissn:
- 2379-190X
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sparse null space basis pursuit and analysis dictionary learning for high-dimensional
data analysis
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1839'
abstract:
- lang: eng
text: We present MultiGain, a tool to synthesize strategies for Markov decision
processes (MDPs) with multiple mean-payoff objectives. Our models are described
in PRISM, and our tool uses the existing interface and simulator of PRISM. Our
tool extends PRISM by adding novel algorithms for multiple mean-payoff objectives,
and also provides features such as (i) generating strategies and exploring them
for simulation, and checking them with respect to other properties; and (ii) generating
an approximate Pareto curve for two mean-payoff objectives. In addition, we present
a new practical algorithm for the analysis of MDPs with multiple mean-payoff objectives
under memoryless strategies.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Tomáš
full_name: Brázdil, Tomáš
last_name: Brázdil
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Vojtěch
full_name: Forejt, Vojtěch
last_name: Forejt
- first_name: Antonín
full_name: Kučera, Antonín
last_name: Kučera
citation:
ama: 'Brázdil T, Chatterjee K, Forejt V, Kučera A. Multigain: A controller synthesis
tool for MDPs with multiple mean-payoff objectives. 2015;9035:181-187. doi:10.1007/978-3-662-46681-0_12'
apa: 'Brázdil, T., Chatterjee, K., Forejt, V., & Kučera, A. (2015). Multigain:
A controller synthesis tool for MDPs with multiple mean-payoff objectives. Presented
at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems,
London, United Kingdom: Springer. https://doi.org/10.1007/978-3-662-46681-0_12'
chicago: 'Brázdil, Tomáš, Krishnendu Chatterjee, Vojtěch Forejt, and Antonín Kučera.
“Multigain: A Controller Synthesis Tool for MDPs with Multiple Mean-Payoff Objectives.”
Lecture Notes in Computer Science. Springer, 2015. https://doi.org/10.1007/978-3-662-46681-0_12.'
ieee: 'T. Brázdil, K. Chatterjee, V. Forejt, and A. Kučera, “Multigain: A controller
synthesis tool for MDPs with multiple mean-payoff objectives,” vol. 9035. Springer,
pp. 181–187, 2015.'
ista: 'Brázdil T, Chatterjee K, Forejt V, Kučera A. 2015. Multigain: A controller
synthesis tool for MDPs with multiple mean-payoff objectives. 9035, 181–187.'
mla: 'Brázdil, Tomáš, et al. Multigain: A Controller Synthesis Tool for MDPs
with Multiple Mean-Payoff Objectives. Vol. 9035, Springer, 2015, pp. 181–87,
doi:10.1007/978-3-662-46681-0_12.'
short: T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, 9035 (2015) 181–187.
conference:
end_date: 2015-04-18
location: London, United Kingdom
name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
start_date: 2015-04-11
date_created: 2018-12-11T11:54:18Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2025-06-11T07:09:21Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-662-46681-0_12
ec_funded: 1
external_id:
arxiv:
- '1501.03093'
fulldoi: https://doi.org/10.1007/978-3-662-46681-0_12
intvolume: ' 9035'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1501.03093
month: '01'
oa: 1
oa_version: Preprint
page: 181 - 187
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication_status: published
publisher: Springer
publist_id: '5263'
quality_controlled: '1'
scopus_import: '1'
series_title: Lecture Notes in Computer Science
status: public
title: 'Multigain: A controller synthesis tool for MDPs with multiple mean-payoff
objectives'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9035
year: '2015'
...
---
_id: '1840'
abstract:
- lang: eng
text: In this paper, we present a method for reducing a regular, discrete-time Markov
chain (DTMC) to another DTMC with a given, typically much smaller number of states.
The cost of reduction is defined as the Kullback-Leibler divergence rate between
a projection of the original process through a partition function and a DTMC on
the correspondingly partitioned state space. Finding the reduced model with minimal
cost is computationally expensive, as it requires an exhaustive search among all
state space partitions, and an exact evaluation of the reduction cost for each
candidate partition. Our approach deals with the latter problem by minimizing
an upper bound on the reduction cost instead of minimizing the exact cost. The
proposed upper bound is easy to compute and it is tight if the original chain
is lumpable with respect to the partition. Then, we express the problem in the
form of information bottleneck optimization, and propose using the agglomerative
information bottleneck algorithm for searching a suboptimal partition greedily,
rather than exhaustively. The theory is illustrated with examples and one application
scenario in the context of modeling bio-molecular interactions.
acknowledgement: "This work was supported by the Austrian Research Association under
Project 06/12684, by the Swiss National Science Foundation (SNSF) under Grant PP00P2
128503/1, by the SystemsX.ch (the Swiss Inititative for Systems Biology), and by
a SNSF Early Postdoc.Mobility Fellowship grant P2EZP2_148797.\r\n"
article_processing_charge: No
arxiv: 1
author:
- first_name: Bernhard
full_name: Geiger, Bernhard
last_name: Geiger
- first_name: Tatjana
full_name: Petrov, Tatjana
id: 3D5811FC-F248-11E8-B48F-1D18A9856A87
last_name: Petrov
orcid: 0000-0002-9041-0905
- first_name: Gernot
full_name: Kubin, Gernot
last_name: Kubin
- first_name: Heinz
full_name: Koeppl, Heinz
last_name: Koeppl
citation:
ama: Geiger B, Petrov T, Kubin G, Koeppl H. Optimal Kullback-Leibler aggregation
via information bottleneck. IEEE Transactions on Automatic Control. 2015;60(4):1010-1022.
doi:10.1109/TAC.2014.2364971
apa: Geiger, B., Petrov, T., Kubin, G., & Koeppl, H. (2015). Optimal Kullback-Leibler
aggregation via information bottleneck. IEEE Transactions on Automatic Control.
IEEE. https://doi.org/10.1109/TAC.2014.2364971
chicago: Geiger, Bernhard, Tatjana Petrov, Gernot Kubin, and Heinz Koeppl. “Optimal
Kullback-Leibler Aggregation via Information Bottleneck.” IEEE Transactions
on Automatic Control. IEEE, 2015. https://doi.org/10.1109/TAC.2014.2364971.
ieee: B. Geiger, T. Petrov, G. Kubin, and H. Koeppl, “Optimal Kullback-Leibler aggregation
via information bottleneck,” IEEE Transactions on Automatic Control, vol.
60, no. 4. IEEE, pp. 1010–1022, 2015.
ista: Geiger B, Petrov T, Kubin G, Koeppl H. 2015. Optimal Kullback-Leibler aggregation
via information bottleneck. IEEE Transactions on Automatic Control. 60(4), 1010–1022.
mla: Geiger, Bernhard, et al. “Optimal Kullback-Leibler Aggregation via Information
Bottleneck.” IEEE Transactions on Automatic Control, vol. 60, no. 4, IEEE,
2015, pp. 1010–22, doi:10.1109/TAC.2014.2364971.
short: B. Geiger, T. Petrov, G. Kubin, H. Koeppl, IEEE Transactions on Automatic
Control 60 (2015) 1010–1022.
date_created: 2018-12-11T11:54:18Z
date_published: 2015-04-01T00:00:00Z
date_updated: 2025-09-23T09:45:33Z
day: '01'
department:
- _id: CaGu
- _id: ToHe
doi: 10.1109/TAC.2014.2364971
external_id:
arxiv:
- '1304.6603'
isi:
- '000351731600009'
fulldoi: https://doi.org/10.1109/TAC.2014.2364971
intvolume: ' 60'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1304.6603
month: '04'
oa: 1
oa_version: Preprint
page: 1010 - 1022
publication: IEEE Transactions on Automatic Control
publication_identifier:
issn:
- 0018-9286
publication_status: published
publisher: IEEE
publist_id: '5262'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimal Kullback-Leibler aggregation via information bottleneck
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 60
year: '2015'
...
---
_id: '18400'
abstract:
- lang: eng
text: We propose a method and a prototype imaging system for real-time reconstruction
of volumetric piecewise-smooth scattering media. The volume is illuminated by
a sequence of structured binary patterns emitted from a fan beam projector, and
the scattered light is collected by a two-dimensional sensor, thus creating an
under-complete set of compressed measurements. We show a fixed-complexity and
latency reconstruction algorithm capable of estimating the scattering coefficients
in real-time. We also show a simple greedy algorithm for learning the optimal
illumination patterns. Our results demonstrate faithful reconstruction from highly
compressed measurements. Furthermore, a method for compressed registration of
the measured volume to a known template is presented, showing excellent alignment
with just a single projection. Though our prototype system operates in visible
light, the presented methodology is suitable for fast x-ray scattering imaging,
in particular in real-time vascular medical imaging.
article_number: '7025264'
article_processing_charge: No
author:
- first_name: Ohad
full_name: Menashe, Ohad
last_name: Menashe
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
citation:
ama: 'Menashe O, Bronstein AM. Real-time compressed imaging of scattering volumes.
In: 2014 IEEE International Conference on Image Processing (ICIP). IEEE;
2015. doi:10.1109/icip.2014.7025264'
apa: 'Menashe, O., & Bronstein, A. M. (2015). Real-time compressed imaging of
scattering volumes. In 2014 IEEE International Conference on Image Processing
(ICIP). Paris, France: IEEE. https://doi.org/10.1109/icip.2014.7025264'
chicago: Menashe, Ohad, and Alex M. Bronstein. “Real-Time Compressed Imaging of
Scattering Volumes.” In 2014 IEEE International Conference on Image Processing
(ICIP). IEEE, 2015. https://doi.org/10.1109/icip.2014.7025264.
ieee: O. Menashe and A. M. Bronstein, “Real-time compressed imaging of scattering
volumes,” in 2014 IEEE International Conference on Image Processing (ICIP),
Paris, France, 2015.
ista: Menashe O, Bronstein AM. 2015. Real-time compressed imaging of scattering
volumes. 2014 IEEE International Conference on Image Processing (ICIP). IEEE International
Conference on Image Processing, 7025264.
mla: Menashe, Ohad, and Alex M. Bronstein. “Real-Time Compressed Imaging of Scattering
Volumes.” 2014 IEEE International Conference on Image Processing (ICIP),
7025264, IEEE, 2015, doi:10.1109/icip.2014.7025264.
short: O. Menashe, A.M. Bronstein, in:, 2014 IEEE International Conference on Image
Processing (ICIP), IEEE, 2015.
conference:
end_date: 2014-10-30
location: Paris, France
name: IEEE International Conference on Image Processing
start_date: 2014-10-27
date_created: 2024-10-15T11:20:54Z
date_published: 2015-01-29T00:00:00Z
date_updated: 2024-12-04T13:56:28Z
day: '29'
doi: 10.1109/icip.2014.7025264
extern: '1'
fulldoi: https://doi.org/10.1109/icip.2014.7025264
language:
- iso: eng
month: '01'
oa_version: None
publication: 2014 IEEE International Conference on Image Processing (ICIP)
publication_identifier:
eisbn:
- '9781479957514'
eissn:
- 2381-8549
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Real-time compressed imaging of scattering volumes
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '18401'
abstract:
- lang: eng
text: Intel's newly-announced low-cost RealSense 3D camera claims significantly
better precision than other currently available low-cost platforms and is expected
to become ubiquitous in laptops and mobile devices starting this year. In this
paper, we demonstrate for the first time that the RealSense camera can be easily
converted into a real low-cost gaze tracker. Gaze has become increasingly relevant
as an input for human-computer interaction due to its association with attention.
It is also critical in clinical mental health diagnosis. We present a novel 3D
gaze and fixation tracker based on the eye surface geometry captured with the
RealSense 3D camera. First, eye surface 3D point clouds are segmented to extract
the pupil center and iris using registered infrared images. With non-ellipsoid
eye surface and single fixation point assumptions, pupil centers and iris normal
vectors are used to first estimate gaze (for each eye), and then a single fixation
point for both eyes simultaneously using a RANSAC-based approach. With a simple
learned bias field correction model, the fixation tracker demonstrates mean error
of approximately 1 cm at 20-30 cm, which is sufficiently adequate for gaze and
fixation tracking in human-computer interaction and mental health diagnosis applications.
article_number: '7351256'
article_processing_charge: No
author:
- first_name: Mark
full_name: Draelos, Mark
last_name: Draelos
- first_name: Qiang
full_name: Qiu, Qiang
last_name: Qiu
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: Guillermo
full_name: Sapiro, Guillermo
last_name: Sapiro
citation:
ama: 'Draelos M, Qiu Q, Bronstein AM, Sapiro G. Intel realsense = Real low cost
gaze. In: 2015 IEEE International Conference on Image Processing (ICIP).
IEEE; 2015. doi:10.1109/icip.2015.7351256'
apa: 'Draelos, M., Qiu, Q., Bronstein, A. M., & Sapiro, G. (2015). Intel realsense
= Real low cost gaze. In 2015 IEEE International Conference on Image Processing
(ICIP). Quebec City, QC, Canada: IEEE. https://doi.org/10.1109/icip.2015.7351256'
chicago: Draelos, Mark, Qiang Qiu, Alex M. Bronstein, and Guillermo Sapiro. “Intel
Realsense = Real Low Cost Gaze.” In 2015 IEEE International Conference on Image
Processing (ICIP). IEEE, 2015. https://doi.org/10.1109/icip.2015.7351256.
ieee: M. Draelos, Q. Qiu, A. M. Bronstein, and G. Sapiro, “Intel realsense = Real
low cost gaze,” in 2015 IEEE International Conference on Image Processing (ICIP),
Quebec City, QC, Canada, 2015.
ista: Draelos M, Qiu Q, Bronstein AM, Sapiro G. 2015. Intel realsense = Real low
cost gaze. 2015 IEEE International Conference on Image Processing (ICIP). IEEE
International Conference on Image Processing, 7351256.
mla: Draelos, Mark, et al. “Intel Realsense = Real Low Cost Gaze.” 2015 IEEE
International Conference on Image Processing (ICIP), 7351256, IEEE, 2015,
doi:10.1109/icip.2015.7351256.
short: M. Draelos, Q. Qiu, A.M. Bronstein, G. Sapiro, in:, 2015 IEEE International
Conference on Image Processing (ICIP), IEEE, 2015.
conference:
end_date: 2015-09-30
location: Quebec City, QC, Canada
name: IEEE International Conference on Image Processing
start_date: 2015-09-27
date_created: 2024-10-15T11:20:54Z
date_published: 2015-12-10T00:00:00Z
date_updated: 2024-12-05T08:13:05Z
day: '10'
doi: 10.1109/icip.2015.7351256
extern: '1'
fulldoi: https://doi.org/10.1109/icip.2015.7351256
language:
- iso: eng
month: '12'
oa_version: None
publication: 2015 IEEE International Conference on Image Processing (ICIP)
publication_identifier:
eisbn:
- '9781479983391'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Intel realsense = Real low cost gaze
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
OA_place: repository
OA_type: green
_id: '1841'
abstract:
- lang: eng
text: We propose a new family of message passing techniques for MAP estimation in
graphical models which we call Sequential Reweighted Message Passing (SRMP). Special
cases include well-known techniques such as Min-Sum Diffusion (MSD) and a faster
Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation
is simpler than the original derivation of TRW-S, and does not involve a decomposition
into trees. This allows easy generalizations. The new family of algorithms can
be viewed as a generalization of TRW-S from pairwise to higher-order graphical
models. We test SRMP on several real-world problems with promising results.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. A new look at reweighted message passing. IEEE Transactions
on Pattern Analysis and Machine Intelligence. 2015;37(5):919-930. doi:10.1109/TPAMI.2014.2363465
apa: Kolmogorov, V. (2015). A new look at reweighted message passing. IEEE Transactions
on Pattern Analysis and Machine Intelligence. IEEE. https://doi.org/10.1109/TPAMI.2014.2363465
chicago: Kolmogorov, Vladimir. “A New Look at Reweighted Message Passing.” IEEE
Transactions on Pattern Analysis and Machine Intelligence. IEEE, 2015. https://doi.org/10.1109/TPAMI.2014.2363465.
ieee: V. Kolmogorov, “A new look at reweighted message passing,” IEEE Transactions
on Pattern Analysis and Machine Intelligence, vol. 37, no. 5. IEEE, pp. 919–930,
2015.
ista: Kolmogorov V. 2015. A new look at reweighted message passing. IEEE Transactions
on Pattern Analysis and Machine Intelligence. 37(5), 919–930.
mla: Kolmogorov, Vladimir. “A New Look at Reweighted Message Passing.” IEEE Transactions
on Pattern Analysis and Machine Intelligence, vol. 37, no. 5, IEEE, 2015,
pp. 919–30, doi:10.1109/TPAMI.2014.2363465.
short: V. Kolmogorov, IEEE Transactions on Pattern Analysis and Machine Intelligence
37 (2015) 919–930.
corr_author: '1'
date_created: 2018-12-11T11:54:18Z
date_published: 2015-05-01T00:00:00Z
date_updated: 2025-09-22T14:33:14Z
day: '01'
department:
- _id: VlKo
doi: 10.1109/TPAMI.2014.2363465
ec_funded: 1
external_id:
arxiv:
- '1309.5655'
isi:
- '000352533000002'
fulldoi: https://doi.org/10.1109/TPAMI.2014.2363465
intvolume: ' 37'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1309.5655
month: '05'
oa: 1
oa_version: Preprint
page: 919 - 930
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: IEEE Transactions on Pattern Analysis and Machine Intelligence
publication_status: published
publisher: IEEE
publist_id: '5261'
quality_controlled: '1'
related_material:
record:
- id: '2273'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: A new look at reweighted message passing
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 37
year: '2015'
...
---
_id: '18415'
abstract:
- lang: eng
text: Parsimony, including sparsity and low rank, has been shown to successfully
model data in numerous machine learning and signal processing tasks. Traditionally,
such modeling approaches rely on an iterative algorithm that minimizes an objective
function with parsimony-promoting terms. The inherently sequential structure and
data-dependent complexity and latency of iterative optimization constitute a major
limitation in many applications requiring real-time performance or involving large-scale
data. Another limitation encountered by these modeling techniques is the difficulty
of their inclusion in discriminative learning scenarios. In this work, we propose
to move the emphasis from the model to the pursuit algorithm, and develop a process-centric
view of parsimonious modeling, in which a learned deterministic fixed-complexity
pursuit process is used in lieu of iterative optimization. We show a principled
way to construct learnable pursuit process architectures for structured sparse
and robust low rank models, derived from the iteration of proximal descent algorithms.
These architectures learn to approximate the exact parsimonious representation
at a fraction of the complexity of the standard optimization methods. We also
show that appropriate training regimes allow to naturally extend parsimonious
models to discriminative settings. State-of-the-art results are demonstrated on
several challenging problems in image and audio processing with several orders
of magnitude speed-up compared to the exact optimization algorithms.
article_processing_charge: No
arxiv: 1
author:
- first_name: P.
full_name: Sprechmann, P.
last_name: Sprechmann
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: G.
full_name: Sapiro, G.
last_name: Sapiro
citation:
ama: Sprechmann P, Bronstein AM, Sapiro G. Learning efficient sparse and low rank
models. IEEE Transactions on Pattern Analysis and Machine Intelligence.
2015;37(9):1821-1833. doi:10.1109/tpami.2015.2392779
apa: Sprechmann, P., Bronstein, A. M., & Sapiro, G. (2015). Learning efficient
sparse and low rank models. IEEE Transactions on Pattern Analysis and Machine
Intelligence. IEEE. https://doi.org/10.1109/tpami.2015.2392779
chicago: Sprechmann, P., Alex M. Bronstein, and G. Sapiro. “Learning Efficient Sparse
and Low Rank Models.” IEEE Transactions on Pattern Analysis and Machine Intelligence.
IEEE, 2015. https://doi.org/10.1109/tpami.2015.2392779.
ieee: P. Sprechmann, A. M. Bronstein, and G. Sapiro, “Learning efficient sparse
and low rank models,” IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 37, no. 9. IEEE, pp. 1821–1833, 2015.
ista: Sprechmann P, Bronstein AM, Sapiro G. 2015. Learning efficient sparse and
low rank models. IEEE Transactions on Pattern Analysis and Machine Intelligence.
37(9), 1821–1833.
mla: Sprechmann, P., et al. “Learning Efficient Sparse and Low Rank Models.” IEEE
Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 9,
IEEE, 2015, pp. 1821–33, doi:10.1109/tpami.2015.2392779.
short: P. Sprechmann, A.M. Bronstein, G. Sapiro, IEEE Transactions on Pattern Analysis
and Machine Intelligence 37 (2015) 1821–1833.
date_created: 2024-10-15T11:20:55Z
date_published: 2015-09-01T00:00:00Z
date_updated: 2024-12-18T11:40:35Z
day: '01'
doi: 10.1109/tpami.2015.2392779
extern: '1'
external_id:
arxiv:
- '1212.3631'
pmid:
- '26353129'
fulldoi: https://doi.org/10.1109/tpami.2015.2392779
intvolume: ' 37'
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1212.3631
month: '09'
oa: 1
oa_version: Preprint
page: 1821-1833
pmid: 1
publication: IEEE Transactions on Pattern Analysis and Machine Intelligence
publication_identifier:
eissn:
- 1939-3539
issn:
- 0162-8828
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Learning efficient sparse and low rank models
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 37
year: '2015'
...
---
_id: '18416'
abstract:
- lang: eng
text: We construct an extension of spectral and diffusion geometry to multiple modalities
through simultaneous diagonalization of Laplacian matrices. This naturally extends
classical data analysis tools based on spectral geometry, such as diffusion maps
and spectral clustering. We provide several synthetic and real examples of manifold
learning, object classification, and clustering, showing that the joint spectral
geometry better captures the inherent structure of multi-modal data. We also show
the relation of many previous approaches for multimodal manifold analysis to our
framework.
article_processing_charge: No
author:
- first_name: Davide
full_name: Eynard, Davide
last_name: Eynard
- first_name: Artiom
full_name: Kovnatsky, Artiom
last_name: Kovnatsky
- first_name: Michael M.
full_name: Bronstein, Michael M.
last_name: Bronstein
- first_name: Klaus
full_name: Glashoff, Klaus
last_name: Glashoff
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
citation:
ama: Eynard D, Kovnatsky A, Bronstein MM, Glashoff K, Bronstein AM. Multimodal manifold
snalysis by simultaneous diagonalization of Laplacians. IEEE Transactions on
Pattern Analysis and Machine Intelligence. 2015;37(12):2505-2517. doi:10.1109/tpami.2015.2408348
apa: Eynard, D., Kovnatsky, A., Bronstein, M. M., Glashoff, K., & Bronstein,
A. M. (2015). Multimodal manifold snalysis by simultaneous diagonalization of
Laplacians. IEEE Transactions on Pattern Analysis and Machine Intelligence.
IEEE. https://doi.org/10.1109/tpami.2015.2408348
chicago: Eynard, Davide, Artiom Kovnatsky, Michael M. Bronstein, Klaus Glashoff,
and Alex M. Bronstein. “Multimodal Manifold Snalysis by Simultaneous Diagonalization
of Laplacians.” IEEE Transactions on Pattern Analysis and Machine Intelligence.
IEEE, 2015. https://doi.org/10.1109/tpami.2015.2408348.
ieee: D. Eynard, A. Kovnatsky, M. M. Bronstein, K. Glashoff, and A. M. Bronstein,
“Multimodal manifold snalysis by simultaneous diagonalization of Laplacians,”
IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37,
no. 12. IEEE, pp. 2505–2517, 2015.
ista: Eynard D, Kovnatsky A, Bronstein MM, Glashoff K, Bronstein AM. 2015. Multimodal
manifold snalysis by simultaneous diagonalization of Laplacians. IEEE Transactions
on Pattern Analysis and Machine Intelligence. 37(12), 2505–2517.
mla: Eynard, Davide, et al. “Multimodal Manifold Snalysis by Simultaneous Diagonalization
of Laplacians.” IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 37, no. 12, IEEE, 2015, pp. 2505–17, doi:10.1109/tpami.2015.2408348.
short: D. Eynard, A. Kovnatsky, M.M. Bronstein, K. Glashoff, A.M. Bronstein, IEEE
Transactions on Pattern Analysis and Machine Intelligence 37 (2015) 2505–2517.
date_created: 2024-10-15T11:20:55Z
date_published: 2015-12-01T00:00:00Z
date_updated: 2024-12-12T14:08:46Z
day: '01'
doi: 10.1109/tpami.2015.2408348
extern: '1'
external_id:
pmid:
- '26539854'
fulldoi: https://doi.org/10.1109/tpami.2015.2408348
intvolume: ' 37'
issue: '12'
language:
- iso: eng
month: '12'
oa_version: None
page: 2505-2517
pmid: 1
publication: IEEE Transactions on Pattern Analysis and Machine Intelligence
publication_identifier:
eissn:
- 1939-3539
issn:
- 0162-8828
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multimodal manifold snalysis by simultaneous diagonalization of Laplacians
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 37
year: '2015'
...
---
_id: '18424'
abstract:
- lang: eng
text: We present a fast algorithm for global rigid symmetry detection with approximation
guarantees. The algorithm is guaranteed to find the best approximate symmetry
of a given shape, to within a user-specified threshold, with very high probability.
Our method uses a carefully designed sampling of the transformation space, where
each transformation is efficiently evaluated using a sublinear algorithm. We prove
that the density of the sampling depends on the total variation of the shape,
allowing us to derive formal bounds on the algorithm's complexity and approximation
quality. We further investigate different volumetric shape representations (in
the form of truncated distance transforms), and in such a way control the total
variation of the shape and hence the sampling density and the runtime of the algorithm.
A comprehensive set of experiments assesses the proposed method, including an
evaluation on the eight categories of the COSEG data set. This is the first large-scale
evaluation of any symmetry detection technique that we are aware of.
article_processing_charge: No
arxiv: 1
author:
- first_name: Simon
full_name: Korman, Simon
last_name: Korman
- first_name: Roee
full_name: Litman, Roee
last_name: Litman
- first_name: Shai
full_name: Avidan, Shai
last_name: Avidan
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
citation:
ama: 'Korman S, Litman R, Avidan S, Bronstein AM. Probably approximately symmetric:
Fast rigid symmetry detection with global guarantees. Computer Graphics Forum.
2015;34(1):2-13. doi:10.1111/cgf.12454'
apa: 'Korman, S., Litman, R., Avidan, S., & Bronstein, A. M. (2015). Probably
approximately symmetric: Fast rigid symmetry detection with global guarantees.
Computer Graphics Forum. Wiley. https://doi.org/10.1111/cgf.12454'
chicago: 'Korman, Simon, Roee Litman, Shai Avidan, and Alex M. Bronstein. “Probably
Approximately Symmetric: Fast Rigid Symmetry Detection with Global Guarantees.”
Computer Graphics Forum. Wiley, 2015. https://doi.org/10.1111/cgf.12454.'
ieee: 'S. Korman, R. Litman, S. Avidan, and A. M. Bronstein, “Probably approximately
symmetric: Fast rigid symmetry detection with global guarantees,” Computer
Graphics Forum, vol. 34, no. 1. Wiley, pp. 2–13, 2015.'
ista: 'Korman S, Litman R, Avidan S, Bronstein AM. 2015. Probably approximately
symmetric: Fast rigid symmetry detection with global guarantees. Computer Graphics
Forum. 34(1), 2–13.'
mla: 'Korman, Simon, et al. “Probably Approximately Symmetric: Fast Rigid Symmetry
Detection with Global Guarantees.” Computer Graphics Forum, vol. 34, no.
1, Wiley, 2015, pp. 2–13, doi:10.1111/cgf.12454.'
short: S. Korman, R. Litman, S. Avidan, A.M. Bronstein, Computer Graphics Forum
34 (2015) 2–13.
date_created: 2024-10-15T11:20:55Z
date_published: 2015-02-01T00:00:00Z
date_updated: 2024-12-19T10:12:48Z
day: '01'
doi: 10.1111/cgf.12454
extern: '1'
external_id:
arxiv:
- '1403.6637'
fulldoi: https://doi.org/10.1111/cgf.12454
intvolume: ' 34'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1403.6637
month: '02'
oa: 1
oa_version: Preprint
page: 2-13
publication: Computer Graphics Forum
publication_identifier:
eissn:
- 1467-8659
issn:
- 0167-7055
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Probably approximately symmetric: Fast rigid symmetry detection with global
guarantees'
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '18425'
abstract:
- lang: eng
text: The recent introduction of 3D shape analysis frameworks able to quantify the
deformation of a shape into another in terms of the variation of real functions
yields a new interpretation of the 3D shape similarity assessment and opens new
perspectives. Indeed, while the classical approaches to similarity mainly quantify
it as a numerical score, map-based methods also define (dense) shape correspondences.
After presenting in detail the theoretical foundations underlying these approaches,
we classify them by looking at their most salient features, including the kind
of structure and invariance properties they capture, as well as the distances
and the output modalities according to which the similarity between shapes is
assessed and returned. We also review the usage of these methods in a number of
3D shape application domains, ranging from matching and retrieval to annotation
and segmentation. Finally, the most promising directions for future research developments
are discussed.
article_processing_charge: No
author:
- first_name: S.
full_name: Biasotti, S.
last_name: Biasotti
- first_name: A.
full_name: Cerri, A.
last_name: Cerri
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: M.
full_name: Bronstein, M.
last_name: Bronstein
citation:
ama: Biasotti S, Cerri A, Bronstein AM, Bronstein M. Recent trends, applications,
and perspectives in 3D shape similarity assessment. Computer Graphics Forum.
2015;35(6):87-119. doi:10.1111/cgf.12734
apa: Biasotti, S., Cerri, A., Bronstein, A. M., & Bronstein, M. (2015). Recent
trends, applications, and perspectives in 3D shape similarity assessment. Computer
Graphics Forum. Wiley. https://doi.org/10.1111/cgf.12734
chicago: Biasotti, S., A. Cerri, Alex M. Bronstein, and M. Bronstein. “Recent Trends,
Applications, and Perspectives in 3D Shape Similarity Assessment.” Computer
Graphics Forum. Wiley, 2015. https://doi.org/10.1111/cgf.12734.
ieee: S. Biasotti, A. Cerri, A. M. Bronstein, and M. Bronstein, “Recent trends,
applications, and perspectives in 3D shape similarity assessment,” Computer
Graphics Forum, vol. 35, no. 6. Wiley, pp. 87–119, 2015.
ista: Biasotti S, Cerri A, Bronstein AM, Bronstein M. 2015. Recent trends, applications,
and perspectives in 3D shape similarity assessment. Computer Graphics Forum. 35(6),
87–119.
mla: Biasotti, S., et al. “Recent Trends, Applications, and Perspectives in 3D Shape
Similarity Assessment.” Computer Graphics Forum, vol. 35, no. 6, Wiley,
2015, pp. 87–119, doi:10.1111/cgf.12734.
short: S. Biasotti, A. Cerri, A.M. Bronstein, M. Bronstein, Computer Graphics Forum
35 (2015) 87–119.
date_created: 2024-10-15T11:20:55Z
date_published: 2015-09-01T00:00:00Z
date_updated: 2024-12-19T13:44:16Z
day: '01'
doi: 10.1111/cgf.12734
extern: '1'
fulldoi: https://doi.org/10.1111/cgf.12734
intvolume: ' 35'
issue: '6'
language:
- iso: eng
month: '09'
oa_version: None
page: 87-119
publication: Computer Graphics Forum
publication_identifier:
eissn:
- 1467-8659
issn:
- 0167-7055
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Recent trends, applications, and perspectives in 3D shape similarity assessment
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 35
year: '2015'
...
---
_id: '18436'
article_processing_charge: No
author:
- first_name: Harel
full_name: Haim, Harel
last_name: Haim
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: Emanuel
full_name: Marom, Emanuel
last_name: Marom
citation:
ama: Haim H, Bronstein AM, Marom E. Computational multi-focus imaging combining
sparse model with color dependent phase mask. Optics Express. 2015;23(19):24547-24556.
doi:10.1364/oe.23.024547
apa: Haim, H., Bronstein, A. M., & Marom, E. (2015). Computational multi-focus
imaging combining sparse model with color dependent phase mask. Optics Express.
Optica Publishing Group. https://doi.org/10.1364/oe.23.024547
chicago: Haim, Harel, Alex M. Bronstein, and Emanuel Marom. “Computational Multi-Focus
Imaging Combining Sparse Model with Color Dependent Phase Mask.” Optics Express.
Optica Publishing Group, 2015. https://doi.org/10.1364/oe.23.024547.
ieee: H. Haim, A. M. Bronstein, and E. Marom, “Computational multi-focus imaging
combining sparse model with color dependent phase mask,” Optics Express,
vol. 23, no. 19. Optica Publishing Group, pp. 24547–24556, 2015.
ista: Haim H, Bronstein AM, Marom E. 2015. Computational multi-focus imaging combining
sparse model with color dependent phase mask. Optics Express. 23(19), 24547–24556.
mla: Haim, Harel, et al. “Computational Multi-Focus Imaging Combining Sparse Model
with Color Dependent Phase Mask.” Optics Express, vol. 23, no. 19, Optica
Publishing Group, 2015, pp. 24547–56, doi:10.1364/oe.23.024547.
short: H. Haim, A.M. Bronstein, E. Marom, Optics Express 23 (2015) 24547–24556.
date_created: 2024-10-15T11:20:55Z
date_published: 2015-09-10T00:00:00Z
date_updated: 2024-12-19T10:48:50Z
day: '10'
doi: 10.1364/oe.23.024547
extern: '1'
fulldoi: https://doi.org/10.1364/oe.23.024547
intvolume: ' 23'
issue: '19'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1364/OE.23.024547
month: '09'
oa: 1
oa_version: Published Version
page: 24547 - 24556
publication: Optics Express
publication_identifier:
eissn:
- 1094-4087
publication_status: published
publisher: Optica Publishing Group
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computational multi-focus imaging combining sparse model with color dependent
phase mask
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2015'
...
---
_id: '18439'
abstract:
- lang: eng
text: Intel’s newly-announced low-cost and high precision RealSense 3D (RGBD) camera
is becoming ubiquitous in laptops and mobile devices starting this year, opening
the door for new applications in the mobile health arena. In this paper, we demonstrate
how the Intel RealSense 3D camera can be used for low-cost gaze tracking and passive
pulse rate estimation. We develop a novel 3D gaze and fixation tracker based on
the eye surface geometry as well as an illumination invariant pulse rate estimation
method using near-infrared images captured with RealSense. We achieve a mean error
of 1cm at 20 − 30cm for the gaze tracker and 2.26bpm (beats per minute) for pulse
estimation, which is adequate in many medical applications, demonstrating the
great potential of novel consumer-grade RGBD technology in mobile health.
article_processing_charge: No
author:
- first_name: Qiang
full_name: Qiu, Qiang
last_name: Qiu
- first_name: Zhuoqing
full_name: Chang, Zhuoqing
last_name: Chang
- first_name: Mark
full_name: Draelos, Mark
last_name: Draelos
- first_name: Jie
full_name: Chen, Jie
last_name: Chen
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: Guillermo
full_name: Sapiro, Guillermo
last_name: Sapiro
citation:
ama: 'Qiu Q, Chang Z, Draelos M, Chen J, Bronstein AM, Sapiro G. Low-cost gaze and
pulse analysis using realsense. In: Proceedings of the 5th EAI International
Conference on Wireless Mobile Communication and Healthcare. ICST; 2015. doi:10.4108/eai.14-10-2015.2261657'
apa: 'Qiu, Q., Chang, Z., Draelos, M., Chen, J., Bronstein, A. M., & Sapiro,
G. (2015). Low-cost gaze and pulse analysis using realsense. In Proceedings
of the 5th EAI International Conference on Wireless Mobile Communication and Healthcare.
London, United Kingdom: ICST. https://doi.org/10.4108/eai.14-10-2015.2261657'
chicago: Qiu, Qiang, Zhuoqing Chang, Mark Draelos, Jie Chen, Alex M. Bronstein,
and Guillermo Sapiro. “Low-Cost Gaze and Pulse Analysis Using Realsense.” In Proceedings
of the 5th EAI International Conference on Wireless Mobile Communication and Healthcare.
ICST, 2015. https://doi.org/10.4108/eai.14-10-2015.2261657.
ieee: Q. Qiu, Z. Chang, M. Draelos, J. Chen, A. M. Bronstein, and G. Sapiro, “Low-cost
gaze and pulse analysis using realsense,” in Proceedings of the 5th EAI International
Conference on Wireless Mobile Communication and Healthcare, London, United
Kingdom, 2015.
ista: Qiu Q, Chang Z, Draelos M, Chen J, Bronstein AM, Sapiro G. 2015. Low-cost
gaze and pulse analysis using realsense. Proceedings of the 5th EAI International
Conference on Wireless Mobile Communication and Healthcare. 5th EAI International
Conference on Wireless Mobile Communication and Healthcare - Transforming Healthcare
through Innovations in Mobile and Wireless Technologies.
mla: Qiu, Qiang, et al. “Low-Cost Gaze and Pulse Analysis Using Realsense.” Proceedings
of the 5th EAI International Conference on Wireless Mobile Communication and Healthcare,
ICST, 2015, doi:10.4108/eai.14-10-2015.2261657.
short: Q. Qiu, Z. Chang, M. Draelos, J. Chen, A.M. Bronstein, G. Sapiro, in:, Proceedings
of the 5th EAI International Conference on Wireless Mobile Communication and Healthcare,
ICST, 2015.
conference:
end_date: 2015-10-16
location: London, United Kingdom
name: 5th EAI International Conference on Wireless Mobile Communication and Healthcare
- Transforming Healthcare through Innovations in Mobile and Wireless Technologies
start_date: 2015-10-14
date_created: 2024-10-15T11:20:55Z
date_published: 2015-12-22T00:00:00Z
date_updated: 2024-12-19T13:36:57Z
day: '22'
doi: 10.4108/eai.14-10-2015.2261657
extern: '1'
fulldoi: https://doi.org/10.4108/eai.14-10-2015.2261657
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4108/eai.14-10-2015.2261657
month: '12'
oa: 1
oa_version: Published Version
publication: Proceedings of the 5th EAI International Conference on Wireless Mobile
Communication and Healthcare
publication_identifier:
isbn:
- '9781631900884'
publication_status: published
publisher: ICST
quality_controlled: '1'
scopus_import: '1'
status: public
title: Low-cost gaze and pulse analysis using realsense
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1508'
abstract:
- lang: eng
text: We consider generalized Wigner ensembles and general β-ensembles with analytic
potentials for any β ≥ 1. The recent universality results in particular assert
that the local averages of consecutive eigenvalue gaps in the bulk of the spectrum
are universal in the sense that they coincide with those of the corresponding
Gaussian β-ensembles. In this article, we show that local averaging is not necessary
for this result, i.e. we prove that the single gap distributions in the bulk are
universal. In fact, with an additional step, our result can be extended to any
C4(ℝ) potential.
article_processing_charge: No
arxiv: 1
author:
- first_name: László
full_name: Erdös, László
id: 4DBD5372-F248-11E8-B48F-1D18A9856A87
last_name: Erdös
orcid: 0000-0001-5366-9603
- first_name: Horng
full_name: Yau, Horng
last_name: Yau
citation:
ama: Erdös L, Yau H. Gap universality of generalized Wigner and β ensembles. Journal
of the European Mathematical Society. 2015;17(8):1927-2036. doi:10.4171/JEMS/548
apa: Erdös, L., & Yau, H. (2015). Gap universality of generalized Wigner and
β ensembles. Journal of the European Mathematical Society. EMS Press. https://doi.org/10.4171/JEMS/548
chicago: Erdös, László, and Horng Yau. “Gap Universality of Generalized Wigner and
β Ensembles.” Journal of the European Mathematical Society. EMS Press,
2015. https://doi.org/10.4171/JEMS/548.
ieee: L. Erdös and H. Yau, “Gap universality of generalized Wigner and β ensembles,”
Journal of the European Mathematical Society, vol. 17, no. 8. EMS Press,
pp. 1927–2036, 2015.
ista: Erdös L, Yau H. 2015. Gap universality of generalized Wigner and β ensembles.
Journal of the European Mathematical Society. 17(8), 1927–2036.
mla: Erdös, László, and Horng Yau. “Gap Universality of Generalized Wigner and β
Ensembles.” Journal of the European Mathematical Society, vol. 17, no.
8, EMS Press, 2015, pp. 1927–2036, doi:10.4171/JEMS/548.
short: L. Erdös, H. Yau, Journal of the European Mathematical Society 17 (2015)
1927–2036.
das_tickbox: '1'
date_created: 2018-12-11T11:52:26Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2026-07-06T11:55:30Z
day: '01'
department:
- _id: LaEr
doi: 10.4171/JEMS/548
external_id:
arxiv:
- '1211.3786'
isi:
- '000360822900003'
fulldoi: https://doi.org/10.4171/JEMS/548
intvolume: ' 17'
isi: 1
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1211.3786
month: '08'
oa: 1
oa_version: Preprint
page: 1927 - 2036
publication: Journal of the European Mathematical Society
publication_status: published
publisher: EMS Press
publist_id: '5669'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Gap universality of generalized Wigner and β ensembles
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 17
year: '2015'
...
---
_id: '1832'
abstract:
- lang: eng
text: 'Linearizability of concurrent data structures is usually proved by monolithic
simulation arguments relying on the identification of the so-called linearization
points. Regrettably, such proofs, whether manual or automatic, are often complicated
and scale poorly to advanced non-blocking concurrency patterns, such as helping
and optimistic updates. In response, we propose a more modular way of checking
linearizability of concurrent queue algorithms that does not involve identifying
linearization points. We reduce the task of proving linearizability with respect
to the queue specification to establishing four basic properties, each of which
can be proved independently by simpler arguments. As a demonstration of our approach,
we verify the Herlihy and Wing queue, an algorithm that is challenging to verify
by a simulation proof. '
article_number: '20'
article_processing_charge: No
article_type: original
author:
- first_name: Soham
full_name: Chakraborty, Soham
last_name: Chakraborty
- 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: Ali
full_name: Sezgin, Ali
last_name: Sezgin
- first_name: Viktor
full_name: Vafeiadis, Viktor
last_name: Vafeiadis
citation:
ama: Chakraborty S, Henzinger TA, Sezgin A, Vafeiadis V. Aspect-oriented linearizability
proofs. Logical Methods in Computer Science. 2015;11(1). doi:10.2168/LMCS-11(1:20)2015
apa: Chakraborty, S., Henzinger, T. A., Sezgin, A., & Vafeiadis, V. (2015).
Aspect-oriented linearizability proofs. Logical Methods in Computer Science.
International Federation for Computational Logic. https://doi.org/10.2168/LMCS-11(1:20)2015
chicago: Chakraborty, Soham, Thomas A Henzinger, Ali Sezgin, and Viktor Vafeiadis.
“Aspect-Oriented Linearizability Proofs.” Logical Methods in Computer Science.
International Federation for Computational Logic, 2015. https://doi.org/10.2168/LMCS-11(1:20)2015.
ieee: S. Chakraborty, T. A. Henzinger, A. Sezgin, and V. Vafeiadis, “Aspect-oriented
linearizability proofs,” Logical Methods in Computer Science, vol. 11,
no. 1. International Federation for Computational Logic, 2015.
ista: Chakraborty S, Henzinger TA, Sezgin A, Vafeiadis V. 2015. Aspect-oriented
linearizability proofs. Logical Methods in Computer Science. 11(1), 20.
mla: Chakraborty, Soham, et al. “Aspect-Oriented Linearizability Proofs.” Logical
Methods in Computer Science, vol. 11, no. 1, 20, International Federation
for Computational Logic, 2015, doi:10.2168/LMCS-11(1:20)2015.
short: S. Chakraborty, T.A. Henzinger, A. Sezgin, V. Vafeiadis, Logical Methods
in Computer Science 11 (2015).
corr_author: '1'
das_tickbox: '1'
date_created: 2018-12-11T11:54:15Z
date_published: 2015-04-01T00:00:00Z
date_updated: 2026-07-06T13:24:05Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.2168/LMCS-11(1:20)2015
ec_funded: 1
external_id:
isi:
- '000353193000019'
file:
- access_level: open_access
checksum: 7370e164d0a731f442424a92669efc34
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:27Z
date_updated: 2020-07-14T12:45:17Z
file_id: '4881'
file_name: IST-2015-390-v1+1_1502.07639.pdf
file_size: 380203
relation: main_file
file_date_updated: 2020-07-14T12:45:17Z
fulldoi: https://doi.org/10.2168/LMCS-11(1:20)2015
has_accepted_license: '1'
intvolume: ' 11'
isi: 1
issue: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '04'
oa: 1
oa_version: Published Version
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: Logical Methods in Computer Science
publication_status: published
publisher: International Federation for Computational Logic
publist_id: '5271'
pubrep_id: '390'
quality_controlled: '1'
related_material:
record:
- id: '2328'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Aspect-oriented linearizability proofs
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2015'
...
---
OA_place: repository
OA_type: green
_id: '1610'
abstract:
- lang: eng
text: The edit distance between two words w1, w2 is the minimal number of word operations
(letter insertions, deletions, and substitutions) necessary to transform w1 to
w2. The edit distance generalizes to languages L1,L2, where the edit distance
is the minimal number k such that for every word from L1 there exists a word in
L2 with edit distance at most k. We study the edit distance computation problem
between pushdown automata and their subclasses. The problem of computing edit
distance to pushdown automata is undecidable, and in practice, the interesting
question is to compute the edit distance from a pushdown automaton (the implementation,
a standard model for programs with recursion) to a regular language (the specification).
In this work, we present a complete picture of decidability and complexity for
deciding whether, for a given threshold k, the edit distance from a pushdown automaton
to a finite automaton is at most k.
acknowledgement: "This research was funded in part by the European Research Council
(ERC) under\r\ngrant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF)
projects\r\nS11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), FWF Grant No P23499-\r\nN23,
FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph\r\nGames), and
MSR faculty fellows award."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- 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: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: 'Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit distance for pushdown
automata. In: 42nd International Colloquium on Automata, Languages, and Programming.
Vol 9135. Springer Nature; 2015:121-133. doi:10.1007/978-3-662-47666-6_10'
apa: 'Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015).
Edit distance for pushdown automata. In 42nd International Colloquium on Automata,
Languages, and Programming (Vol. 9135, pp. 121–133). Kyoto, Japan: Springer
Nature. https://doi.org/10.1007/978-3-662-47666-6_10'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan
Otop. “Edit Distance for Pushdown Automata.” In 42nd International Colloquium
on Automata, Languages, and Programming, 9135:121–33. Springer Nature, 2015.
https://doi.org/10.1007/978-3-662-47666-6_10.
ieee: K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, “Edit distance
for pushdown automata,” in 42nd International Colloquium on Automata, Languages,
and Programming, Kyoto, Japan, 2015, vol. 9135, no. Part II, pp. 121–133.
ista: 'Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for
pushdown automata. 42nd International Colloquium on Automata, Languages, and Programming.
ICALP: Automata, Languages and Programming, LNCS, vol. 9135, 121–133.'
mla: Chatterjee, Krishnendu, et al. “Edit Distance for Pushdown Automata.” 42nd
International Colloquium on Automata, Languages, and Programming, vol. 9135,
no. Part II, Springer Nature, 2015, pp. 121–33, doi:10.1007/978-3-662-47666-6_10.
short: K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, in:, 42nd International
Colloquium on Automata, Languages, and Programming, Springer Nature, 2015, pp.
121–133.
conference:
end_date: 2015-07-10
location: Kyoto, Japan
name: 'ICALP: Automata, Languages and Programming'
start_date: 2015-07-06
date_created: 2018-12-11T11:53:01Z
date_published: 2015-07-01T00:00:00Z
date_updated: 2026-07-06T13:27:53Z
day: '01'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-662-47666-6_10
ec_funded: 1
external_id:
arxiv:
- '1504.08259'
isi:
- '000364317900010'
fulldoi: https://doi.org/10.1007/978-3-662-47666-6_10
intvolume: ' 9135'
isi: 1
issue: Part II
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1504.08259
month: '07'
oa: 1
oa_version: Preprint
page: 121 - 133
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication: 42nd International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- 978-3-662-47665-9
publication_status: published
publisher: Springer Nature
publist_id: '5556'
pubrep_id: '321'
quality_controlled: '1'
related_material:
record:
- id: '5438'
relation: earlier_version
status: public
- id: '465'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Edit distance for pushdown automata
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9135
year: '2015'
...
---
OA_place: repository
OA_type: green
_id: '1657'
abstract:
- lang: eng
text: 'We consider Markov decision processes (MDPs) with multiple limit-average
(or mean-payoff) objectives. There exist 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. We consider
optimization with respect to both objectives at once, thus unifying the existing
semantics. Precisely, the goal is to optimize the expectation while ensuring the
satisfaction constraint. Our problem captures the notion of optimization with
respect to strategies that are risk-averse (i.e., Ensure certain probabilistic
guarantee). Our main results are as follows: First, we present algorithms for
the decision problems, which are always polynomial in the size of the MDP. We
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. Second, we present a complete characterization of the strategy
complexity (in terms of memory bounds and randomization) required to solve our
problem. '
acknowledgement: "A Technical Report of this paper is available at DOI: 10.15479/AT:IST-2015-318-v1-1\r\n"
alternative_title:
- LICS
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: Zuzana
full_name: Komárková, Zuzana
last_name: Komárková
- 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, Komárková Z, Kretinsky J. Unifying two views on multiple mean-payoff
objectives in Markov decision processes. 2015:244-256. doi:10.1109/LICS.2015.32
apa: 'Chatterjee, K., Komárková, Z., & Kretinsky, J. (2015). Unifying two views
on multiple mean-payoff objectives in Markov decision processes. Presented at
the LICS: Logic in Computer Science, Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.32'
chicago: Chatterjee, Krishnendu, Zuzana Komárková, and Jan Kretinsky. “Unifying
Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes.” LICS.
IEEE, 2015. https://doi.org/10.1109/LICS.2015.32.
ieee: K. Chatterjee, Z. Komárková, and J. Kretinsky, “Unifying two views on multiple
mean-payoff objectives in Markov decision processes.” IEEE, pp. 244–256, 2015.
ista: Chatterjee K, Komárková Z, Kretinsky J. 2015. Unifying two views on multiple
mean-payoff objectives in Markov decision processes. , 244–256.
mla: Chatterjee, Krishnendu, et al. Unifying Two Views on Multiple Mean-Payoff
Objectives in Markov Decision Processes. IEEE, 2015, pp. 244–56, doi:10.1109/LICS.2015.32.
short: K. Chatterjee, Z. Komárková, J. Kretinsky, (2015) 244–256.
conference:
end_date: 2015-07-10
location: Kyoto, Japan
name: 'LICS: Logic in Computer Science'
start_date: 2015-07-06
date_created: 2018-12-11T11:53:18Z
date_published: 2015-07-01T00:00:00Z
date_updated: 2026-07-06T13:26:26Z
day: '01'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1109/LICS.2015.32
ec_funded: 1
external_id:
isi:
- '000380427100024'
fulldoi: https://doi.org/10.1109/LICS.2015.32
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.15479/AT:IST-2015-318-v1-1
month: '07'
oa: 1
oa_version: Preprint
page: 244 - 256
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: IEEE
publist_id: '5493'
quality_controlled: '1'
related_material:
record:
- id: '5429'
relation: earlier_version
status: public
- id: '5435'
relation: earlier_version
status: public
- id: '466'
relation: later_version
status: public
scopus_import: '1'
series_title: LICS
status: public
title: Unifying two views on multiple mean-payoff objectives in Markov decision processes
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
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: 2026-07-06T13:26:26Z
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
fulldoi: https://doi.org/10.15479/AT:IST-2015-318-v2-1
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: '1657'
relation: later_version
status: public
- id: '466'
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'
...