7 Search Results for "Palamidessi, Catuscia"

Document
DOI: 10.4230/LIPIcs.WABI.2024.5
Memoization on Shared Subtrees Accelerates Computations on Genealogical Forests

Authors: Lukas Hübner and Alexandros Stamatakis

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
The field of population genetics attempts to advance our understanding of evolutionary processes. It has applications, for example, in medical research, wildlife conservation, and - in conjunction with recent advances in ancient DNA sequencing technology - studying human migration patterns over the past few thousand years. The basic toolbox of population genetics includes genealogical trees, which describe the shared evolutionary history among individuals of the same species. They are calculated on the basis of genetic variations. However, in recombining organisms, a single tree is insufficient to describe the evolutionary history of the whole genome. Instead, a collection of correlated trees can be used, where each describes the evolutionary history of a consecutive region of the genome. The current corresponding state of-the-art data structure, tree sequences, compresses these genealogical trees via edit operations when moving from one tree to the next along the genome instead of storing the full, often redundant, description for each tree. We propose a new data structure, genealogical forests, which compresses the set of genealogical trees into a DAG. In this DAG identical subtrees that are shared across the input trees are encoded only once, thereby allowing for straight-forward memoization of intermediate results. Additionally, we provide a C++ implementation of our proposed data structure, called gfkit, which is 2.1 to 11.2 (median 4.0) times faster than the state-of-the-art tool on empirical and simulated datasets at computing important population genetics statistics such as the Allele Frequency Spectrum, Patterson’s f, the Fixation Index, Tajima’s D, pairwise Lowest Common Ancestors, and others. On Lowest Common Ancestor queries with more than two samples as input, gfkit scales asymptotically better than the state-of-the-art, and is thus up to 990 times faster. In conclusion, our proposed data structure compresses genealogical trees by storing shared subtrees only once, thereby enabling straight-forward memoization of intermediate results, yielding a substantial runtime reduction and a potentially more intuitive data representation over the state-of-the-art. Our improvements will boost the development of novel analyses and models in the field of population genetics and increases scalability to ever-growing genomic datasets.
Cite as

Lukas Hübner and Alexandros Stamatakis. Memoization on Shared Subtrees Accelerates Computations on Genealogical Forests. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hubner_et_al:LIPIcs.WABI.2024.5,
  author =	{H\"{u}bner, Lukas and Stamatakis, Alexandros},
  title =	{{Memoization on Shared Subtrees Accelerates Computations on Genealogical Forests}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.5},
  URN =		{urn:nbn:de:0030-drops-206499},
  doi =		{10.4230/LIPIcs.WABI.2024.5},
  annote =	{Keywords: bioinformatics, population genetics, algorithms}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.CONCUR.2021.1
CONCUR Test-Of-Time Award 2021 (Invited Paper)

Authors: Nathalie Bertrand, Luca de Alfaro, Rob van Glabbeek, Catuscia Palamidessi, and Nobuko Yoshida

Published in: LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021)

Abstract
This short article announces the recipients of the CONCUR Test-of-Time Award 2021.
Cite as

Nathalie Bertrand, Luca de Alfaro, Rob van Glabbeek, Catuscia Palamidessi, and Nobuko Yoshida. CONCUR Test-Of-Time Award 2021 (Invited Paper). In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 1:1-1:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bertrand_et_al:LIPIcs.CONCUR.2021.1,
  author =	{Bertrand, Nathalie and de Alfaro, Luca and van Glabbeek, Rob and Palamidessi, Catuscia and Yoshida, Nobuko},
  title =	{{CONCUR Test-Of-Time Award 2021}},
  booktitle =	{32nd International Conference on Concurrency Theory (CONCUR 2021)},
  pages =	{1:1--1:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-203-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{203},
  editor =	{Haddad, Serge and Varacca, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.1},
  URN =		{urn:nbn:de:0030-drops-143786},
  doi =		{10.4230/LIPIcs.CONCUR.2021.1},
  annote =	{Keywords: Concurrency, CONCUR Test-of-Time Award}
}
Document
DOI: 10.4230/OASIcs.Gabbrielli.11
Derivation of Constraints from Machine Learning Models and Applications to Security and Privacy

Authors: Moreno Falaschi, Catuscia Palamidessi, and Marco Romanelli

