4 Search Results for "Fischer, Daniel"


Document
Improved Distributed Algorithms for Random Colorings

Authors: Charlie Carlson, Daniel Frishberg, and Eric Vigoda

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)


Abstract
Markov Chain Monte Carlo (MCMC) algorithms are a widely-used algorithmic tool for sampling from high-dimensional distributions, a notable example is the equilibirum distribution of graphical models. The Glauber dynamics, also known as the Gibbs sampler, is the simplest example of an MCMC algorithm; the transitions of the chain update the configuration at a randomly chosen coordinate at each step. Several works have studied distributed versions of the Glauber dynamics and we extend these efforts to a more general family of Markov chains. An important combinatorial problem in the study of MCMC algorithms is random colorings. Given a graph G of maximum degree Δ and an integer k ≥ Δ+1, the goal is to generate a random proper vertex k-coloring of G. Jerrum (1995) proved that the Glauber dynamics has O(nlog{n}) mixing time when k > 2Δ. Fischer and Ghaffari (2018), and independently Feng, Hayes, and Yin (2018), presented a parallel and distributed version of the Glauber dynamics which converges in O(log{n}) rounds for k > (2+ε)Δ for any ε > 0. We improve this result to k > (11/6-δ)Δ for a fixed δ > 0. This matches the state of the art for randomly sampling colorings of general graphs in the sequential setting. Whereas previous works focused on distributed variants of the Glauber dynamics, our work presents a parallel and distributed version of the more general flip dynamics presented by Vigoda (2000) (and refined by Chen, Delcourt, Moitra, Perarnau, and Postle (2019)), which recolors local maximal two-colored components in each step.

Cite as

Charlie Carlson, Daniel Frishberg, and Eric Vigoda. Improved Distributed Algorithms for Random Colorings. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{carlson_et_al:LIPIcs.OPODIS.2023.13,
  author =	{Carlson, Charlie and Frishberg, Daniel and Vigoda, Eric},
  title =	{{Improved Distributed Algorithms for Random Colorings}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.13},
  URN =		{urn:nbn:de:0030-drops-195030},
  doi =		{10.4230/LIPIcs.OPODIS.2023.13},
  annote =	{Keywords: Distributed Graph Algorithms, Local Algorithms, Coloring, Glauber Dynamics, Sampling, Markov Chains}
}
Document
Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays

Authors: Omri Ben-Eliezer, Simon Korman, and Daniel Reichman

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


Abstract
Analyzing multi-dimensional data is a fundamental problem in various areas of computer science. As the amount of data is often huge, it is desirable to obtain sublinear time algorithms to understand local properties of the data. We focus on the natural problem of testing pattern freeness: given a large d-dimensional array A and a fixed d-dimensional pattern P over a finite alphabet Gamma, we say that A is P-free if it does not contain a copy of the forbidden pattern P as a consecutive subarray. The distance of A to P-freeness is the fraction of the entries of A that need to be modified to make it P-free. For any epsilon > 0 and any large enough pattern P over any alphabet - other than a very small set of exceptional patterns - we design a tolerant tester that distinguishes between the case that the distance is at least epsilon and the case that the distance is at most a_d epsilon, with query complexity and running time c_d epsilon^{-1}, where a_d < 1 and c_d depend only on the dimension d. These testers only need to access uniformly random blocks of samples from the input A. To analyze the testers we establish several combinatorial results, including the following d-dimensional modification lemma, which might be of independent interest: For any large enough d-dimensional pattern P over any alphabet (excluding a small set of exceptional patterns for the binary case), and any d-dimensional array A containing a copy of P, one can delete this copy by modifying one of its locations without creating new P-copies in A. Our results address an open question of Fischer and Newman, who asked whether there exist efficient testers for properties related to tight substructures in multi-dimensional structured data.

Cite as

Omri Ben-Eliezer, Simon Korman, and Daniel Reichman. Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ICALP.2017.9,
  author =	{Ben-Eliezer, Omri and Korman, Simon and Reichman, Daniel},
  title =	{{Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{9:1--9: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.9},
  URN =		{urn:nbn:de:0030-drops-74427},
  doi =		{10.4230/LIPIcs.ICALP.2017.9},
  annote =	{Keywords: Property testing, Sublinear algorithms, Pattern matching}
}
Document
A Mobility Model for the Realistic Simulation of Social Context

Authors: Daniel Fischer

Published in: OASIcs, Volume 17, 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)


