Found 2 Possible Name Variants:

Document

**Published in:** Dagstuhl Reports, Volume 1, Issue 6 (2011)

The Dagstuhl Seminar on ``Design and Analysis of Randomized and Approximation Algorithms'' (Seminar 11241) was held at Schloss Dagstuhl between June 13--17, 2011.
There were 26 regular talks and several informal and open problem session contributions presented during this seminar. Abstracts of the presentations have been put together in this seminar proceedings document together with some links to extended abstracts and full papers.

Martin Dyer, Uriel Feige, Alan M. Frieze, and Marek Karpinski. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). In Dagstuhl Reports, Volume 1, Issue 6, pp. 24-53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{dyer_et_al:DagRep.1.6.24, author = {Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek}, title = {{Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241)}}, pages = {24--53}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2011}, volume = {1}, number = {6}, editor = {Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.6.24}, URN = {urn:nbn:de:0030-drops-32585}, doi = {10.4230/DagRep.1.6.24}, annote = {Keywords: Randomized Algorithms, Approximation Algorithms, Probabilistically Checkable Proofs, Approximation Hardness, Optimization Problems, Counting Problems, Streaming Algorithms, Random Graphs, Hypergraphs, Probabilistic Method, Networks, Linear Programs, Semidefinite Programs} }

Document

RANDOM

**Published in:** LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Let Omega_q=Omega_q(H) denote the set of proper [q]-colorings of the hypergraph H. Let Gamma_q be the graph with vertex set Omega_q where two vertices are adjacent iff the corresponding colorings differ in exactly one vertex. We show that if H=H_{n,m;k}, k >= 2, the random k-uniform hypergraph with V=[n] and m=dn/k hyperedges then w.h.p. Gamma_q is connected if d is sufficiently large and q >~ (d/log d)^{1/(k-1)}. This is optimal to the first order in d. Furthermore, with a few more colors, we find that the diameter of Gamma_q is O(n) w.h.p, where the hidden constant depends on d. So, with this choice of d,q, the natural Glauber Dynamics Markov Chain on Omega_q is ergodic w.h.p.

Michael Anastos and Alan Frieze. On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 36:1-36:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{anastos_et_al:LIPIcs.APPROX-RANDOM.2019.36, author = {Anastos, Michael and Frieze, Alan}, title = {{On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {36:1--36:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.36}, URN = {urn:nbn:de:0030-drops-112513}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.36}, annote = {Keywords: Random Graphs, Colorings, Ergodicity} }

Document

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

We study a random walk that prefers to use unvisited edges in the context of random cubic graphs, i.e., graphs chosen uniformly at random from the set of 3-regular graphs. We establish asymptotically correct estimates for the vertex and edge cover times, these being n log n and 3/2 n log n respectively.

Colin Cooper, Alan Frieze, and Tony Johansson. The Cover Time of a Biased Random Walk on a Random Cubic Graph. 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. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.AofA.2018.16, author = {Cooper, Colin and Frieze, Alan and Johansson, Tony}, title = {{The Cover Time of a Biased Random Walk on a Random Cubic Graph}}, booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)}, pages = {16:1--16:12}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.16}, URN = {urn:nbn:de:0030-drops-89097}, doi = {10.4230/LIPIcs.AofA.2018.16}, annote = {Keywords: Random walk, random regular graph, cover time} }

Document

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

We consider the problem of traveling among random points in Euclidean space, when only a random fraction of the pairs are joined by traversable connections. In particular, we show a threshold for a pair of points to be connected by a geodesic of length arbitrarily close to their Euclidean distance, and analyze the minimum length Traveling Salesperson Tour, extending the Beardwood-Halton-Hammersley theorem to this setting.

Alan Frieze and Wesley Pegden. Traveling in Randomly Embedded Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 45:1-45:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{frieze_et_al:LIPIcs.APPROX-RANDOM.2017.45, author = {Frieze, Alan and Pegden, Wesley}, title = {{Traveling in Randomly Embedded Random Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {45:1--45:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.45}, URN = {urn:nbn:de:0030-drops-75949}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.45}, annote = {Keywords: Traveling Salesman, Euclidean, Shortest Path} }

Document

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

We consider an asynchronous voting process on graphs which we call discordant voting, and which can be described as follows. Initially each vertex holds one of two opinions, red or blue say. Neighbouring vertices with different opinions interact pairwise. After an interaction both vertices have the same colour. The quantity of interest is T, the time to reach consensus, i.e. the number of interactions needed for all vertices have the same colour.
An edge whose endpoint colours differ (i.e. one vertex is coloured red and the other one blue) is said to be discordant. A vertex is discordant if its is incident with a discordant edge. In discordant voting, all interactions are based on discordant edges. Because the voting process is asynchronous there are several ways to update the colours of the interacting vertices.
- Push: Pick a random discordant vertex and push its colour to a random discordant neighbour.
- Pull: Pick a random discordant vertex and pull the colour of a random discordant neighbour.
- Oblivious: Pick a random endpoint of a random discordant edge and push the colour to the other end point.
We show that ET, the expected time to reach consensus, depends strongly on the underlying graph and the update rule. For connected graphs on n vertices, and an initial half red, half blue colouring the following hold. For oblivious voting, ET = (n^2)/4 independent of the underlying graph. For the complete graph Kn, the push protocol has ET = Theta(n*log(n)), whereas the pull protocol has ET = Theta(2^n). For the cycle C_n all three protocols have ET = Theta(n^2). For the star graph however, the pull protocol has ET = O(n^2), whereas the push protocol is slower with ET = Theta(n^2*log(n)).
The wide variation in ET for the pull protocol is to be contrasted with the well known model of synchronous pull voting, for which ET = O(n) on many classes of expanders.

Colin Cooper, Martin Dyer, Alan Frieze, and Nicolás Rivera. Discordant Voting Processes on Finite Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 145:1-145:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.ICALP.2016.145, author = {Cooper, Colin and Dyer, Martin and Frieze, Alan and Rivera, Nicol\'{a}s}, title = {{Discordant Voting Processes on Finite Graphs}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {145:1--145:13}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.145}, URN = {urn:nbn:de:0030-drops-62898}, doi = {10.4230/LIPIcs.ICALP.2016.145}, annote = {Keywords: Distributed consensus, Voter model, Interacting particles, Randomized algorithm} }

Document

**Published in:** LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

We study the problem of finding a large planted clique in the random graph
$G_{n,1/2}$.
We reduce the problem to that of maximising a three dimensional tensor
over the unit ball
in $n$ dimensions. This latter problem has not been well studied and so we
hope that
this reduction will eventually lead to an improved solution to the planted
clique problem.

Alan Frieze and Ravi Kannan. A new approach to the planted clique problem. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 187-198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{frieze_et_al:LIPIcs.FSTTCS.2008.1752, author = {Frieze, Alan and Kannan, Ravi}, title = {{A new approach to the planted clique problem}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {187--198}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-08-8}, ISSN = {1868-8969}, year = {2008}, volume = {2}, editor = {Hariharan, Ramesh and Mukund, Madhavan and Vinay, V}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1752}, URN = {urn:nbn:de:0030-drops-17521}, doi = {10.4230/LIPIcs.FSTTCS.2008.1752}, annote = {Keywords: Planted Clique, Tensor, Random Graph} }