Published in: OASIcs, Volume 86, Recent Developments in the Design and Implementation of Programming Languages (2020)

Abstract
This paper shows how we can combine the power of machine learning with the flexibility of constraints. More specifically, we show how machine learning models can be represented by first-order logic theories, and how to derive these theories. The advantage of this representation is that it can be augmented with additional formulae, representing constraints of some kind on the data domain. For instance, new knowledge, or potential attackers, or fairness desiderata. We consider various kinds of learning algorithms (neural networks, k-nearest-neighbours, decision trees, support vector machines) and for each of them we show how to infer the FOL formulae. Then we focus on one particular application domain, namely the field of security and privacy. The idea is to represent the potentialities and goals of the attacker as a set of constraints, then use a constraint solver (more precisely, a solver modulo theories) to verify the satisfiability. If a solution exists, then it means that an attack is possible, otherwise, the system is safe. We show various examples from different areas of security and privacy; specifically, we consider a side-channel attack on a password checker, a malware attack on smart health systems, and a model-inversion attack on a neural network.
Cite as

Moreno Falaschi, Catuscia Palamidessi, and Marco Romanelli. Derivation of Constraints from Machine Learning Models and Applications to Security and Privacy. In Recent Developments in the Design and Implementation of Programming Languages. Open Access Series in Informatics (OASIcs), Volume 86, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{falaschi_et_al:OASIcs.Gabbrielli.11,
  author =	{Falaschi, Moreno and Palamidessi, Catuscia and Romanelli, Marco},
  title =	{{Derivation of Constraints from Machine Learning Models and Applications to Security and Privacy}},
  booktitle =	{Recent Developments in the Design and Implementation of Programming Languages},
  pages =	{11:1--11:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-171-9},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{86},
  editor =	{de Boer, Frank S. and Mauro, Jacopo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Gabbrielli.11},
  URN =		{urn:nbn:de:0030-drops-132338},
  doi =		{10.4230/OASIcs.Gabbrielli.11},
  annote =	{Keywords: Constraints, machine learning, privacy, security}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.CONCUR.2020.4
Modern Applications of Game-Theoretic Principles (Invited Paper)

Authors: Catuscia Palamidessi and Marco Romanelli

Published in: LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)

Abstract
Game theory is the study of the strategic behavior of rational decision makers who are aware that their decisions affect one another. Its simple but universal principles have found applications in the most diverse disciplines, including economics, social sciences, evolutionary biology, as well as logic, system science and computer science. Despite its long-standing tradition and its many advances, game theory is still a young and developing science. In this paper, we describe some recent and exciting applications in the fields of machine learning and privacy.
Cite as

