Dear all,
the DFG Research Unit ADYN invites you to their next online seminar
session on Zoom:
*Monday, February 3rd, 17:00 CET*.
Link:
https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1
Meeting-ID: 688 3715 6442
Kenncode: 593098
The following talks will be given:
(1) "A New Look on an Old Counter Example of Doeblin Measures" by Noam
Berger Steiger (Technical University of Munich)
(2) "Noisy Linear Group Testing: Exact Thresholds and Efficient
Algorithms" by Olga Scheftelowitsch (TU Dortmund University)
Abstracts:
(1) We consider an example from 2017 of a Doeblin function that admits
two extremal Doeblin measures, and see that's variants thereof provide
counter examples to a number of conjectures, in particular we get a
non-mixing Doeblin measure, and Doeblin functions that admit Doeblin
measures of different entropies. I will start by giving a thorough
introduction to the topic of Doeblin functions and measures. Based on an
old work with Hoffman and Sidoravicius, and a new work with Conache,
Johansson and Öberg.
(2) In group testing, the task is to identify defective items by testing
groups of them together using as few tests as possible. We consider the
setting where each item is defective with a constant probability α,
independent of all other items. In the (over-)idealized noiseless
setting, tests are positive exactly if any of the tested items are
defective. We study a more realistic model in which observed test
results are subject to noise, i.e., tests can display false positive or
false negative results with constant positive probabilities. We
determine precise constants c such that cnlogn tests are required to
recover the infection status of every individual for both adaptive and
non-adaptive group testing: in the former, the selection of groups to
test can depend on previously observed test results, whereas it cannot
in the latter. Additionally, for both settings, we provide efficient
algorithms that identify all defective items with the optimal amount of
tests with high probability. Thus, we completely solve the problem of
binary noisy group testing in the studied setting.
For more information on ADYN and the seminar series, visit our website
using the link https://adyn.informatik.rwth-aachen.de/ .
Best,
Tim
Dear all,
happy new year to everyone! The DFG Research Unit ADYN invites you to
their next online seminar session on Zoom:
*Monday, January 13th, 17:00 CET*.
Link:
https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1
Meeting-ID: 688 3715 6442
Kenncode: 593098
The following talks will be given:
(1) "Chromatic Number of Randomly Augmented Graphs" by Anand Srivastav
(Kiel University)
(2) "Insights into (k, ρ)-Shortcutting Algorithms" by Alexander
Leonhardt (Goethe University Frankfurt)
Abstracts:
(1) An extension of the Erdős-Renyi random graph model $G_{n,p}$ is the
model of perturbed graphs introduced by Bohman, Frieze and Martin
(2003). This is a special case of the randomly augmented graphs studied
in this paper. An augmented graph is the union of a deterministic host
graph and a random graph. Among the first problems in perturbed graphs
has been the question how many random edges are needed to ensure
Hamiltonicity of the graph. This question was answered in the paper by
Bohman, Frieze and Martin. The host graph is often chosen to be a dense
graph. In recent years several papers on combinatorial functions of
perturbed graphs were published, e.g. on the emergence of powers of
Hamiltonian cycles (Dudek, Reiher, Ruciński, Schacht 2020), the
properties of Positional Games played on perturbed graphs (Clemens,
Hamann, Mogge, Parczyk, 2020) and the emergence of multiple invariants
e.g. fixed clique size (Bohman, Frieze, Krivelevich, Martin, 2004).
In this paper we study the chromatic number of randomly augmented
graphs. We concentrate on a host graph $H$ with chromatic number $o(n)$,
augmented by a $G_{n,p}$ with $n^{-\frac{1}{3} + \delta}\leq p(n) \leq
1-\delta$ for some $\delta \in (0,1)$. We denote such a graph by
$\pert_{H,p}$. Our main result is an upper bound for the chromatic
number of such a randomly augmented graph $\pert_{H,p}: we show that for
any $\epsilon>0$ there is a $n(\epsilon) \in \N$ such that for $n \geq
n(\epsilon)$ with high probability $\chromaticOf{\pert_{H,p}} \leq
(1+o(1)) \cdot \frac{n \log(b)}{2 (\log(n) - \log(\chromaticOf{H}))}$.
This result collapses to the famous theorem of Bollobás (1988), when $H$
is the empty host graph, thus our result can be regarded as a
generalization of the latter. Our proof is not constructive. To give the
reader an impression of a coloring strategy, we give a constructive
proof of the upper bound for the chromatic number of $\pert_{H,p}$ where
the chromatic number of the host grah is at most
$\frac{n}{\log(n)^{\alpha}}$ where $\alpha>\frac{1}{2}$.
(2) A graph is called a (k, ρ)-graph iff every node can reach ρ of its
nearest neighbors in at most k hops. This property has proven useful in
the analysis and design of parallel shortest-path algorithms [Blelloch
et al., 2016; Dong et al., 2021]. Any graph can be transformed into a
(k, ρ)-graph by adding shortcuts. Formally, the
(k,ρ)-Minimum-Shortcut-Problem (kρ-MSP) asks to find an appropriate
shortcut set of minimal cardinality. We show that kρ-MSP is NP-complete
in the practical regime of k ≥ 3 and ρ = Θ(n^ε) for ε > 0. With a
related construction, we bound the approximation factor of known kρ-MSP
heuristics [Blelloch et al., 2016] from below and propose algorithmic
countermeasures improving the approximation quality. Further, we
describe an integer linear problem (ILP) that optimally solves kρ-MSP.
Finally, we compare the practical performance and quality of all
algorithms empirically.
This is joint work with Manuel Penschuck and Ulrich Meyer.
For more information on ADYN and the seminar series, visit our website
using the link https://adyn.informatik.rwth-aachen.de/ .
Best,
Tim
