5 Search Results for "Young, Ben"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.33
Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint

Authors: Jin-Yi Cai and Ben Young

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Recently, Mančinska and Roberson proved [Mančinska and Roberson, 2020] that two graphs G and G' are quantum isomorphic if and only if they admit the same number of homomorphisms from all planar graphs. We extend this result to planar #CSP with any pair of sets ℱ and ℱ' of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special case where each of ℱ and ℱ' contains a single symmetric 0-1-valued binary constraint function. Our treatment uses the framework of planar Holant problems. To prove that quantum isomorphic constraint function sets give the same value on any planar #CSP instance, we apply a novel form of holographic transformation of Valiant [Valiant, 2008], using the quantum permutation matrix 𝒰 defining the quantum isomorphism. Due to the noncommutativity of 𝒰’s entries, it turns out that this form of holographic transformation is only applicable to planar Holant. To prove the converse, we introduce the quantum automorphism group Qut(ℱ) of a set of constraint functions/tensors ℱ, and characterize the intertwiners of Qut(ℱ) as the signature matrices of planar Holant(ℱ | EQ) quantum gadgets. Then we define a new notion of (projective) connectivity for constraint functions and reduce arity while preserving the quantum automorphism group. Finally, to address the challenges posed by generalizing from 0-1 valued to real-valued constraint functions, we adapt a technique of Lovász [László Lovász, 1967] in the classical setting for isomorphisms of real-weighted graphs to the setting of quantum isomorphisms.
Cite as