Abstract
Simulation is a fundamental means for evaluating mobile applications based on ad-hoc networks. In recent years, the new breed of social mobility models (SMMs) has risen. Contrary to most classical mobility models, SMMs model the social aspects of human mobility, i.e. which users meet, when and how often. Such information is indispensable for the simulation of a wide range of socially-aware communication protocols mostly based on delay-tolerant networks, including opportunistic ad-hoc routing and data dissemination systems. Each SMM needs a model of the relations between a set of relevant people (called social network model -- SNM) in order to simulate their mobility. Existing SMMs lack flexibility since each of them is implicitly restricted to a specific, simplifying SNM. We present GeSoMo (General Social Mobility Model), a new SMM that separates the core mobility model from the structural description of the social network underlying the simulation. This simple and elegant design principle gives GeSoMo generalizing power: Arbitrary existing and future SNMs can be used without changing GeSoMo itself. Our evaluation results show that GeSoMo produces simulations that are coherent with a broad range of empirical data describing real-world human social behavior and mobility.

Cite as

Daniel Fischer. A Mobility Model for the Realistic Simulation of Social Context. In 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011). Open Access Series in Informatics (OASIcs), Volume 17, pp. 215-220, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{fischer:OASIcs.KiVS.2011.215,
  author =	{Fischer, Daniel},
  title =	{{A Mobility Model for the Realistic Simulation of Social Context}},
  booktitle =	{17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)},
  pages =	{215--220},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-27-9},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{17},
  editor =	{Luttenberger, Norbert and Peters, Hagen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.KiVS.2011.215},
  URN =		{urn:nbn:de:0030-drops-29772},
  doi =		{10.4230/OASIcs.KiVS.2011.215},
  annote =	{Keywords: Mobility Model, Simulation, ad-hoc networks}
}
Document
Satisfiability of Acyclic and Almost Acyclic CNF Formulas

Authors: Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)


Abstract
We study the propositional satisfiability problem (SAT) on classes of CNF formulas (formulas in Conjunctive Normal Form) that obey certain structural restrictions in terms of their hypergraph structure, by associating to a CNF formula the hypergraph obtained by ignoring negations and considering clauses as hyperedges on variables. We show that satisfiability of CNF formulas with so-called ``beta-acyclic hypergraphs'' can be decided in polynomial time. We also study the parameterized complexity of SAT for ``almost'' beta-acyclic instances, using as parameter the formula's distance from being beta-acyclic. As distance we use the size of smallest strong backdoor sets and the beta-hypertree width. As a by-product we obtain the W[1]-hardness of SAT parameterized by the (undirected) clique-width of the incidence graph, which disproves a conjecture by Fischer, Makowsky, and Ravve (Discr. Appl. Math. 156, 2008).

Cite as

Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Satisfiability of Acyclic and Almost Acyclic CNF Formulas. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 84-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{ordyniak_et_al:LIPIcs.FSTTCS.2010.84,
  author =	{Ordyniak, Sebastian and Paulusma, Daniel and Szeider, Stefan},
  title =	{{Satisfiability of Acyclic and Almost Acyclic CNF Formulas}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{84--95},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.84},
  URN =		{urn:nbn:de:0030-drops-28556},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.84},
  annote =	{Keywords: Satisfiability, chordal bipartite graphs, beta-acyclic hypergraphs, backdoor sets, parameterized complexity}
}
  • Refine by Author
  • 1 Ben-Eliezer, Omri
  • 1 Carlson, Charlie
  • 1 Fischer, Daniel
  • 1 Frishberg, Daniel
  • 1 Korman, Simon
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Random walks and Markov chains

  • Refine by Keyword
  • 1 Coloring
  • 1 Distributed Graph Algorithms
  • 1 Glauber Dynamics
  • 1 Local Algorithms
  • 1 Markov Chains
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2010
  • 1 2011
  • 1 2017
  • 1 2024

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