6 Search Results for "Davis, James"


Document
Dynamic Size Counting in Population Protocols

Authors: David Doty and Mahsa Eftekhari

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
The population protocol model describes a network of anonymous agents that interact asynchronously in pairs chosen at random. Each agent starts in the same initial state s. We introduce the dynamic size counting problem: approximately counting the number of agents in the presence of an adversary who at any time can remove any number of agents or add any number of new agents in state s. A valid solution requires that after each addition/removal event, resulting in population size n, with high probability each agent "quickly" computes the same constant-factor estimate of the value log₂(n) (how quickly is called the convergence time), which remains the output of every agent for as long as possible (the holding time). Since the adversary can remove agents, the holding time is necessarily finite: even after the adversary stops altering the population, it is impossible to stabilize to an output that never again changes. We first show that a protocol solves the dynamic size counting problem if and only if it solves the loosely-stabilizing counting problem: that of estimating log n in a fixed-size population, but where the adversary can initialize each agent in an arbitrary state, with the same convergence time and holding time. We then show a protocol solving the loosely-stabilizing counting problem with the following guarantees: if the population size is n, M is the largest initial estimate of log n, and s is the maximum integer initially stored in any field of the agents' memory, we have expected convergence time O(log n + log M), expected polynomial holding time, and expected memory usage of O(log²(s) + (log log n)²) bits. Interpreted as a dynamic size counting protocol, when changing from population size n_prev to n_next, the convergence time is O(log n_next + log log n_prev).

Cite as

David Doty and Mahsa Eftekhari. Dynamic Size Counting in Population Protocols. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{doty_et_al:LIPIcs.SAND.2022.13,
  author =	{Doty, David and Eftekhari, Mahsa},
  title =	{{Dynamic Size Counting in Population Protocols}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.13},
  URN =		{urn:nbn:de:0030-drops-159558},
  doi =		{10.4230/LIPIcs.SAND.2022.13},
  annote =	{Keywords: Loosely-stabilizing, population protocols, size counting}
}
Document
Simulating 3-Symbol Turing Machines with SIMD||DNA

Authors: David Doty and Aaron Ong

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
SIMD||DNA [Wang et al., 2019] is a model of DNA strand displacement allowing parallel in-memory computation on DNA storage. We show how to simulate an arbitrary 3-symbol space-bounded Turing machine with a SIMD||DNA program, giving a more direct and efficient route to general-purpose information manipulation on DNA storage than the Rule 110 simulation of Wang, Chalk, and Soloveichik [Wang et al., 2019]. We also develop software (https://github.com/UC-Davis-molecular-computing/simd-dna) that can simulate SIMD||DNA programs and produce SVG figures.

Cite as

David Doty and Aaron Ong. Simulating 3-Symbol Turing Machines with SIMD||DNA. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{doty_et_al:LIPIcs.SAND.2022.14,
  author =	{Doty, David and Ong, Aaron},
  title =	{{Simulating 3-Symbol Turing Machines with SIMD||DNA}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.14},
  URN =		{urn:nbn:de:0030-drops-159568},
  doi =		{10.4230/LIPIcs.SAND.2022.14},
  annote =	{Keywords: DNA storage, strand displacement, parallel computation}
}
Document
Machine Learning in Sports (Dagstuhl Seminar 21411)

Authors: Ulf Brefeld, Jesse Davis, Martin Lames, and James J. Little

Published in: Dagstuhl Reports, Volume 11, Issue 9 (2022)


Abstract
Data about sports have long been the subject of research and analysis by sports scientists. The increasing size and availability of these data have also attracted the attention of researchers in machine learning, computer vision and artificial intelligence. However, these communities rarely interact. This seminar aimed to bring together researchers from these areas to spur an interdisciplinary approach to these problems. The seminar was organized around five different themes that were introduced with tutorial and overview style talks about the key concepts to facilitate knowledge exchange among researchers with different backgrounds and approaches to data-based sports research. These were augmented by more in-depth presentations on specific problems or techniques. There was a panel discussion by practitioners on the difficulties and lessons learned about putting analytics into practice. Finally, we came up with a number of conclusions and next steps.

Cite as

Ulf Brefeld, Jesse Davis, Martin Lames, and James J. Little. Machine Learning in Sports (Dagstuhl Seminar 21411). In Dagstuhl Reports, Volume 11, Issue 9, pp. 45-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@Article{brefeld_et_al:DagRep.11.9.45,
  author =	{Brefeld, Ulf and Davis, Jesse and Lames, Martin and Little, James J.},
  title =	{{Machine Learning in Sports (Dagstuhl Seminar 21411)}},
  pages =	{45--63},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{11},
  number =	{9},
  editor =	{Brefeld, Ulf and Davis, Jesse and Lames, Martin and Little, James J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.11.9.45},
  URN =		{urn:nbn:de:0030-drops-159178},
  doi =		{10.4230/DagRep.11.9.45},
  annote =	{Keywords: machine learning, artificial intelligence, sports science, computer vision, explanations, visualization, tactics, health, biomechanics}
}
Document
Message Complexity of Population Protocols

Authors: Talley Amir, James Aspnes, David Doty, Mahsa Eftekhari, and Eric Severson

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)


