--- _id: '2911' abstract: - lang: eng text: |- We have selected problems that may not yet be well known, but have the potential to push the research in interesting directions. In particular, we state problems that do not require specific knowledge outside the standard circle of ideas in discrete geometry. Despite the relatively simple statements, these problems are related to current research and their solutions are likely to require new ideas and approaches. We have chosen problems from different fields to make this short paper attractive to a wide range of specialists. author: - first_name: Herbert full_name: Herbert Edelsbrunner id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Alexander full_name: Ivanov, Alexander last_name: Ivanov - first_name: Roman full_name: Karasev, Roman last_name: Karasev citation: ama: Edelsbrunner H, Ivanov A, Karasev R. Open problems in discrete and computational geometry. Automatic Control and Computer Sciences. 2012;in print. apa: Edelsbrunner, H., Ivanov, A., & Karasev, R. (2012). Open problems in discrete and computational geometry. Automatic Control and Computer Sciences. Springer. chicago: Edelsbrunner, Herbert, Alexander Ivanov, and Roman Karasev. “Open Problems in Discrete and Computational Geometry.” Automatic Control and Computer Sciences. Springer, 2012. ieee: H. Edelsbrunner, A. Ivanov, and R. Karasev, “Open problems in discrete and computational geometry,” Automatic Control and Computer Sciences, vol. in print. Springer, 2012. ista: Edelsbrunner H, Ivanov A, Karasev R. 2012. Open problems in discrete and computational geometry. Automatic Control and Computer Sciences. in print. mla: Edelsbrunner, Herbert, et al. “Open Problems in Discrete and Computational Geometry.” Automatic Control and Computer Sciences, vol. in print, Springer, 2012. short: H. Edelsbrunner, A. Ivanov, R. Karasev, Automatic Control and Computer Sciences in print (2012). date_created: 2018-12-11T12:00:18Z date_published: 2012-01-01T00:00:00Z date_updated: 2021-01-12T07:00:38Z day: '01' extern: 1 month: '01' publication: Automatic Control and Computer Sciences publication_status: published publisher: Springer publist_id: '3832' quality_controlled: 0 status: public title: Open problems in discrete and computational geometry type: journal_article volume: in print year: '2012' ... --- _id: '2930' abstract: - lang: eng text: "In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k = 1 and k = 2 respectively.\r\n\r\nIn particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron.\r\n" acknowledgement: "We would like to thank Andrei Krokhin for encourag- ing our cooperation, for helpful discussions, and for his critical reading of the manuscript.\r\n" alternative_title: - LNCS author: - first_name: Anna full_name: Huber, Anna last_name: Huber - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Huber A, Kolmogorov V. Towards minimizing k-submodular functions. In: Vol 7422. Springer; 2012:451-462. doi:10.1007/978-3-642-32147-4_40' apa: 'Huber, A., & Kolmogorov, V. (2012). Towards minimizing k-submodular functions (Vol. 7422, pp. 451–462). Presented at the ISCO: International Symposium on Combinatorial Optimization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-642-32147-4_40' chicago: Huber, Anna, and Vladimir Kolmogorov. “Towards Minimizing K-Submodular Functions,” 7422:451–62. Springer, 2012. https://doi.org/10.1007/978-3-642-32147-4_40. ieee: 'A. Huber and V. Kolmogorov, “Towards minimizing k-submodular functions,” presented at the ISCO: International Symposium on Combinatorial Optimization, Athens, Greece, 2012, vol. 7422, pp. 451–462.' ista: 'Huber A, Kolmogorov V. 2012. Towards minimizing k-submodular functions. ISCO: International Symposium on Combinatorial Optimization, LNCS, vol. 7422, 451–462.' mla: Huber, Anna, and Vladimir Kolmogorov. Towards Minimizing K-Submodular Functions. Vol. 7422, Springer, 2012, pp. 451–62, doi:10.1007/978-3-642-32147-4_40. short: A. Huber, V. Kolmogorov, in:, Springer, 2012, pp. 451–462. conference: end_date: 2012-04-21 location: Athens, Greece name: 'ISCO: International Symposium on Combinatorial Optimization' start_date: 2012-04-19 date_created: 2018-12-11T12:00:24Z date_published: 2012-04-01T00:00:00Z date_updated: 2021-01-12T07:00:46Z day: '01' department: - _id: VlKo doi: 10.1007/978-3-642-32147-4_40 intvolume: ' 7422' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1309.5469 month: '04' oa: 1 oa_version: Preprint page: 451 - 462 publication_status: published publisher: Springer publist_id: '3806' quality_controlled: '1' scopus_import: 1 status: public title: Towards minimizing k-submodular functions type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 7422 year: '2012' ... --- _id: '2928' abstract: - lang: eng text: ' This paper addresses the problem of approximate MAP-MRF inference in general graphical models. Following [36], we consider a family of linear programming relaxations of the problem where each relaxation is specified by a set of nested pairs of factors for which the marginalization constraint needs to be enforced. We develop a generalization of the TRW-S algorithm [9] for this problem, where we use a decomposition into junction chains, monotonic w.r.t. some ordering on the nodes. This generalizes the monotonic chains in [9] in a natural way. We also show how to deal with nested factors in an efficient way. Experiments show an improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on a number of computer vision and natural language processing problems. ' article_processing_charge: No author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Thomas full_name: Schoenemann, Thomas last_name: Schoenemann citation: ama: Kolmogorov V, Schoenemann T. Generalized sequential tree-reweighted message passing. arXiv. 2012. apa: Kolmogorov, V., & Schoenemann, T. (2012). Generalized sequential tree-reweighted message passing. arXiv. ArXiv. chicago: Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted Message Passing.” ArXiv. ArXiv, 2012. ieee: V. Kolmogorov and T. Schoenemann, “Generalized sequential tree-reweighted message passing,” arXiv. ArXiv, 2012. ista: Kolmogorov V, Schoenemann T. 2012. Generalized sequential tree-reweighted message passing. arXiv, . mla: Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted Message Passing.” ArXiv, ArXiv, 2012. short: V. Kolmogorov, T. Schoenemann, ArXiv (2012). date_created: 2018-12-11T12:00:23Z date_published: 2012-05-29T00:00:00Z date_updated: 2021-01-12T07:00:45Z day: '29' department: - _id: VlKo external_id: arxiv: - '1205.6352' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1205.6352 month: '05' oa: 1 oa_version: Preprint page: '16' publication: arXiv publication_status: published publisher: ArXiv publist_id: '3809' status: public title: Generalized sequential tree-reweighted message passing type: preprint user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '2929' author: - first_name: Vladimir full_name: Vladimir Kolmogorov id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Kolmogorov V. The Power of Linear Programming for Valued CSPs: A Constructive Characterization. Unknown; 2012.' apa: 'Kolmogorov, V. (2012). The power of linear programming for valued CSPs: a constructive characterization. Unknown.' chicago: 'Kolmogorov, Vladimir. The Power of Linear Programming for Valued CSPs: A Constructive Characterization. Unknown, 2012.' ieee: 'V. Kolmogorov, The power of linear programming for valued CSPs: a constructive characterization. Unknown, 2012.' ista: 'Kolmogorov V. 2012. The power of linear programming for valued CSPs: a constructive characterization, Unknown,p.' mla: 'Kolmogorov, Vladimir. The Power of Linear Programming for Valued CSPs: A Constructive Characterization. Unknown, 2012.' short: 'V. Kolmogorov, The Power of Linear Programming for Valued CSPs: A Constructive Characterization, Unknown, 2012.' date_created: 2018-12-11T12:00:24Z date_published: 2012-01-01T00:00:00Z date_updated: 2019-04-26T07:22:21Z day: '01' extern: 1 main_file_link: - open_access: '1' url: http://arxiv.org/abs/1207.7213 month: '01' oa: 1 publication_status: published publisher: Unknown publist_id: '3807' quality_controlled: 0 status: public title: 'The power of linear programming for valued CSPs: a constructive characterization' type: report year: '2012' ... --- _id: '2937' abstract: - lang: eng text: Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from this task by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is hard as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage, ZKCrypt provides assurance that the output implementation securely realizes the abstract proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system. acknowledgement: This work was partially funded by National Funds through the FCT - Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) within project ENI-AC/2224/2009, by ENIAC Joint Undertaking under grant agreement number 120224, European Projects FP7-256980 NESSoS and FP7-229599 AMAROUT, Spanish National project TIN2009-14599 DESAFIOS 10, and Madrid Regional project S2009TIC-1465 PROMETIDOS. author: - first_name: José full_name: Almeida, José last_name: Almeida - first_name: Manuel full_name: Barbosa, Manuel last_name: Barbosa - first_name: Endre full_name: Bangerter, Endre last_name: Bangerter - first_name: Gilles full_name: Barthe, Gilles last_name: Barthe - first_name: Stephan full_name: Krenn, Stephan id: 329FCCF0-F248-11E8-B48F-1D18A9856A87 last_name: Krenn orcid: 0000-0003-2835-9093 - first_name: Santiago full_name: Béguelin, Santiago last_name: Béguelin citation: ama: 'Almeida J, Barbosa M, Bangerter E, Barthe G, Krenn S, Béguelin S. Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security. ACM; 2012:488-500. doi:10.1145/2382196.2382249' apa: 'Almeida, J., Barbosa, M., Bangerter, E., Barthe, G., Krenn, S., & Béguelin, S. (2012). Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols. In Proceedings of the 2012 ACM conference on Computer and communications security (pp. 488–500). Raleigh, NC, USA: ACM. https://doi.org/10.1145/2382196.2382249' chicago: 'Almeida, José, Manuel Barbosa, Endre Bangerter, Gilles Barthe, Stephan Krenn, and Santiago Béguelin. “Full Proof Cryptography: Verifiable Compilation of Efficient Zero-Knowledge Protocols.” In Proceedings of the 2012 ACM Conference on Computer and Communications Security, 488–500. ACM, 2012. https://doi.org/10.1145/2382196.2382249.' ieee: 'J. Almeida, M. Barbosa, E. Bangerter, G. Barthe, S. Krenn, and S. Béguelin, “Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols,” in Proceedings of the 2012 ACM conference on Computer and communications security, Raleigh, NC, USA, 2012, pp. 488–500.' ista: 'Almeida J, Barbosa M, Bangerter E, Barthe G, Krenn S, Béguelin S. 2012. Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols. Proceedings of the 2012 ACM conference on Computer and communications security. CCS: Computer and Communications Security, 488–500.' mla: 'Almeida, José, et al. “Full Proof Cryptography: Verifiable Compilation of Efficient Zero-Knowledge Protocols.” Proceedings of the 2012 ACM Conference on Computer and Communications Security, ACM, 2012, pp. 488–500, doi:10.1145/2382196.2382249.' short: J. Almeida, M. Barbosa, E. Bangerter, G. Barthe, S. Krenn, S. Béguelin, in:, Proceedings of the 2012 ACM Conference on Computer and Communications Security, ACM, 2012, pp. 488–500. conference: end_date: 2012-10-18 location: Raleigh, NC, USA name: 'CCS: Computer and Communications Security' start_date: 2012-10-16 date_created: 2018-12-11T12:00:26Z date_published: 2012-10-01T00:00:00Z date_updated: 2021-01-12T07:39:53Z day: '01' department: - _id: KrPi doi: 10.1145/2382196.2382249 language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2012/258 month: '10' oa: 1 oa_version: Submitted Version page: 488 - 500 publication: Proceedings of the 2012 ACM conference on Computer and communications security publication_status: published publisher: ACM publist_id: '3798' quality_controlled: '1' scopus_import: 1 status: public title: 'Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols' type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '2936' abstract: - lang: eng text: The notion of delays arises naturally in many computational models, such as, in the design of circuits, control systems, and dataflow languages. In this work, we introduce automata with delay blocks (ADBs), extending finite state automata with variable time delay blocks, for deferring individual transition output symbols, in a discrete-time setting. We show that the ADB languages strictly subsume the regular languages, and are incomparable in expressive power to the context-free languages. We show that ADBs are closed under union, concatenation and Kleene star, and under intersection with regular languages, but not closed under complementation and intersection with other ADB languages. We show that the emptiness and the membership problems are decidable in polynomial time for ADBs, whereas the universality problem is undecidable. Finally we consider the linear-time model checking problem, i.e., whether the language of an ADB is contained in a regular language, and show that the model checking problem is PSPACE-complete. Copyright 2012 ACM. acknowledgement: 'This work has been financially supported in part by the European Commission FP7-ICT Cognitive Systems, Interaction, and Robotics under the contract # 270180 (NOPTILUS); by Fundacao para Ciencia e Tecnologia under project PTDC/EEA-CRO/104901/2008 (Modeling and control of Networked vehicle systems in persistent autonomous operations); by Austrian Science Fund (FWF) Grant No P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification; FWF NFN Grant No S11407-N23 (RiSE); ERC Start grant (279307: Graph Games); Microsoft faculty fellows award; ERC Advanced grant QUAREM; and FWF Grant No S11403-N23 (RiSE).' 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: Vinayak full_name: Prabhu, Vinayak last_name: Prabhu citation: ama: 'Chatterjee K, Henzinger TA, Prabhu V. Finite automata with time delay blocks. In: Roceedings of the Tenth ACM International Conference on Embedded Software. ACM; 2012:43-52. doi:10.1145/2380356.2380370' apa: 'Chatterjee, K., Henzinger, T. A., & Prabhu, V. (2012). Finite automata with time delay blocks. In roceedings of the tenth ACM international conference on Embedded software (pp. 43–52). Tampere, Finland: ACM. https://doi.org/10.1145/2380356.2380370' chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Vinayak Prabhu. “Finite Automata with Time Delay Blocks.” In Roceedings of the Tenth ACM International Conference on Embedded Software, 43–52. ACM, 2012. https://doi.org/10.1145/2380356.2380370. ieee: K. Chatterjee, T. A. Henzinger, and V. Prabhu, “Finite automata with time delay blocks,” in roceedings of the tenth ACM international conference on Embedded software, Tampere, Finland, 2012, pp. 43–52. ista: 'Chatterjee K, Henzinger TA, Prabhu V. 2012. Finite automata with time delay blocks. roceedings of the tenth ACM international conference on Embedded software. EMSOFT: Embedded Software , 43–52.' mla: Chatterjee, Krishnendu, et al. “Finite Automata with Time Delay Blocks.” Roceedings of the Tenth ACM International Conference on Embedded Software, ACM, 2012, pp. 43–52, doi:10.1145/2380356.2380370. short: K. Chatterjee, T.A. Henzinger, V. Prabhu, in:, Roceedings of the Tenth ACM International Conference on Embedded Software, ACM, 2012, pp. 43–52. conference: end_date: 2012-10-12 location: Tampere, Finland name: 'EMSOFT: Embedded Software ' start_date: 2012-10-07 date_created: 2018-12-11T12:00:26Z date_published: 2012-10-01T00:00:00Z date_updated: 2021-01-12T07:39:53Z day: '01' department: - _id: KrCh - _id: ToHe doi: 10.1145/2380356.2380370 ec_funded: 1 language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1207.7019 month: '10' oa: 1 oa_version: Preprint page: 43 - 52 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25EE3708-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '267989' name: Quantitative Reactive Modeling - _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: roceedings of the tenth ACM international conference on Embedded software publication_status: published publisher: ACM publist_id: '3799' quality_controlled: '1' scopus_import: 1 status: public title: Finite automata with time delay blocks type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '2938' abstract: - lang: eng text: 'Social insects have a very high potential to become invasive pest species. Here, we explore how their social lifestyle and their interaction with parasites may contribute to this invasive success. Similar to solitary species, parasite release followed by the evolution of increased competitive ability can promote establishment of introduced social insect hosts in their introduced range. Genetic bottlenecks during introduction of low numbers of founder individuals decrease the genetic diversity at three levels: the population, the colony and the individual, with the colony level being specific to social insects. Reduced genetic diversity can affect both the individual immune system and the collective colony-level disease defences (social immunity). Still, the dual immune system is likely to make social insects more robust to parasite attack. Changes in social structure from small, family-based, territorially aggressive societies in native populations towards huge networks of cooperating nests (unicoloniality) occur in some invasive social insects, for example, most invasive ants and some termites. Unicoloniality is likely to affect disease dynamics in multiple ways. The free exchange of individuals within the population leads to an increased genetic heterogeneity among individuals of a single nest, thereby decreasing disease transmission. However, the multitude of reproductively active queens per colony buffers the effect of individual diseased queens and their offspring, which may result in a higher level of vertical disease transmission in unicolonial societies. Lastly, unicoloniality provides a competitive advantage over native species, allowing them to quickly become the dominant species in the habitat, which in turn selects for parasite adaptation to this common host genotype and thus eventually a high parasite pressure. Overall, invasions by insect societies are characterized by general features applying to all introduced species, as well as idiosyncrasies that emerge from their social lifestyle. It is important to study these effects in concert to be able to develop efficient management and biocontrol strategies. © 2012 British Ecological Society.' acknowledgement: We thank Mark Brown, Christopher Pull, Meghan L. Vyleta, Miriam Stock, Barbara Casillas-Perez and three anonymous reviewers for valuable comments on the manuscript and Eva Sixt for ant drawings. Funding was obtained from the German Science Foundation (DFG, by an Individual Research Grant to S.C.) and the European Research Council (ERC, by an ERC-Starting Grant to SC and an Individual Marie Curie EIF fellowship to L.desU.). The authors declare no conflict of interests. author: - first_name: Line V full_name: Ugelvig, Line V id: 3DC97C8E-F248-11E8-B48F-1D18A9856A87 last_name: Ugelvig orcid: 0000-0003-1832-8883 - first_name: Sylvia full_name: Cremer, Sylvia id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87 last_name: Cremer orcid: 0000-0002-2193-3868 citation: ama: Ugelvig LV, Cremer S. Effects of social immunity and unicoloniality on host parasite interactions in invasive insect societies. Functional Ecology. 2012;26(6):1300-1312. doi:10.1111/1365-2435.12013 apa: Ugelvig, L. V., & Cremer, S. (2012). Effects of social immunity and unicoloniality on host parasite interactions in invasive insect societies. Functional Ecology. Wiley-Blackwell. https://doi.org/10.1111/1365-2435.12013 chicago: Ugelvig, Line V, and Sylvia Cremer. “Effects of Social Immunity and Unicoloniality on Host Parasite Interactions in Invasive Insect Societies.” Functional Ecology. Wiley-Blackwell, 2012. https://doi.org/10.1111/1365-2435.12013. ieee: L. V. Ugelvig and S. Cremer, “Effects of social immunity and unicoloniality on host parasite interactions in invasive insect societies,” Functional Ecology, vol. 26, no. 6. Wiley-Blackwell, pp. 1300–1312, 2012. ista: Ugelvig LV, Cremer S. 2012. Effects of social immunity and unicoloniality on host parasite interactions in invasive insect societies. Functional Ecology. 26(6), 1300–1312. mla: Ugelvig, Line V., and Sylvia Cremer. “Effects of Social Immunity and Unicoloniality on Host Parasite Interactions in Invasive Insect Societies.” Functional Ecology, vol. 26, no. 6, Wiley-Blackwell, 2012, pp. 1300–12, doi:10.1111/1365-2435.12013. short: L.V. Ugelvig, S. Cremer, Functional Ecology 26 (2012) 1300–1312. date_created: 2018-12-11T12:00:27Z date_published: 2012-01-01T00:00:00Z date_updated: 2021-01-12T07:39:54Z day: '01' department: - _id: SyCr doi: 10.1111/1365-2435.12013 intvolume: ' 26' issue: '6' language: - iso: eng month: '01' oa_version: None page: 1300 - 1312 publication: Functional Ecology publication_status: published publisher: Wiley-Blackwell publist_id: '3797' quality_controlled: '1' scopus_import: 1 status: public title: Effects of social immunity and unicoloniality on host parasite interactions in invasive insect societies type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 26 year: '2012' ... --- _id: '2931' abstract: - lang: eng text: "In this paper, we present a new approach for establishing correspondences between sparse image features related by an unknown nonrigid mapping and corrupted by clutter and occlusion, such as points extracted from images of different instances of the same object category. We formulate this matching task as an energy minimization problem by defining an elaborate objective function of the appearance and the spatial arrangement of the features. Optimization of this energy is an instance of graph matching, which is in general an NP-hard problem. We describe a novel graph matching optimization technique, which we refer to as dual decomposition (DD), and demonstrate on a variety of examples that this method outperforms existing graph matching algorithms. In the majority of our examples, DD is able to find the global minimum within a minute. The ability to globally optimize the objective allows us to accurately learn the parameters of our matching model from training examples. We show on several matching tasks that our learned model yields results superior to those of state-of-the-art methods.\r\n" acknowledgement: This research was funded in part by Microsoft Research. author: - first_name: Lorenzo full_name: Torresani, Lorenzo last_name: Torresani - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Carsten full_name: Rother, Carsten last_name: Rother citation: ama: Torresani L, Kolmogorov V, Rother C. A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2012;35(2):259-271. doi:10.1109/TPAMI.2012.105 apa: Torresani, L., Kolmogorov, V., & Rother, C. (2012). A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. https://doi.org/10.1109/TPAMI.2012.105 chicago: Torresani, Lorenzo, Vladimir Kolmogorov, and Carsten Rother. “A Dual Decomposition Approach to Feature Correspondence.” IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE, 2012. https://doi.org/10.1109/TPAMI.2012.105. ieee: L. Torresani, V. Kolmogorov, and C. Rother, “A dual decomposition approach to feature correspondence,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 2. IEEE, pp. 259–271, 2012. ista: Torresani L, Kolmogorov V, Rother C. 2012. A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. 35(2), 259–271. mla: Torresani, Lorenzo, et al. “A Dual Decomposition Approach to Feature Correspondence.” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 2, IEEE, 2012, pp. 259–71, doi:10.1109/TPAMI.2012.105. short: L. Torresani, V. Kolmogorov, C. Rother, IEEE Transactions on Pattern Analysis and Machine Intelligence 35 (2012) 259–271. date_created: 2018-12-11T12:00:24Z date_published: 2012-05-08T00:00:00Z date_updated: 2021-01-12T07:00:46Z day: '08' department: - _id: VlKo doi: 10.1109/TPAMI.2012.105 intvolume: ' 35' issue: '2' language: - iso: eng month: '05' oa_version: None page: 259 - 271 project: - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: IEEE Transactions on Pattern Analysis and Machine Intelligence publication_status: published publisher: IEEE publist_id: '3805' quality_controlled: '1' scopus_import: 1 status: public title: A dual decomposition approach to feature correspondence type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 35 year: '2012' ... --- _id: '2942' abstract: - lang: eng text: Interface theories provide a formal framework for component-based development of software and hardware which supports the incremental design of systems and the independent implementability of components. These capabilities are ensured through mathematical properties of the parallel composition operator and the refinement relation for components. More recently, a conjunction operation was added to interface theories in order to provide support for handling multiple viewpoints, requirements engineering, and component reuse. Unfortunately, the conjunction operator does not allow independent implementability in general. In this paper, we study conditions that need to be imposed on interface models in order to enforce independent implementability with respect to conjunction. We focus on multiple viewpoint specifications and propose a new compatibility criterion between two interfaces, which we call orthogonality. We show that orthogonal interfaces can be refined separately, while preserving both orthogonality and composability with other interfaces. We illustrate the independent implementability of different viewpoints with a FIFO buffer example. acknowledgement: ERC Advanced Grant QUAREM (Quantitative Reactive Modeling), FWF National Research Network RISE (Rigorous Systems Engineering) alternative_title: - LNCS author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Dejan full_name: Nickovic, Dejan id: 41BCEE5C-F248-11E8-B48F-1D18A9856A87 last_name: Nickovic citation: ama: 'Henzinger TA, Nickovic D. Independent implementability of viewpoints. In: Conference Proceedings Monterey Workshop 2012. Vol 7539. Springer; 2012:380-395. doi:10.1007/978-3-642-34059-8_20' apa: 'Henzinger, T. A., & Nickovic, D. (2012). Independent implementability of viewpoints. In Conference proceedings Monterey Workshop 2012 (Vol. 7539, pp. 380–395). Oxford, UK: Springer. https://doi.org/10.1007/978-3-642-34059-8_20' chicago: Henzinger, Thomas A, and Dejan Nickovic. “Independent Implementability of Viewpoints.” In Conference Proceedings Monterey Workshop 2012, 7539:380–95. Springer, 2012. https://doi.org/10.1007/978-3-642-34059-8_20. ieee: T. A. Henzinger and D. Nickovic, “Independent implementability of viewpoints,” in Conference proceedings Monterey Workshop 2012, Oxford, UK, 2012, vol. 7539, pp. 380–395. ista: Henzinger TA, Nickovic D. 2012. Independent implementability of viewpoints. Conference proceedings Monterey Workshop 2012. Monterey Workshop 2012, LNCS, vol. 7539, 380–395. mla: Henzinger, Thomas A., and Dejan Nickovic. “Independent Implementability of Viewpoints.” Conference Proceedings Monterey Workshop 2012, vol. 7539, Springer, 2012, pp. 380–95, doi:10.1007/978-3-642-34059-8_20. short: T.A. Henzinger, D. Nickovic, in:, Conference Proceedings Monterey Workshop 2012, Springer, 2012, pp. 380–395. conference: end_date: 2012-03-21 location: Oxford, UK name: Monterey Workshop 2012 start_date: 2012-03-19 date_created: 2018-12-11T12:00:28Z date_published: 2012-09-16T00:00:00Z date_updated: 2021-01-12T07:39:56Z day: '16' department: - _id: ToHe doi: 10.1007/978-3-642-34059-8_20 ec_funded: 1 intvolume: ' 7539' language: - iso: eng month: '09' oa_version: None page: 380 - 395 project: - _id: 25EE3708-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '267989' name: Quantitative Reactive Modeling - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering publication: ' Conference proceedings Monterey Workshop 2012' publication_status: published publisher: Springer publist_id: '3791' quality_controlled: '1' scopus_import: 1 status: public title: Independent implementability of viewpoints type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 7539 year: '2012' ... --- _id: '2943' abstract: - lang: eng text: We examine whether the Escherichia coli chromosome is folded into a self-adherent nucleoprotein complex, or alternately is a confined but otherwise unconstrained self-avoiding polymer. We address this through in vivo visualization, using an inducible GFP fusion to the nucleoid-associated protein Fis to non-specifically decorate the entire chromosome. For a range of different growth conditions, the chromosome is a compact structure that does not fill the volume of the cell, and which moves from the new pole to the cell centre. During rapid growth, chromosome segregation occurs well before cell division, with daughter chromosomes coupled by a thin inter-daughter filament before complete segregation, whereas during slow growth chromosomes stay adjacent until cell division occurs. Image correlation analysis indicates that sub-nucleoid structure is stable on a 1min timescale, comparable to the timescale for redistribution time measured for GFP-Fis after photobleaching. Optical deconvolution and writhe calculation analysis indicate that the nucleoid has a large-scale coiled organization rather than being an amorphous mass. Our observations are consistent with the chromosome having a self-adherent filament organization. acknowledgement: We thank Professor Philippe Cluzel and Mr Lance Min for providing advice and materials. Jeannette Chau provided technical support. Work at NU was supported by NSF Grants DMR-0715099, MCB-1022117, DMR-1206868, DMR-0520513 and DMR-1121262 (NU-MRSEC), by NIH-NCI Grant U54CA143869-01 (NU-PS-OC) and by the Chicago Biomedical Consortium with support from the Searle Funds at the Chicago Community Trust. Work at UCLA was supported by NIH Grant GM038509. author: - first_name: Nastaran full_name: Hadizadeh Yazdi, Nastaran last_name: Hadizadeh Yazdi - first_name: Calin C full_name: Guet, Calin C id: 47F8433E-F248-11E8-B48F-1D18A9856A87 last_name: Guet orcid: 0000-0001-6220-2052 - first_name: Reid full_name: Johnson, Reid last_name: Johnson - first_name: John full_name: Marko, John last_name: Marko citation: ama: Hadizadeh Yazdi N, Guet CC, Johnson R, Marko J. Variation of the folding and dynamics of the Escherichia coli chromosome with growth conditions. Molecular Microbiology. 2012;86(6):1318-1333. doi:10.1111/mmi.12071 apa: Hadizadeh Yazdi, N., Guet, C. C., Johnson, R., & Marko, J. (2012). Variation of the folding and dynamics of the Escherichia coli chromosome with growth conditions. Molecular Microbiology. Wiley-Blackwell. https://doi.org/10.1111/mmi.12071 chicago: Hadizadeh Yazdi, Nastaran, Calin C Guet, Reid Johnson, and John Marko. “Variation of the Folding and Dynamics of the Escherichia Coli Chromosome with Growth Conditions.” Molecular Microbiology. Wiley-Blackwell, 2012. https://doi.org/10.1111/mmi.12071. ieee: N. Hadizadeh Yazdi, C. C. Guet, R. Johnson, and J. Marko, “Variation of the folding and dynamics of the Escherichia coli chromosome with growth conditions,” Molecular Microbiology, vol. 86, no. 6. Wiley-Blackwell, pp. 1318–1333, 2012. ista: Hadizadeh Yazdi N, Guet CC, Johnson R, Marko J. 2012. Variation of the folding and dynamics of the Escherichia coli chromosome with growth conditions. Molecular Microbiology. 86(6), 1318–1333. mla: Hadizadeh Yazdi, Nastaran, et al. “Variation of the Folding and Dynamics of the Escherichia Coli Chromosome with Growth Conditions.” Molecular Microbiology, vol. 86, no. 6, Wiley-Blackwell, 2012, pp. 1318–33, doi:10.1111/mmi.12071. short: N. Hadizadeh Yazdi, C.C. Guet, R. Johnson, J. Marko, Molecular Microbiology 86 (2012) 1318–1333. date_created: 2018-12-11T12:00:28Z date_published: 2012-11-09T00:00:00Z date_updated: 2021-01-12T07:39:56Z day: '09' department: - _id: CaGu doi: 10.1111/mmi.12071 intvolume: ' 86' issue: '6' language: - iso: eng main_file_link: - open_access: '1' url: http://europepmc.org/articles/pmc3524407 month: '11' oa: 1 oa_version: Submitted Version page: 1318 - 1333 publication: Molecular Microbiology publication_status: published publisher: Wiley-Blackwell publist_id: '3790' quality_controlled: '1' scopus_import: 1 status: public title: Variation of the folding and dynamics of the Escherichia coli chromosome with growth conditions type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 86 year: '2012' ...