16 Search Results for "Young, R. Michael"


Document
Approximating Single-Source Personalized PageRank with Absolute Error Guarantees

Authors: Zhewei Wei, Ji-Rong Wen, and Mingji Yang

Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)


Abstract
Personalized PageRank (PPR) is an extensively studied and applied node proximity measure in graphs. For a pair of nodes s and t on a graph G = (V,E), the PPR value π(s,t) is defined as the probability that an α-discounted random walk from s terminates at t, where the walk terminates with probability α at each step. We study the classic Single-Source PPR query, which asks for PPR approximations from a given source node s to all nodes in the graph. Specifically, we aim to provide approximations with absolute error guarantees, ensuring that the resultant PPR estimates π̂(s,t) satisfy max_{t ∈ V} |π̂(s,t)-π(s,t)| ≤ ε for a given error bound ε. We propose an algorithm that achieves this with high probability, with an expected running time of - Õ(√m/ε) for directed graphs, where m = |E|; - Õ(√{d_max}/ε) for undirected graphs, where d_max is the maximum node degree in the graph; - Õ(n^{γ-1/2}/ε) for power-law graphs, where n = |V| and γ ∈ (1/2,1) is the extent of the power law. These sublinear bounds improve upon existing results. We also study the case when degree-normalized absolute error guarantees are desired, requiring max_{t ∈ V} |π̂(s,t)/d(t)-π(s,t)/d(t)| ≤ ε_d for a given error bound ε_d, where the graph is undirected and d(t) is the degree of node t. We give an algorithm that provides this error guarantee with high probability, achieving an expected complexity of Õ(√{∑_{t ∈ V} π(s,t)/d(t)}/ε_d). This improves over the previously known O(1/ε_d) complexity.

Cite as