Catuscia Palamidessi and Marco Romanelli. Modern Applications of Game-Theoretic Principles (Invited Paper). In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 4:1-4:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{palamidessi_et_al:LIPIcs.CONCUR.2020.4,
  author =	{Palamidessi, Catuscia and Romanelli, Marco},
  title =	{{Modern Applications of Game-Theoretic Principles}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{4:1--4:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Konnov, Igor and Kov\'{a}cs, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.4},
  URN =		{urn:nbn:de:0030-drops-128167},
  doi =		{10.4230/LIPIcs.CONCUR.2020.4},
  annote =	{Keywords: Game theory, machine learning, privacy, security}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2016.35
Up-To Techniques for Generalized Bisimulation Metrics

Authors: Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Valeria Vignudelli

Published in: LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016)

Abstract
Bisimulation metrics allow us to compute distances between the behaviors of probabilistic systems. In this paper we present enhancements of the proof method based on bisimulation metrics, by extending the theory of up-to techniques to (pre)metrics on discrete probabilistic concurrent processes. Up-to techniques have proved to be a powerful proof method for showing that two systems are bisimilar, since they make it possible to build (and thereby check) smaller relations in bisimulation proofs. We define soundness conditions for up-to techniques on metrics, and study compatibility properties that allow us to safely compose up-to techniques with each other. As an example, we derive the soundness of the up-to-bisimilarity-metric-and-context technique. The study is carried out for a generalized version of the bisimulation metrics, in which the Kantorovich lifting is parametrized with respect to a distance function. The standard bisimulation metrics, as well as metrics aimed at capturing multiplicative properties such as differential privacy, are specific instances of this general definition.
Cite as

Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Valeria Vignudelli. Up-To Techniques for Generalized Bisimulation Metrics. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chatzikokolakis_et_al:LIPIcs.CONCUR.2016.35,
  author =	{Chatzikokolakis, Konstantinos and Palamidessi, Catuscia and Vignudelli, Valeria},
  title =	{{Up-To Techniques for Generalized Bisimulation Metrics}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{35:1--35:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Desharnais, Jos\'{e}e and Jagadeesan, Radha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.35},
  URN =		{urn:nbn:de:0030-drops-61793},
  doi =		{10.4230/LIPIcs.CONCUR.2016.35},
  annote =	{Keywords: bisimulation, metrics, up-to techniques, Kantorovich, differential privacy}
}
Document
DOI: 10.4230/DagRep.2.11.135
Quantitative Security Analysis (Dagstuhl Seminar 12481)

Authors: Boris Köpf, Paquale Malacaria, and Catuscia Palamidessi

Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)

Abstract
The high amount of trust put into today's software systems calls for a rigorous analysis of their security. Unfortunately, security is often in conflict with requirements on the functionality or the performance of a system, making perfect security an impossible or overly expensive goal. Under such constraints, the relevant question is not whether a system is secure, but rather how much security it provides. Quantitative notions of security can express degrees of protection and thus enable reasoning about the trade-off between security and conflicting requirements. Corresponding quantitative security analyses bear the potential of becoming an important tool for the rigorous development of practical systems, and a formal foundation for the management of security risks.
Cite as

Boris Köpf, Paquale Malacaria, and Catuscia Palamidessi. Quantitative Security Analysis (Dagstuhl Seminar 12481). In Dagstuhl Reports, Volume 2, Issue 11, pp. 135-154, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{kopf_et_al:DagRep.2.11.135,
  author =	{K\"{o}pf, Boris and Malacaria, Paquale and Palamidessi, Catuscia},
  title =	{{Quantitative Security Analysis (Dagstuhl Seminar 12481)}},
  pages =	{135--154},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{11},
  editor =	{K\"{o}pf, Boris and Malacaria, Paquale and Palamidessi, Catuscia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.11.135},
  URN =		{urn:nbn:de:0030-drops-39824},
  doi =		{10.4230/DagRep.2.11.135},
  annote =	{Keywords: Security, Privacy,Information theory, Programming languages, Formal methods}
}
Document
DOI: 10.4230/DagSemProc.05081.8
Probabilistic Anonymity

Authors: Catuscia Palamidessi and Mohit Bhargava

Published in: Dagstuhl Seminar Proceedings, Volume 5081, Foundations of Global Computing (2006)

Abstract
The concept of anonymity comes into play in a wide range of situations, varying from voting and anonymous donations to postings on bulletin boards and sending mails. A formal definition of this concept has been given in literature in terms of nondeterminism. In this paper, we investigate a notion of anonymity based on probability theory, and we we discuss the relation with the nondeterministic one. We then formulate this definition in terms of observables for processes in the probabilistic $pi$-calculus, and propose a method to verify automatically the anonymity property. We illustrate the method by using the example of the dining cryptographers.
Cite as

Catuscia Palamidessi and Mohit Bhargava. Probabilistic Anonymity. In Foundations of Global Computing. Dagstuhl Seminar Proceedings, Volume 5081, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{palamidessi_et_al:DagSemProc.05081.8,
  author =	{Palamidessi, Catuscia and Bhargava, Mohit},
  title =	{{Probabilistic Anonymity}},
  booktitle =	{Foundations of Global Computing},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5081},
  editor =	{Jos\'{e} Luiz Fiadeiro and Ugo Montanari and Martin Wirsing},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05081.8},
  URN =		{urn:nbn:de:0030-drops-2992},
  doi =		{10.4230/DagSemProc.05081.8},
  annote =	{Keywords: Anonymity, probability theory, process calculi}
}
  • Refine by Author
  • 6 Palamidessi, Catuscia
  • 2 Romanelli, Marco
  • 1 Bertrand, Nathalie
  • 1 Bhargava, Mohit
  • 1 Chatzikokolakis, Konstantinos
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 machine learning
  • 2 privacy
  • 2 security
  • 1 Anonymity
  • 1 CONCUR Test-of-Time Award
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2020
  • 1 2006
  • 1 2013
  • 1 2016
  • 1 2021
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact