标题： 标量可解性网络计算问题与可表示的拟阵 显示英文标题

标题： Scalar Solvability of Network Computation Problems and Representable Matroids

摘要： 我们考虑以下\textit{网络计算问题}。 在无环网络中，有多个源节点，每个生成多个消息，有多个汇节点，每个需求源消息的函数。 网络编码问题对应于每个需求函数等于某个源消息的情况，即每个汇节点需求某个源消息。 网络编码问题与拟阵之间的联系已被广泛研究。 在本工作中，我们建立了网络计算问题与可表示拟阵之间的关系。 我们证明，当汇节点需求源消息的线性函数时，网络计算问题存在标量线性解当且仅当它相对于满足由网络计算问题决定的某些约束的可表示拟阵是拟阵的。 接下来，我们得到网络计算问题与功能依赖关系（FD-关系）之间的联系，并表明FD-关系可以用来表征具有任意（不一定是线性）函数需求的网络计算问题以及非线性网络编码。 显示英文摘要

摘要： We consider the following \textit{network computation problem}. In an acyclic network, there are multiple source nodes, each generating multiple messages, and there are multiple sink nodes, each demanding a function of the source messages. The network coding problem corresponds to the case in which every demand function is equal to some source message, i.e., each sink demands some source message. Connections between network coding problems and matroids have been well studied. In this work, we establish a relation between network computation problems and representable matroids. We show that a network computation problem in which the sinks demand linear functions of source messages admits a scalar linear solution if and only if it is matroidal with respect to a representable matroid whose representation fulfills certain constraints dictated by the network computation problem. Next, we obtain a connection between network computation problems and functional dependency relations (FD-relations) and show that FD-relations can be used to characterize network computation problem with arbitrary (not necessarily linear) function demands as well as nonlinear network codes.