Zhewei Wei, Ji-Rong Wen, and Mingji Yang. Approximating Single-Source Personalized PageRank with Absolute Error Guarantees. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{wei_et_al:LIPIcs.ICDT.2024.9,
  author =	{Wei, Zhewei and Wen, Ji-Rong and Yang, Mingji},
  title =	{{Approximating Single-Source Personalized PageRank with Absolute Error Guarantees}},
  booktitle =	{27th International Conference on Database Theory (ICDT 2024)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-312-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{290},
  editor =	{Cormode, Graham and Shekelyan, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.9},
  URN =		{urn:nbn:de:0030-drops-197911},
  doi =		{10.4230/LIPIcs.ICDT.2024.9},
  annote =	{Keywords: Graph Algorithms, Sublinear Algorithms, Personalized PageRank}
}
Document
Survey
Structural Summarization of Semantic Graphs Using Quotients

Authors: Ansgar Scherp, David Richerby, Till Blume, Michael Cochez, and Jannik Rau

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1


Abstract
Graph summarization is the process of computing a compact version of an input graph while preserving chosen features of its structure. We consider semantic graphs where the features include edge labels and label sets associated with a vertex. Graph summaries are typically much smaller than the original graph. Applications that depend on the preserved features can perform their tasks on the summary, but much faster or with less memory overhead, while producing the same outcome as if they were applied on the original graph. In this survey, we focus on structural summaries based on quotients that organize vertices in equivalence classes of shared features. Structural summaries are particularly popular for semantic graphs and have the advantage of defining a precise graph-based output. We consider approaches and algorithms for both static and temporal graphs. A common example of quotient-based structural summaries is bisimulation, and we discuss this in detail. While there exist other surveys on graph summarization, to the best of our knowledge, we are the first to bring in a focused discussion on quotients, bisimulation, and their relation. Furthermore, structural summarization naturally connects well with formal logic due to the discrete structures considered. We complete the survey with a brief description of approaches beyond structural summaries.

Cite as

Ansgar Scherp, David Richerby, Till Blume, Michael Cochez, and Jannik Rau. Structural Summarization of Semantic Graphs Using Quotients. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 12:1-12:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@Article{scherp_et_al:TGDK.1.1.12,
  author =	{Scherp, Ansgar and Richerby, David and Blume, Till and Cochez, Michael and Rau, Jannik},
  title =	{{Structural Summarization of Semantic Graphs Using Quotients}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{12:1--12:25},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/TGDK.1.1.12},
  URN =		{urn:nbn:de:0030-drops-194862},
  doi =		{10.4230/TGDK.1.1.12},
  annote =	{Keywords: graph summarization, quotients, stratified bisimulation}
}
Document
Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs

Authors: Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted drawings. A simple drawing is generalized twisted if there is a point O such that every ray emanating from O crosses every edge of the drawing at most once and there is a ray emanating from O which crosses every edge exactly once. Via this new class of simple drawings, we show that every simple drawing of the complete graph with n vertices contains Ω(n^{1/2}) pairwise disjoint edges and a plane path of length Ω((log n)/(log log n)). Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest.

Cite as

Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2022.5,
  author =	{Aichholzer, Oswin and Garc{\'\i}a, Alfredo and Tejel, Javier and Vogtenhuber, Birgit and Weinberger, Alexandra},
  title =	{{Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.5},
  URN =		{urn:nbn:de:0030-drops-160136},
  doi =		{10.4230/LIPIcs.SoCG.2022.5},
  annote =	{Keywords: Simple drawings, simple topological graphs, disjoint edges, plane matching, plane path}
}
Document
Simple Contention Resolution via Multiplicative Weight Updates

Authors: Yi-Jun Chang, Wenyu Jin, and Seth Pettie

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)


Abstract
We consider the classic contention resolution problem, in which devices conspire to share some common resource, for which they each need temporary and exclusive access. To ground the discussion, suppose (identical) devices wake up at various times, and must send a single packet over a shared multiple-access channel. In each time step they may attempt to send their packet; they receive ternary feedback {0,1,2^+} from the channel, 0 indicating silence (no one attempted transmission), 1 indicating success (one device successfully transmitted), and 2^+ indicating noise. We prove that a simple strategy suffices to achieve a channel utilization rate of 1/e-O(epsilon), for any epsilon>0. In each step, device i attempts to send its packet with probability p_i, then applies a rudimentary multiplicative weight-type update to p_i. p_i <- { p_i * e^{epsilon} upon hearing silence (0), p_i upon hearing success (1), p_i * e^{-epsilon/(e-2)} upon hearing noise (2^+) }. This scheme works well even if the introduction of devices/packets is adversarial, and even if the adversary can jam time slots (make noise) at will. We prove that if the adversary jams J time slots, then this scheme will achieve channel utilization 1/e-epsilon, excluding O(J) wasted slots. Results similar to these (Bender, Fineman, Gilbert, Young, SODA 2016) were already achieved, but with a lower constant efficiency (less than 0.05) and a more complex algorithm.

Cite as

Yi-Jun Chang, Wenyu Jin, and Seth Pettie. Simple Contention Resolution via Multiplicative Weight Updates. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{chang_et_al:OASIcs.SOSA.2019.16,
  author =	{Chang, Yi-Jun and Jin, Wenyu and Pettie, Seth},
  title =	{{Simple Contention Resolution via Multiplicative Weight Updates}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{16:1--16:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.16},
  URN =		{urn:nbn:de:0030-drops-100426},
  doi =		{10.4230/OASIcs.SOSA.2019.16},
  annote =	{Keywords: Contention resolution, multiplicative weight update method}
}
Document
Periodic Pólya Urns and an Application to Young Tableaux

Authors: Cyril Banderier, Philippe Marchal, and Michael Wallner

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
Pólya urns are urns where at each unit of time a ball is drawn and is replaced with some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We discuss some intriguing properties of the differential operators associated to the generating functions encoding the evolution of these urns. The initial non-linear partial differential equation indeed leads to linear differential equations and we prove that the moment generating functions are D-finite. For a subclass, we exhibit a closed form for the corresponding generating functions (giving the exact state of the urns at time n). When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. En passant, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.

Cite as

Cyril Banderier, Philippe Marchal, and Michael Wallner. Periodic Pólya Urns and an Application to Young Tableaux. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2018.11,
  author =	{Banderier, Cyril and Marchal, Philippe and Wallner, Michael},
  title =	{{Periodic P\'{o}lya Urns and an Application to Young Tableaux}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.11},
  URN =		{urn:nbn:de:0030-drops-89045},
  doi =		{10.4230/LIPIcs.AofA.2018.11},
  annote =	{Keywords: P\'{o}lya urn, Young tableau, generating functions, analytic combinatorics, pumping moment, D-finite function, hypergeometric function, generalized Gamma distribution, Mittag-Leffler distribution}
}
Document
Artificial and Computational Intelligence in Games: AI-Driven Game Design (Dagstuhl Seminar 17471)

Authors: Pieter Spronck, Elisabeth André, Michael Cook, and Mike Preuß

Published in: Dagstuhl Reports, Volume 7, Issue 11 (2018)


Abstract
With the dramatic growth of the game industry over the past decade, its rapid inclusion in many sectors of today's society, and the increased complexity of games, game development has reached a point where it is no longer humanly possible to use only manual techniques to create games. Large parts of games need to be designed, built, and tested automatically. In recent years, researchers have delved into artificial intelligence techniques to support, assist, and even drive game development. Such techniques include procedural content generation, automated narration, player modelling and adaptation, and automated game design. This research is still very young, but already the games industry is taking small steps to integrate some of these techniques in their approach to design. The goal of this seminar was to bring together researchers and industry representatives who work at the forefront of artificial intelligence (AI) and computational intelligence (CI) in games, to (1) explore and extend the possibilities of AI-driven game design, (2) to identify the most viable applications of AI-driven game design in the game industry, and (3) to investigate new approaches to AI-driven game design. To this end, the seminar included a wide range of researchers and developers, including specialists in AI/CI for abstract games, commercial video games, and serious games. Thus, it fostered a better understanding of and unified vision on AI-driven game design, using input from both scientists as well as AI specialists from industry.

Cite as

Pieter Spronck, Elisabeth André, Michael Cook, and Mike Preuß. Artificial and Computational Intelligence in Games: AI-Driven Game Design (Dagstuhl Seminar 17471). In Dagstuhl Reports, Volume 7, Issue 11, pp. 86-129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@Article{spronck_et_al:DagRep.7.11.86,
  author =	{Spronck, Pieter and Andr\'{e}, Elisabeth and Cook, Michael and Preu{\ss}, Mike},
  title =	{{Artificial and Computational Intelligence in Games: AI-Driven Game Design (Dagstuhl Seminar 17471)}},
  pages =	{86--129},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{11},
  editor =	{Spronck, Pieter and Andr\'{e}, Elisabeth and Cook, Michael and Preu{\ss}, Mike},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.11.86},
  URN =		{urn:nbn:de:0030-drops-86722},
  doi =		{10.4230/DagRep.7.11.86},
  annote =	{Keywords: dynamical systems, entertainment modeling, game design, multi-agent systems, serious games}
}
Document
Automated Program Repair (Dagstuhl Seminar 17022)

Authors: Sunghun Kim, Claire Le Goues, Michael Pradel, and Abhik Roychoudhury

Published in: Dagstuhl Reports, Volume 7, Issue 1 (2017)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17022 "Automated Program Repair". The seminar participants presented and discussed their research through formal and informal presentations. In particular, the seminar covered work related to search-based program repair, semantic program repair, and repair of non-functional properties. As a result of the seminar, several participants plan to launch various follow-up activities, such as a program repair competition, which would help to further establish and guide this young field of research.

Cite as

Sunghun Kim, Claire Le Goues, Michael Pradel, and Abhik Roychoudhury. Automated Program Repair (Dagstuhl Seminar 17022). In Dagstuhl Reports, Volume 7, Issue 1, pp. 19-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Article{kim_et_al:DagRep.7.1.19,
  author =	{Kim, Sunghun and Le Goues, Claire and Pradel, Michael and Roychoudhury, Abhik},
  title =	{{Automated Program Repair (Dagstuhl Seminar 17022)}},
  pages =	{19--31},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{1},
  editor =	{Kim, Sunghun and Le Goues, Claire and Pradel, Michael and Roychoudhury, Abhik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.1.19},
  URN =		{urn:nbn:de:0030-drops-71767},
  doi =		{10.4230/DagRep.7.1.19},
  annote =	{Keywords: Program repair, program analysis, software engineering}
}
Document
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
Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time

Authors: Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)


Abstract
We study the problem of approximately solving positive linear programs (LPs). This class of LPs models a wide range of fundamental problems in combinatorial optimization and operations research, such as many resource allocation problems, solving non-negative linear systems, computing tomography, single/multi commodity flows on graphs, etc. For the special cases of pure packing or pure covering LPs, recent result by Allen-Zhu and Orecchia [Allen/Zhu/Orecchia, SODA'15] gives O˜(1/(epsilon^3))-time parallel algorithm, which breaks the longstanding O˜(1/(epsilon^4)) running time bound by the seminal work of Luby and Nisan [Luby/Nisan, STOC'93]. We present new parallel algorithm with running time O˜(1/(epsilon^3)) for the more general mixed packing and covering LPs, which improves upon the O˜(1/(epsilon^4))-time algorithm of Young [Young, FOCS'01; Young, arXiv 2014]. Our work leverages the ideas from both the optimization oriented approach [Allen/Zhu/Orecchia, SODA'15; Wang/Mahoney/Mohan/Rao, arXiv 2015], as well as the more combinatorial approach with phases [Young, FOCS'01; Young, arXiv 2014]. In addition, our algorithm, when directly applied to pure packing or pure covering LPs, gives a improved running time of O˜(1/(epsilon^2)).

Cite as

Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang. Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{mahoney_et_al:LIPIcs.ICALP.2016.52,
  author =	{Mahoney, Michael W. and Rao, Satish and Wang, Di and Zhang, Peng},
  title =	{{Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^\{-3\}) Time}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.52},
  URN =		{urn:nbn:de:0030-drops-63335},
  doi =		{10.4230/LIPIcs.ICALP.2016.52},
  annote =	{Keywords: Mixed packing and covering, Linear program, Approximation algorithm, Parallel algorithm}
}
Document
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-dev.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
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-dev.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}
}
Document
CB-POCL: A Choice-Based Algorithm for Character Personality in Planning-based Narrative Generation

Authors: Julio César Bahamón and R. Michael Young

Published in: OASIcs, Volume 32, 2013 Workshop on Computational Models of Narrative


Abstract
The quality and believability of a story can be significantly enhanced by the presence of compelling characters. Characters can be made more compelling by the portrayal of a distinguishable personality. This paper presents an algorithm that formalizes an approach previously described for the incorporation of character personality in narrative that is automatically generated. The approach is based on a computational model that operationalizes personality as behavior that results from the choices made by characters in the course of a story. This operationalization is based on the Big Five personality structure and results from behavioral psychology studies that link behavior to personality traits.

Cite as

Julio César Bahamón and R. Michael Young. CB-POCL: A Choice-Based Algorithm for Character Personality in Planning-based Narrative Generation. In 2013 Workshop on Computational Models of Narrative. Open Access Series in Informatics (OASIcs), Volume 32, pp. 4-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{bahamon_et_al:OASIcs.CMN.2013.4,
  author =	{Baham\'{o}n, Julio C\'{e}sar and Young, R. Michael},
  title =	{{CB-POCL: A Choice-Based Algorithm for Character Personality in Planning-based Narrative Generation}},
  booktitle =	{2013 Workshop on Computational Models of Narrative},
  pages =	{4--23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-57-6},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{32},
  editor =	{Finlayson, Mark A. and Fisseni, Bernhard and L\"{o}we, Benedikt and Meister, Jan Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2013.4},
  URN =		{urn:nbn:de:0030-drops-41601},
  doi =		{10.4230/OASIcs.CMN.2013.4},
  annote =	{Keywords: Artificial Intelligence, Planning, Narrative Generation}
}
Document
09341 Summary – Cognition, Control and Learning for Robot Manipulation in Human Environments

Authors: Michael Beetz, Oliver Brock, Gordon Cheng, and Jan Peters

Published in: Dagstuhl Seminar Proceedings, Volume 9341, Cognition, Control and Learning for Robot Manipulation in Human Environments (2010)


Abstract
High performance robot arms are faster, more accurate, and stronger than humans. Yet many manipulation tasks that are easily performed by humans as part of their daily life are well beyond the capabilities of such robots. The main reason for this superiority is that humans can rely upon neural information processing and control mechanisms which are tailored for performing complex motor skills, adapting to uncertain environments and to not imposing a danger to surrounding humans. As we are working towards autonomous service robots operating and performing manipulation in the presence of humans and in human living and working environments, the robots must exhibit similar levels of flexibility, compliance, and adaptivity. The goal of this Dagstuhl seminar is to make a big step towards pushing robot manipulation forward such that robot assisted living can become a concrete vision for the future. In order to achieve this goal, the computational aspects of everyday manipulation tasks need to be well-understood, and requires the thorough study of the interaction of perceptual, learning, reasoning, planning, and control mechanisms. The challenges to be met include cooperation with humans, uncertainty in both task and environments, real-time action requirements, and the use of tools. The challenges cannot be met by merely improving the software engineering and programming techniques. Rather the systems need built-in capabilities to deal with these challenges. Looking at natural intelligent systems, the most promising approach for handling them is to equip the systems with more powerful cognitive mechanisms. The potential impact of bringing cognition, control and learning methods together for robotic manipulation can be enormous. This urge for such concerted approaches is reflected by a large number of national and international research initiatives including the DARPA cognitive systems initiative of the Information Processing Technoloy Office, various integrated projects funded by the European Community, the British Foresight program for cognitive systems, huge Japanese research efforts, to name only a few. As a result, many researchers all over the world engage in cognitive system research and there is need for and value in discussion. These discussions become particularly promising because of the growing readiness of researchers of different disciplines to talk to each other. Early results of such interdisciplinary crossfertilization can already be observed and we only intend to give a few examples: Cognitive psychologists have presented empirical evidence for the use of Bayesian estimation and discovered the cost functions possibly underlying human motor control. Neuroscientists have shown that reinforcement learning algorithms can be used to explain the role of Dopamine in the human basal ganglia as well as the functioning of the bea brain. Computer scientists and engineers have shown that the understanding of brain mechanisms can result into realiable learning algorithms as well as control setups. Insights from artificial intelligence such as Bayesian networks and the associated reasoning and learning mechanisms have inspired research in cognitive psychology, in particular the formation of causal theory in young children. These examples suggest that (1)~successful computational mechanisms in artificial cognitive systems tend to have counterparts with similar functionality in natural cognitive systems; and (2)~new consolidated findings about the structure and functional organization of perception and motion control in natural cognitive systems indicate in a number of cases much better ways of organizing and specifying computational tasks in artificial cognitive systems.

Cite as

Michael Beetz, Oliver Brock, Gordon Cheng, and Jan Peters. 09341 Summary – Cognition, Control and Learning for Robot Manipulation in Human Environments. In Cognition, Control and Learning for Robot Manipulation in Human Environments. Dagstuhl Seminar Proceedings, Volume 9341, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{beetz_et_al:DagSemProc.09341.2,
  author =	{Beetz, Michael and Brock, Oliver and Cheng, Gordon and Peters, Jan},
  title =	{{09341 Summary – Cognition, Control and Learning for Robot Manipulation in Human Environments}},
  booktitle =	{Cognition, Control and Learning for Robot Manipulation in Human Environments},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9341},
  editor =	{Michael Beetz and Oliver Brock and Gordon Cheng and Jan Peters},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09341.2},
  URN =		{urn:nbn:de:0030-drops-23647},
  doi =		{10.4230/DagSemProc.09341.2},
  annote =	{Keywords: Mobile manipulation, cognition, control, learning, humanoid robot, unstructured environments}
}
Document
Creative Computers, Improvisation and Intimacy

Authors: Michael Young

Published in: Dagstuhl Seminar Proceedings, Volume 9291, Computational Creativity: An Interdisciplinary Approach (2009)


Abstract
Autonomous musical machine partners, ‘live algorithms’, are able to collaborate with human improvisers on an equal footing. Adaptability can be a significant factor in human/machine interaction in this context. Intimacy is an additional factor; intimacy might be achieved if human and machine performers can adapt to each other and learn from one another. Previously associated in computer music with ideas of embodiment and HCI, ‘intimacy’ as more widely understood, refers to the interpersonal process enjoyed between individuals, in which personal self-disclosure finds validation through a partner’s response. Real intimacies are learned over time, not designed, and are based upon an evident reciprocity and emergent mutuality. In the context of musical expression, a social – rather than a biological/technological –discourse can be applied to live algorithms with a capacity for learning. This possibility is explored with reference to the author’s various improvisation/composition systems including au(or)a, piano_prosthesis, and oboe_prosthesis.

Cite as

Michael Young. Creative Computers, Improvisation and Intimacy. In Computational Creativity: An Interdisciplinary Approach. Dagstuhl Seminar Proceedings, Volume 9291, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{young:DagSemProc.09291.12,
  author =	{Young, Michael},
  title =	{{Creative Computers, Improvisation and Intimacy}},
  booktitle =	{Computational Creativity: An Interdisciplinary Approach},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9291},
  editor =	{Margaret Boden and Mark D'Inverno and Jon McCormack},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09291.12},
  URN =		{urn:nbn:de:0030-drops-22222},
  doi =		{10.4230/DagSemProc.09291.12},
  annote =	{Keywords: Computational creativity, improvisation, intimacy, composition, live algorithm, neural network, computer music, adaptation}
}
Document
Stimulating creative flow through computational feedback

Authors: Daniel Jones, Oliver Bown, Jon McCormack, Francois Pachet, Michael Young, Rodney Berry, Iris Asaf, and Benjamin Porter

Published in: Dagstuhl Seminar Proceedings, Volume 9291, Computational Creativity: An Interdisciplinary Approach (2009)


Abstract
This report summarises the discussion and experimental work produced by the authors at the 2009 symposium Computational Creativity: An Interdisciplinary Approach, Dagstuhl Leibniz-Zentrum für Informatik. It outlines the motivation for using computational techniques to stimulate human creativity, briefly summarising its historical context and predecessors, and describes two software studies produced by the group as base-line exemplars of these ideas.

Cite as

Daniel Jones, Oliver Bown, Jon McCormack, Francois Pachet, Michael Young, Rodney Berry, Iris Asaf, and Benjamin Porter. Stimulating creative flow through computational feedback. In Computational Creativity: An Interdisciplinary Approach. Dagstuhl Seminar Proceedings, Volume 9291, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{jones_et_al:DagSemProc.09291.28,
  author =	{Jones, Daniel and Bown, Oliver and McCormack, Jon and Pachet, Francois and Young, Michael and Berry, Rodney and Asaf, Iris and Porter, Benjamin},
  title =	{{Stimulating creative flow through computational feedback}},
  booktitle =	{Computational Creativity: An Interdisciplinary Approach},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9291},
  editor =	{Margaret Boden and Mark D'Inverno and Jon McCormack},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09291.28},
  URN =		{urn:nbn:de:0030-drops-22232},
  doi =		{10.4230/DagSemProc.09291.28},
  annote =	{Keywords: Computational creativity}
}
  • Refine by Author
  • 4 Young, R. Michael
  • 2 Barot, Camille
  • 2 Young, Michael
  • 1 Aichholzer, Oswin
  • 1 Amos-Binks, Adam
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 1 General and reference → Surveys and overviews
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Distribution functions
  • 1 Mathematics of computing → Enumeration
  • Show More...

  • Refine by Keyword
  • 2 Computational creativity
  • 2 narrative
  • 1 Approximation algorithm
  • 1 Artificial Intelligence
  • 1 Contention resolution
  • Show More...

  • Refine by Type
  • 16 document

  • Refine by Publication Year
  • 2 2009
  • 2 2015
  • 2 2016
  • 2 2018
  • 1 2006
  • 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