Given a finite alphabet $A$ and a binary relation $\tau\subseteq A^*\times
A^*$, a set $X$ is $\tau$-{\it independent} if $ \tau(X)\cap X=\emptyset$.
Given a quasi-metric $d$ over $A^*$ (in the meaning of \cite{W31}) and $k\ge
1$, we associate the relation $\tau_{d,k}$ defined by $(x,y)\in\tau_{d,k}$ if,
and only if, $d(x,y)\le k$ \cite{CP02}.In the spirit of \cite{JK97,N21}, the
error detection-correction capability of variable-length codes can be expressed
in term of conditions over $\tau_{d,k}$. With respect to the prefix metric, the
factor one, and every quasi-metric associated to (anti-)automorphisms of the
free monoid, we examine whether those conditions are decidable for a given
regular code.

研究了与自动机同构相关的几种赋范情况下，对于给定的正则码，能否判断基于 $\tau_{d,k}$ 的条件的变长编码的错误检测和纠正能力的问题。

变长编码与误差检测领域的交叉

When Variable-Length Codes Meet the Field of Error Detection

Let $i_t(G)$ be the number of independent sets of size $t$ in a graph $G$.
Engbers and Galvin asked how large $i_t(G)$ could be in graphs with minimum
degree at least $\delta$. They further conjectured that when $n\geq 2\delta$
and $t\geq 3$, $i_t(G)$ is maximized by the complete bipartite graph
$K_{\delta, n-\delta}$. This conjecture has drawn the attention of many
researchers recently. In this short note, we prove this conjecture.

研究独立集的数量及其最大化问题，通过证明假设得出其在最小度至少为 δ 的完全二分图中实现最大化。

最大化固定大小独立集的数量

Maximizing the number of independent sets of a fixed size

We study the problem of finding a maximum matching in a graph given by an
input stream listing its edges in some arbitrary order, where the quantity to
be maximized is given by a monotone submodular function on subsets of edges.
This problem, which we call maximum submodular-function matching (MSM), is a
natural generalization of maximum weight matching (MWM), which is in turn a
generalization of maximum cardinality matching (MCM). We give two incomparable
algorithms for this problem with space usage falling in the semi-streaming
range---they store only $O(n)$ edges, using $O(n\log n)$ working memory---that
achieve approximation ratios of $7.75$ in a single pass and $(3+\epsilon)$ in
$O(\epsilon^{-3})$ passes respectively. The operations of these algorithms
mimic those of Zelke's and McGregor's respective algorithms for MWM; the
novelty lies in the analysis for the MSM setting. In fact we identify a general
framework for MWM algorithms that allows this kind of adaptation to the broader
setting of MSM.
In the sequel, we give generalizations of these results where the
maximization is over "independent sets" in a very general sense. This
generalization captures hypermatchings in hypergraphs as well as independence
in the intersection of multiple matroids.

本文研究了最大子模函数匹配问题，给出了两种空间复杂度均为 O (nlogn) 的半流算法，并探讨了最大加权匹配和多重矩阵交叉的相似性，以求得更普适的解决方案。

模模块极值相遇流式计算：匹配，拟阵等

Submodular Maximization Meets Streaming: Matchings, Matroids, and More

Local algorithms on graphs are algorithms that run in parallel on the nodes
of a graph to compute some global structural feature of the graph. Such
algorithms use only local information available at nodes to determine local
aspects of the global structure, while also potentially using some randomness.
Recent research has shown that such algorithms show significant promise in
computing structures like large independent sets in graphs locally. Indeed the
promise led to a conjecture by Hatami, \Lovasz and Szegedy
\cite{HatamiLovaszSzegedy} that local algorithms may be able to compute maximum
independent sets in (sparse) random $d$-regular graphs. In this paper we refute
this conjecture and show that every independent set produced by local
algorithms is multiplicative factor $1/2+1/(2\sqrt{2})$ smaller than the
largest, asymptotically as $d\rightarrow\infty$.
Our result is based on an important clustering phenomena predicted first in
the literature on spin glasses, and recently proved rigorously for a variety of
constraint satisfaction problems on random graphs. Such properties suggest that
the geometry of the solution space can be quite intricate. The specific
clustering property, that we prove and apply in this paper shows that typically
every two large independent sets in a random graph either have a significant
intersection, or have a nearly empty intersection. As a result, large
independent sets are clustered according to the proximity to each other. While
the clustering property was postulated earlier as an obstruction for the
success of local algorithms, such as for example, the Belief Propagation
algorithm, our result is the first one where the clustering property is used to
formally prove limits on local algorithms.

本文研究了关于在图上的局部算法。我们证明了局部算法产生的每个独立集都比最大集合要小，而且通过聚类属性，我们强调了在随机图上的局部算法存在局限性。