计算复杂度学术速递[1.10]
Update！H5支持摘要折叠，体验更佳！点击阅读原文访问arxivdaily.com，涵盖CS|物理|数学|经济|统计|金融|生物|电气领域，更有搜索、收藏等功能！
cs.CC计算复杂度，共计2篇
【1】 Tight Fine-Grained Bounds for Direct Access on Join Queries
标题：连接查询直接访问的紧致细粒度界限
链接：https://arxiv.org/abs/2201.02401
摘要：We consider the task of lexicographic direct access to query answers. That
is, we want to simulate an array containing the answers of a join query sorted
in a lexicographic order chosen by the user. A recent dichotomy showed for
which queries and orders this task can be done in polylogarithmic access time
after quasilinear preprocessing, but this dichotomy does not tell us how much
time is required in the cases classified as hard. We determine the
preprocessing time needed to achieve polylogarithmic access time for all
self-join free queries and all lexicographical orders. To this end, we propose
a decomposition-based general algorithm for direct access on join queries. We
then explore its optimality by proving lower bounds for the preprocessing time
based on the hardness of a certain online Set-Disjointness problem, which shows
that our algorithm's bounds are tight for all lexicographic orders on self-join
free queries. Then, we prove the hardness of Set-Disjointness based on the
Zero-Clique Conjecture which is an established conjecture from fine-grained
complexity theory. We also show that similar techniques can be used to prove
that, for enumerating answers to Loomis-Whitney joins, it is not possible to
significantly improve upon trivially computing all answers at preprocessing.
This, in turn, gives further evidence (based on the Zero-Clique Conjecture) to
the enumeration hardness of self-join free cyclic joins with respect to linear
preprocessing and constant delay.
【2】 Fixation Maximization in the Positional Moran Process
标题：位置性Moran过程中的注视最大化
链接：https://arxiv.org/abs/2201.02248
备注：11 pages, 6 figures, to appear at AAAI 2022
摘要：The Moran process is a classic stochastic process that models invasion
dynamics on graphs. A single "mutant" (e.g., a new opinion, strain, social
trait etc.) invades a population of residents spread over the nodes of a graph.
The mutant fitness advantage $\delta\geq 0$ determines how aggressively mutants
propagate to their neighbors. The quantity of interest is the fixation
probability, i.e., the probability that the initial mutant eventually takes
over the whole population. However, in realistic settings, the invading mutant
has an advantage only in certain locations. E.g., a bacterial mutation allowing
for lactose metabolism only confers an advantage on places where dairy products
are present. In this paper we introduce the positional Moran process, a natural
generalization in which the mutant fitness advantage is only realized on
specific nodes called active nodes. The associated optimization problem is
fixation maximization: given a budget $k$, choose a set of $k$ active nodes
that maximize the fixation probability of the invading mutant. We show that the
problem is NP-hard, while the optimization function is not submodular, thus
indicating strong computational hardness. Then we focus on two natural limits.
In the limit of $\delta\to\infty$ (strong selection), although the problem
remains NP-hard, the optimization function becomes submodular and thus admits a
constant-factor approximation using a simple greedy algorithm. In the limit of
$\delta\to 0$ (weak selection), we show that in $O(m^\omega)$ time we can
obtain a tight approximation, where $m$ is the number of edges and $\omega$ is
the matrix-multiplication exponent. Finally, we present an experimental
evaluation of the new algorithms together with some proposed heuristics.
机器翻译，仅供参考
点击“阅读原文”获取带摘要的学术速递