4 Search Results for "Stauffer, Alexandre"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.4
Fast and Perfect Sampling of Subgraphs and Polymer Systems

Authors: Antonio Blanca, Sarah Cannon, and Will Perkins

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.
Cite as

Antonio Blanca, Sarah Cannon, and Will Perkins. Fast and Perfect Sampling of Subgraphs and Polymer Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blanca_et_al:LIPIcs.APPROX/RANDOM.2022.4,
  author =	{Blanca, Antonio and Cannon, Sarah and Perkins, Will},
  title =	{{Fast and Perfect Sampling of Subgraphs and Polymer Systems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.4},
  URN =		{urn:nbn:de:0030-drops-171261},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.4},
  annote =	{Keywords: Random Sampling, perfect sampling, graphlets, polymer models, spin systems, percolation}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.39
Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents

Authors: Peter Gracar and Alexandre Stauffer

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
We consider the problem of spread of information among mobile agents on the torus. The agents are initially distributed as a Poisson point process on the torus, and move as independent simple random walks. Two agents can share information whenever they are at the same vertex of the torus. We study the so-called flooding time: the amount of time it takes for information to be known by all agents. We establish a tight upper bound on the flooding time, and introduce a technique which we believe can be applicable to analyze other processes involving mobile agents.
Cite as

Peter Gracar and Alexandre Stauffer. Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gracar_et_al:LIPIcs.APPROX-RANDOM.2018.39,
  author =	{Gracar, Peter and Stauffer, Alexandre},
  title =	{{Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.39},
  URN =		{urn:nbn:de:0030-drops-94439},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.39},
  annote =	{Keywords: Lipschitz surface, spread of information, flooding time, moving agents}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.34
Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings

Authors: Sarah Cannon, David A. Levin, and Alexandre Stauffer

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
We give the first polynomial upper bound on the mixing time of the edge-flip Markov chain for unbiased dyadic tilings, resolving an open problem originally posed by Janson, Randall, and Spencer in 2002. A dyadic tiling of size n is a tiling of the unit square by n non-overlapping dyadic rectangles, each of area 1/n, where a dyadic rectangle is any rectangle that can be written in the form [a2^{-s}, (a+1)2^{-s}] x [b2^{-t}, (b+1)2^{-t}] for a,b,s,t nonnegative integers. The edge-flip Markov chain selects a random edge of the tiling and replaces it with its perpendicular bisector if doing so yields a valid dyadic tiling. Specifically, we show that the relaxation time of the edge-flip Markov chain for dyadic tilings is at most O(n^{4.09}), which implies that the mixing time is at most O(n^{5.09}). We complement this by showing that the relaxation time is at least Omega(n^{1.38}), improving upon the previously best lower bound of Omega(n*log n) coming from the diameter of the chain.
Cite as

Sarah Cannon, David A. Levin, and Alexandre Stauffer. Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cannon_et_al:LIPIcs.APPROX-RANDOM.2017.34,
  author =	{Cannon, Sarah and Levin, David A. and Stauffer, Alexandre},
  title =	{{Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{34:1--34:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.34},
  URN =		{urn:nbn:de:0030-drops-75830},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.34},
  annote =	{Keywords: Random dyadic tilings, spectral gap, rapid mixing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.187
Balls into bins via local search: cover time and maximum load

Authors: Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, and He Sun

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We study a natural process for allocating m balls into n bins that are organized as the vertices of an undirected graph G. Balls arrive one at a time. When a ball arrives, it first chooses a vertex u in G uniformly at random. Then the ball performs a local search in G starting from u until it reaches a vertex with local minimum load, where the ball is finally placed on. Then the next ball arrives and this procedure is repeated. For the case m=n, we give an upper bound for the maximum load on graphs with bounded degrees. We also propose the study of the cover time of this process, which is defined as the smallest m so that every bin has at least one ball allocated to it. We establish an upper bound for the cover time on graphs with bounded degrees. Our bounds for the maximum load and the cover time are tight when the graph is vertex transitive or sufficiently homogeneous. We also give upper bounds for the maximum load when m>=n.
Cite as

Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, and He Sun. Balls into bins via local search: cover time and maximum load. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 187-198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.STACS.2014.187,
  author =	{Bringmann, Karl and Sauerwald, Thomas and Stauffer, Alexandre and Sun, He},
  title =	{{Balls into bins via local search: cover time and maximum load}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{187--198},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.187},
  URN =		{urn:nbn:de:0030-drops-44570},
  doi =		{10.4230/LIPIcs.STACS.2014.187},
  annote =	{Keywords: Balls and Bins, Stochastic Process, Randomized Algorithm}
}
  • Refine by Author
  • 3 Stauffer, Alexandre
  • 2 Cannon, Sarah
  • 1 Blanca, Antonio
  • 1 Bringmann, Karl
  • 1 Gracar, Peter
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Probability and statistics
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Random walks and Markov chains
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 1 Balls and Bins
  • 1 Lipschitz surface
  • 1 Random Sampling
  • 1 Random dyadic tilings
  • 1 Randomized Algorithm
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2014
  • 1 2017
  • 1 2018
  • 1 2022

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