3 Search Results for "Freedman, Michael"

Document
DOI: 10.4230/LIPIcs.ITCS.2020.17
On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H

Authors: Jin-Yi Cai and Artem Govorov

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Graph homomorphism has been an important research topic since its introduction [László Lovász, 1967]. Stated in the language of binary relational structures in that paper [László Lovász, 1967], Lovász proved a fundamental theorem that the graph homomorphism function G ↦ hom(G, H) for 0-1 valued H (as the adjacency matrix of a graph) determines the isomorphism type of H. In the past 50 years various extensions have been proved by Lovász and others [László Lovász, 2006; Michael Freedman et al., 2007; Christian Borgs et al., 2008; Alexander Schrijver, 2009; László Lovász and Balázs Szegedy, 2009]. These extend the basic 0-1 case to admit vertex and edge weights; but always with some restrictions such as all vertex weights must be positive. In this paper we prove a general form of this theorem where H can have arbitrary vertex and edge weights. An innovative aspect is that we prove this by a surprisingly simple and unified argument. This bypasses various technical obstacles and unifies and extends all previous known versions of this theorem on graphs. The constructive proof of our theorem can be used to make various complexity dichotomy theorems for graph homomorphism effective, i.e., it provides an algorithm that for any H either outputs a P-time algorithm solving hom(⋅, H) or a P-time reduction from a canonical #P-hard problem to hom(⋅, H).
Cite as

Jin-Yi Cai and Artem Govorov. On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.ITCS.2020.17,
  author =	{Cai, Jin-Yi and Govorov, Artem},
  title =	{{On a Theorem of Lov\'{a}sz that hom(⋅, H) Determines the Isomorphism Type of H}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.17},
  URN =		{urn:nbn:de:0030-drops-117022},
  doi =		{10.4230/LIPIcs.ITCS.2020.17},
  annote =	{Keywords: Graph homomorphism, Partition function, Complexity dichotomy, Connection matrices and tensors}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.8
On the Complexity of Anchored Rectangle Packing

Authors: Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, and Lukas Nölke

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In the Anchored Rectangle Packing (ARP) problem, we are given a set of points P in the unit square [0,1]^2 and seek a maximum-area set of axis-aligned interior-disjoint rectangles S, each of which is anchored at a point p in P. In the most prominent variant - Lower-Left-Anchored Rectangle Packing (LLARP) - rectangles are anchored in their lower-left corner. Freedman [W. T. Tutte (Ed.), 1969] conjectured in 1969 that, if (0,0) in P, then there is a LLARP that covers an area of at least 0.5. Somewhat surprisingly, this conjecture remains open to this day, with the best known result covering an area of 0.091 [Dumitrescu and Tóth, 2015]. Maybe even more surprisingly, it is not known whether LLARP - or any ARP-problem with only one anchor - is NP-hard. In this work, we first study the Center-Anchored Rectangle Packing (CARP) problem, where rectangles are anchored in their center. We prove NP-hardness and provide a PTAS. In fact, our PTAS applies to any ARP problem where the anchor lies in the interior of the rectangles. Afterwards, we turn to the LLARP problem and investigate two different resource-augmentation settings: In the first we allow an epsilon-perturbation of the input P, whereas in the second we permit an epsilon-overlap between rectangles. For the former setting, we give an algorithm that covers at least as much area as an optimal solution of the original problem. For the latter, we give an (1 - epsilon)-approximation.
Cite as

Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, and Lukas Nölke. On the Complexity of Anchored Rectangle Packing. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.ESA.2019.8,
  author =	{Antoniadis, Antonios and Biermeier, Felix and Cristi, Andr\'{e}s and Damerius, Christoph and Hoeksma, Ruben and Kaaser, Dominik and Kling, Peter and N\"{o}lke, Lukas},
  title =	{{On the Complexity of Anchored Rectangle Packing}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.8},
  URN =		{urn:nbn:de:0030-drops-111297},
  doi =		{10.4230/LIPIcs.ESA.2019.8},
  annote =	{Keywords: anchored rectangle, rectangle packing, resource augmentation, PTAS, NP, hardness}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.245
Interferometric Versus Projective Measurement of Anyons

Authors: Claire Levaillant and Michael Freedman

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
Two distinct methods for measuring topological charge in a nonabelian anyonic system have been discussed in the literature: projective measurement of a single point-like quasiparticle and interferometric measurement of the total topological charge of a group of quasiparticles. Projective measurement by definition is only applied near a point and will project to a topological charge sector near that point. Thus, if it is to be applied to a group of anyons to project to a total charge, then the anyons must first be fused one by one to obtain a single anyon carrying the collective charge. We show that interferometric measurement is strictly stronger: Any protocol involving projective measurement can be simulated at low overhead by another protocol involving only interferometric measurement.
Cite as

Claire Levaillant and Michael Freedman. Interferometric Versus Projective Measurement of Anyons. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 245-249, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{levaillant_et_al:LIPIcs.TQC.2015.245,
  author =	{Levaillant, Claire and Freedman, Michael},
  title =	{{Interferometric Versus Projective Measurement of Anyons}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{245--249},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.245},
  URN =		{urn:nbn:de:0030-drops-55600},
  doi =		{10.4230/LIPIcs.TQC.2015.245},
  annote =	{Keywords: anyons, measurement, interferometry, physics}
}
  • Refine by Author
  • 1 Antoniadis, Antonios
  • 1 Biermeier, Felix
  • 1 Cai, Jin-Yi
  • 1 Cristi, Andrés
  • 1 Damerius, Christoph
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Packing and covering problems
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Complexity dichotomy
  • 1 Connection matrices and tensors
  • 1 Graph homomorphism
  • 1 NP
  • 1 PTAS
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2015
  • 1 2019
  • 1 2020

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