4 Search Results for "Gorrieri, Roberto"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.24
Unitary Complexity and the Uhlmann Transformation Problem

Authors: John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann’s theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
Cite as

John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen. Unitary Complexity and the Uhlmann Transformation Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bostanci_et_al:LIPIcs.ITCS.2026.24,
  author =	{Bostanci, John and Efron, Yuval and Metger, Tony and Poremba, Alexander and Qian, Luowen and Yuen, Henry},
  title =	{{Unitary Complexity and the Uhlmann Transformation Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.24},
  URN =		{urn:nbn:de:0030-drops-253111},
  doi =		{10.4230/LIPIcs.ITCS.2026.24},
  annote =	{Keywords: Uhlmann’s theorem, unitary complexity theory}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.5
Information-Theoretic Random-Index PIR

Authors: Sebastian Kolby, Lawrence Roy, Jure Sternad, and Sophia Yakoubov

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
A Private Information Retrieval (PIR) protocol allows a client to learn the ith row of a database held by one or more servers, without revealing i to the servers. A Random-Index PIR (RPIR) protocol, introduced by Gentry et al. (TCC 2021), is a PIR protocol where, instead of being chosen by the client, i is random. This has applications in e.g. anonymous committee selection. Both PIR and RPIR protocols are interesting only if the communication complexity is smaller than the database size; otherwise, the trivial solution where the servers send the entire database suffices. Unlike PIR, where the client must send at least one message (to encode information about i), RPIR can be executed in a single round of server-to-client communication. In this paper, we study such one-round, information-theoretic RPIR protocols. The only known construction in this setting is SimpleMSRPIR (Gentry et al.), which requires the servers to communicate approximately N/2 bits, N being the database size. We show an Ω(√N) lower bound on communication complexity for one-round two-server information-theoretic RPIR, and a sublinear upper bound. Finally, we show how to use a sublinear amount of database-independent correlated randomness among multiple servers to get near-optimal online communication complexity (the size of one row plus the size of one index description per server).
Cite as

Sebastian Kolby, Lawrence Roy, Jure Sternad, and Sophia Yakoubov. Information-Theoretic Random-Index PIR. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kolby_et_al:LIPIcs.ITC.2025.5,
  author =	{Kolby, Sebastian and Roy, Lawrence and Sternad, Jure and Yakoubov, Sophia},
  title =	{{Information-Theoretic Random-Index PIR}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.5},
  URN =		{urn:nbn:de:0030-drops-243559},
  doi =		{10.4230/LIPIcs.ITC.2025.5},
  annote =	{Keywords: Private information retrieval, Multi-server, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.28
A Decidable Equivalence for a Turing-Complete, Distributed Model of Computation

Authors: Arnaldo Cesco and Roberto Gorrieri

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Place/Transition Petri nets with inhibitor arcs (PTI nets for short), which are a well-known Turing-complete, distributed model of computation, are equipped with a decidable, behavioral equivalence, called pti-place bisimilarity, that conservatively extends place bisimilarity defined over Place/Transition nets (without inhibitor arcs). We prove that pti-place bisimilarity is sensible, as it respects the causal semantics of PTI nets.
Cite as

Arnaldo Cesco and Roberto Gorrieri. A Decidable Equivalence for a Turing-Complete, Distributed Model of Computation. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cesco_et_al:LIPIcs.MFCS.2021.28,
  author =	{Cesco, Arnaldo and Gorrieri, Roberto},
  title =	{{A Decidable Equivalence for a Turing-Complete, Distributed Model of Computation}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.28},
  URN =		{urn:nbn:de:0030-drops-144686},
  doi =		{10.4230/LIPIcs.MFCS.2021.28},
  annote =	{Keywords: Petri nets, Inhibitor arc, Behavioral equivalence, Bisimulation, Decidability}
}
Document
DOI: 10.4230/DagSemRep.294
Security through Analysis and Verification (Dagstuhl Seminar 00501)

Authors: Pierpaolo Degano, Roberto Gorrieri, Chris Hankin, Flemming Nielson, and Hanne Riis Nielson

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Pierpaolo Degano, Roberto Gorrieri, Chris Hankin, Flemming Nielson, and Hanne Riis Nielson. Security through Analysis and Verification (Dagstuhl Seminar 00501). Dagstuhl Seminar Report 294, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)

Copy BibTex To Clipboard

@TechReport{degano_et_al:DagSemRep.294,
  author =	{Degano, Pierpaolo and Gorrieri, Roberto and Hankin, Chris and Nielson, Flemming and Riis Nielson, Hanne},
  title =	{{Security through Analysis and Verification (Dagstuhl Seminar 00501)}},
  pages =	{1--15},
  ISSN =	{1619-0203},
  year =	{2001},
  type = 	{Dagstuhl Seminar Report},
  number =	{294},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.294},
  URN =		{urn:nbn:de:0030-drops-151781},
  doi =		{10.4230/DagSemRep.294},
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2021
  • 1 2001

  • Refine by Author
  • 2 Gorrieri, Roberto
  • 1 Bostanci, John
  • 1 Cesco, Arnaldo
  • 1 Degano, Pierpaolo
  • 1 Efron, Yuval
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs
  • 1 DagSemRep

  • Refine by Classification
  • 1 Security and privacy → Information-theoretic techniques
  • 1 Theory of computation → Distributed computing models
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 1 Behavioral equivalence
  • 1 Bisimulation
  • 1 Decidability
  • 1 Inhibitor arc
  • 1 Lower bounds
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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