Search Results

Documents authored by Severini, Simone

Document
DOI: 10.4230/LIPIcs.ICALP.2017.76
Relaxations of Graph Isomorphism

Authors: Laura Mancinska, David E. Roberson, Robert Samal, Simone Severini, and Antonios Varvitsiotis

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We introduce a nonlocal game that captures and extends the notion of graph isomorphism. This game can be won in the classical case if and only if the two input graphs are isomorphic. Thus, by considering quantum strategies we are able to define the notion of quantum isomorphism. We also consider the case of more general non-signalling strategies, and show that such a strategy exists if and only if the graphs are fractionally isomorphic. We prove several necessary conditions for quantum isomorphism, including cospectrality, and provide a construction for producing pairs of non-isomorphic graphs that are quantum isomorphic. We then show that both classical and quantum isomorphism can be reformulated as feasibility programs over the completely positive and completely positive semidefinite cones respectively. This leads us to considering relaxations of (quantum) isomorphism arrived at by relaxing the cone to either the doubly nonnegative (DNN) or positive semidefinite (PSD) cones. We show that DNN-isomorphism is equivalent to the previous defined notion of graph equivalence, a polynomial-time decidable relation that is related to coherent algebras. We also show that PSD-isomorphism implies several types of cospectrality, and that it is equivalent to cospectrality for connected 1-walk-regular graphs. Finally, we show that all of the above mentioned relations form a strict hierarchy of weaker and weaker relations, with non-singalling/fractional isomorphism being the weakest. The techniques used are an interesting mix of algebra, combinatorics, and quantum information.
Cite as

Laura Mancinska, David E. Roberson, Robert Samal, Simone Severini, and Antonios Varvitsiotis. Relaxations of Graph Isomorphism. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 76:1-76:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mancinska_et_al:LIPIcs.ICALP.2017.76,
  author =	{Mancinska, Laura and Roberson, David E. and Samal, Robert and Severini, Simone and Varvitsiotis, Antonios},
  title =	{{Relaxations of Graph Isomorphism}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{76:1--76:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.76},
  URN =		{urn:nbn:de:0030-drops-74697},
  doi =		{10.4230/LIPIcs.ICALP.2017.76},
  annote =	{Keywords: graph isomorphism, quantum information, semidefinite programming}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.48
Bounds on Entanglement Assisted Source-channel Coding Via the Lovász Theta Number and Its Variants

Authors: Toby Cubitt, Laura Mancinska, David Roberson, Simone Severini, Dan Stahlke, and Andreas Winter

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

Abstract
We study zero-error entanglement assisted source-channel coding (communication in the presence of side information). Adapting a technique of Beigi, we show that such coding requires existence of a set of vectors satisfying orthogonality conditions related to suitably defined graphs G and H. Such vectors exist if and only if theta(G) <= theta(H) where theta represents the Lovász number. We also obtain similar inequalities for the related Schrijver theta^- and Szegedy theta^+ numbers. These inequalities reproduce several known bounds and also lead to new results. We provide a lower bound on the entanglement assisted cost rate. We show that the entanglement assisted independence number is bounded by the Schrijver number: alpha^*(G) <= theta^-(G). Therefore, we are able to disprove the conjecture that the one-shot entanglement-assisted zero-error capacity is equal to the integer part of the Lovász number. Beigi introduced a quantity beta as an upper bound on alpha^* and posed the question of whether beta(G) = \lfloor theta(G) \rfloor. We answer this in the affirmative and show that a related quantity is equal to \lceil theta(G) \rceil. We show that a quantity chi_{vect}(G) recently introduced in the context of Tsirelson's conjecture is equal to \lceil theta^+(G) \rceil.
Cite as

Toby Cubitt, Laura Mancinska, David Roberson, Simone Severini, Dan Stahlke, and Andreas Winter. Bounds on Entanglement Assisted Source-channel Coding Via the Lovász Theta Number and Its Variants. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 48-51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{cubitt_et_al:LIPIcs.TQC.2014.48,
  author =	{Cubitt, Toby and Mancinska, Laura and Roberson, David and Severini, Simone and Stahlke, Dan and Winter, Andreas},
  title =	{{Bounds on Entanglement Assisted Source-channel Coding Via the Lov\'{a}sz Theta Number and Its Variants}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{48--51},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.48},
  URN =		{urn:nbn:de:0030-drops-48054},
  doi =		{10.4230/LIPIcs.TQC.2014.48},
  annote =	{Keywords: source-channel coding, zero-error capacity, Lov\'{a}sz theta}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.67
Graph-theoretical Bounds on the Entangled Value of Non-local Games

Authors: André Chailloux, Laura Mancinska, Giannicola Scarpa, and Simone Severini

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

Abstract
We introduce a novel technique to give bounds to the entangled value of non-local games. The technique is based on a class of graphs used by Cabello, Severini and Winter in 2010. The upper bound uses the famous Lovàsz theta number and is efficiently computable; the lower one is based on the quantum independence number, which is a quantity used in the study of entanglement-assisted channel capacities and graph homomorphism games.
Cite as

André Chailloux, Laura Mancinska, Giannicola Scarpa, and Simone Severini. Graph-theoretical Bounds on the Entangled Value of Non-local Games. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 67-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chailloux_et_al:LIPIcs.TQC.2014.67,
  author =	{Chailloux, Andr\'{e} and Mancinska, Laura and Scarpa, Giannicola and Severini, Simone},
  title =	{{Graph-theoretical Bounds on the Entangled Value of Non-local Games}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{67--75},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.67},
  URN =		{urn:nbn:de:0030-drops-48074},
  doi =		{10.4230/LIPIcs.TQC.2014.67},
  annote =	{Keywords: Graph theory, non-locality, entangled games}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.TQC.2013
LIPIcs, Volume 22, TQC'13, Complete Volume

Authors: Simone Severini and Fernando Brandao

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)

Abstract
LIPIcs, Volume 22, TQC'13, Complete Volume
Cite as

8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{severini_et_al:LIPIcs.TQC.2013,
  title =	{{LIPIcs, Volume 22, TQC'13, Complete Volume}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013},
  URN =		{urn:nbn:de:0030-drops-43480},
  doi =		{10.4230/LIPIcs.TQC.2013},
  annote =	{Keywords: Data Encryption, Coding and Information Theory, Theory of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.TQC.2013.i
Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Simone Severini and Fernando Brandao

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)

Abstract
Frontmatter, Table of Contents, Preface, Conference Organization
Cite as

8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. i-x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{severini_et_al:LIPIcs.TQC.2013.i,
  author =	{Severini, Simone and Brandao, Fernando},
  title =	{{Frontmatter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{i--x},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.i},
  URN =		{urn:nbn:de:0030-drops-43081},
  doi =		{10.4230/LIPIcs.TQC.2013.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Conference Organization}
}
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 Imprint Privacy Contact