Abstract
The standard population protocol model assumes that when two agents interact, each observes the entire state of the other. We initiate the study of message complexity for population protocols, where an agent’s state is divided into an externally-visible message and externally-hidden local state. We consider the case of O(1) message complexity. When time is unrestricted, we obtain an exact characterization of the stably computable predicates based on the number of internal states s(n): If s(n) = o(n) then the protocol computes semilinear predicates (unlike the original model, which can compute non-semilinear predicates with s(n) = O(log n)), and otherwise it computes a predicate decidable by a nondeterministic O(n log s(n))-space-bounded Turing machine. We then introduce novel O(polylog(n)) expected time protocols for junta/leader election and general purpose broadcast correct with high probability, and approximate and exact population size counting correct with probability 1. Finally, we show that the main constraint on the power of bounded-message-size protocols is the size of the internal states: with unbounded internal states, any computable function can be computed with probability 1 in the limit by a protocol that uses only 1-bit messages.

Cite as

Talley Amir, James Aspnes, David Doty, Mahsa Eftekhari, and Eric Severson. Message Complexity of Population Protocols. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.DISC.2020.6,
  author =	{Amir, Talley and Aspnes, James and Doty, David and Eftekhari, Mahsa and Severson, Eric},
  title =	{{Message Complexity of Population Protocols}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.6},
  URN =		{urn:nbn:de:0030-drops-130848},
  doi =		{10.4230/LIPIcs.DISC.2020.6},
  annote =	{Keywords: population protocol, message complexity, space-optimal}
}
Document
Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs

Authors: Pinar Heggernes, Davis Issac, Juho Lauri, Paloma T. Lima, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)


Abstract
Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.

Cite as

Pinar Heggernes, Davis Issac, Juho Lauri, Paloma T. Lima, and Erik Jan van Leeuwen. Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 83:1-83:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{heggernes_et_al:LIPIcs.MFCS.2018.83,
  author =	{Heggernes, Pinar and Issac, Davis and Lauri, Juho and Lima, Paloma T. and van Leeuwen, Erik Jan},
  title =	{{Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{83:1--83:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.83},
  URN =		{urn:nbn:de:0030-drops-96657},
  doi =		{10.4230/LIPIcs.MFCS.2018.83},
  annote =	{Keywords: Rainbow coloring, graph classes, polynomial-time algorithms, approximation algorithms}
}
Document
Time-of-Flight Imaging: Algorithms, Sensors and Applications (Dagstuhl Seminar 12431)

Authors: James Davis, Bernd Jähne, Andreas Kolb, Ramesh Raskar, and Christian Theobalt

Published in: Dagstuhl Reports, Volume 2, Issue 10 (2013)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12431 "Time-of-Flight Imaging: Algorithms, Sensors and Applications". The seminar brought together researchers with diverse background from both academia and industry to discuss various aspects of Time-of-Flight imaging and general depth sensors. The executive summary and abstracts of the talks given during the seminar as well as the outcome of several working groups on specific research topics are presented in this report.

Cite as

James Davis, Bernd Jähne, Andreas Kolb, Ramesh Raskar, and Christian Theobalt. Time-of-Flight Imaging: Algorithms, Sensors and Applications (Dagstuhl Seminar 12431). In Dagstuhl Reports, Volume 2, Issue 10, pp. 79-104, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Article{davis_et_al:DagRep.2.10.79,
  author =	{Davis, James and J\"{a}hne, Bernd and Kolb, Andreas and Raskar, Ramesh and Theobalt, Christian},
  title =	{{Time-of-Flight Imaging: Algorithms, Sensors and Applications (Dagstuhl Seminar 12431)}},
  pages =	{79--104},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{10},
  editor =	{Davis, James and J\"{a}hne, Bernd and Kolb, Andreas and Raskar, Ramesh and Theobalt, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.10.79},
  URN =		{urn:nbn:de:0030-drops-39044},
  doi =		{10.4230/DagRep.2.10.79},
  annote =	{Keywords: Time-of-Flight, Kinect^TM, depth sensor}
}
  • Refine by Author
  • 3 Doty, David
  • 2 Eftekhari, Mahsa
  • 1 Amir, Talley
  • 1 Aspnes, James
  • 1 Brefeld, Ulf
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Models of computation
  • 1 Computing methodologies → Computer vision
  • 1 Computing methodologies → Machine learning
  • 1 Mathematics of computing → Graph theory

  • Refine by Keyword
  • 1 DNA storage
  • 1 Kinect^TM
  • 1 Loosely-stabilizing
  • 1 Rainbow coloring
  • 1 Time-of-Flight
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2022
  • 1 2013
  • 1 2018
  • 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