Jin-Yi Cai and Ben Young. Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 33:1-33:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.ICALP.2023.33,
  author =	{Cai, Jin-Yi and Young, Ben},
  title =	{{Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.33},
  URN =		{urn:nbn:de:0030-drops-180851},
  doi =		{10.4230/LIPIcs.ICALP.2023.33},
  annote =	{Keywords: #CSP, Quantum isomorphism, Holant, Gadget, Intertwiners, Planar graphs}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.5
Optimal Distributed Covering Algorithms

Authors: Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, and Gregory Schwartzman

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f. The approximation factor of our algorithm is (f+epsilon). Let Delta denote the maximum degree in the hypergraph. Our algorithm runs in the congest model and requires O(log{Delta} / log log Delta) rounds, for constants epsilon in (0,1] and f in N^+. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal distributed algorithms. For constant values of f and epsilon, our algorithm improves over the (f+epsilon)-approximation algorithm of [Fabian Kuhn et al., 2006] whose running time is O(log Delta + log W), where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f-approximation for the problem in O(f log n) rounds, improving over the classical result of [Samir Khuller et al., 1994] that achieves a running time of O(f log^2 n). Finally, for weighted vertex cover (f=2) our algorithm achieves a deterministic running time of O(log n), matching the randomized previously best result of [Koufogiannakis and Young, 2011]. We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an (f+epsilon)-approximate integral solution in O((1+f/log n)* ((log Delta)/(log log Delta) + (f * log M)^{1.01}* log epsilon^{-1}* (log Delta)^{0.01})) rounds, where f bounds the number of variables in a constraint, Delta bounds the number of constraints a variable appears in, and M=max {1, ceil[1/a_{min}]}, where a_{min} is the smallest normalized constraint coefficient. This improves over the results of [Fabian Kuhn et al., 2006] for the integral case, which combined with rounding achieves the same guarantees in O(epsilon^{-4}* f^4 * log f * log(M * Delta)) rounds.
Cite as

Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Optimal Distributed Covering Algorithms. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 5:1-5:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.DISC.2019.5,
  author =	{Ben-Basat, Ran and Even, Guy and Kawarabayashi, Ken-ichi and Schwartzman, Gregory},
  title =	{{Optimal Distributed Covering Algorithms}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.5},
  URN =		{urn:nbn:de:0030-drops-113129},
  doi =		{10.4230/LIPIcs.DISC.2019.5},
  annote =	{Keywords: Distributed Algorithms, Approximation Algorithms, Vertex Cover, Set Cover}
}
Document
DOI: 10.4230/OASIcs.CMN.2016.9
Summarizing and Comparing Story Plans

Authors: Adam Amos-Binks, David L. Roberts, and R. Michael Young

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract
Branching story games have gained popularity for creating unique playing experiences by adapting story content in response to user actions. Research in interactive narrative (IN) uses automated planning to generate story plans for a given story problem. However, a story planner can generate multiple story plan solutions, all of which equally-satisfy the story problem definition but contain different story content. These differences in story content are key to understanding the story branches in a story problem's solution space, however we lack narrative-theoretic metrics to compare story plans. We address this gap by first defining a story plan summarization model to capture the important story semantics from a story plan. Secondly, we define a story plan comparison metric that compares story plans based on the summarization model. Using the Glaive narrative planner and a simple story problem, we demonstrate the usefulness of using the summarization model and distance metric to characterize the different story branches in a story problem's solution space.
Cite as

Adam Amos-Binks, David L. Roberts, and R. Michael Young. Summarizing and Comparing Story Plans. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 9:1-9:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{amosbinks_et_al:OASIcs.CMN.2016.9,
  author =	{Amos-Binks, Adam and Roberts, David L. and Young, R. Michael},
  title =	{{Summarizing and Comparing Story Plans}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{9:1--9:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.9},
  URN =		{urn:nbn:de:0030-drops-67100},
  doi =		{10.4230/OASIcs.CMN.2016.9},
  annote =	{Keywords: artifical intelligence, planning, narrative, comparison, story}
}
Document
DOI: 10.4230/OASIcs.CMN.2015.45
Impulse: a Formal Characterization of Story

Authors: Markus Eger, Camille Barot, and R. Michael Young

Published in: OASIcs, Volume 45, 6th Workshop on Computational Models of Narrative (CMN 2015)

Abstract
We present a novel representation of narratives at the story level called Impulse. It combines a temporal representation of a story’s actions and events with a representation of the mental models of the story’s characters into a cohesive, logic-based language. We show the expressiveness of this approach by encoding a story fragment, and compare it to other formal story representations in terms of representational dimensions. We also acknowledge the computational complexity of our approach and argue that a restricted subset still provides a high degree of expressive power
Cite as

Markus Eger, Camille Barot, and R. Michael Young. Impulse: a Formal Characterization of Story. In 6th Workshop on Computational Models of Narrative (CMN 2015). Open Access Series in Informatics (OASIcs), Volume 45, pp. 45-53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{eger_et_al:OASIcs.CMN.2015.45,
  author =	{Eger, Markus and Barot, Camille and Young, R. Michael},
  title =	{{Impulse: a Formal Characterization of Story}},
  booktitle =	{6th Workshop on Computational Models of Narrative (CMN 2015)},
  pages =	{45--53},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-93-4},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{45},
  editor =	{Finlayson, Mark A. and Miller, Ben and Lieto, Antonio and Ronfard, Remi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2015.45},
  URN =		{urn:nbn:de:0030-drops-52800},
  doi =		{10.4230/OASIcs.CMN.2015.45},
  annote =	{Keywords: Narrative, logic, representation, mental models, time}
}
Document
DOI: 10.4230/OASIcs.CMN.2015.152
Good Timing for Computational Models of Narrative Discourse

Authors: David R. Winer, Adam A. Amos-Binks, Camille Barot, and R. Michael Young

Published in: OASIcs, Volume 45, 6th Workshop on Computational Models of Narrative (CMN 2015)

Abstract
The temporal order in which story events are presented in discourse can greatly impact how readers experience narrative; however, it remains unclear how narrative systems can leverage temporal order to affect comprehension and experience. We define structural properties of discourse which provide a basis for computational narratologists to reason about good timing, such as when readers learn about event relationships.
Cite as

David R. Winer, Adam A. Amos-Binks, Camille Barot, and R. Michael Young. Good Timing for Computational Models of Narrative Discourse. In 6th Workshop on Computational Models of Narrative (CMN 2015). Open Access Series in Informatics (OASIcs), Volume 45, pp. 152-156, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{winer_et_al:OASIcs.CMN.2015.152,
  author =	{Winer, David R. and Amos-Binks, Adam A. and Barot, Camille and Young, R. Michael},
  title =	{{Good Timing for Computational Models of Narrative Discourse}},
  booktitle =	{6th Workshop on Computational Models of Narrative (CMN 2015)},
  pages =	{152--156},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-93-4},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{45},
  editor =	{Finlayson, Mark A. and Miller, Ben and Lieto, Antonio and Ronfard, Remi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2015.152},
  URN =		{urn:nbn:de:0030-drops-52897},
  doi =		{10.4230/OASIcs.CMN.2015.152},
  annote =	{Keywords: causal inference, narrative, discourse structure, computational model}
}
  • Refine by Author
  • 3 Young, R. Michael
  • 2 Barot, Camille
  • 1 Amos-Binks, Adam
  • 1 Amos-Binks, Adam A.
  • 1 Ben-Basat, Ran
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 narrative
  • 1 #CSP
  • 1 Approximation Algorithms
  • 1 Distributed Algorithms
  • 1 Gadget
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2015
  • 1 2016
  • 1 2019
  • 1 2023

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact