Subword complexity of the Fibonacci–Thue–Morse sequence: The proof of Dekking’s conjecture

Recently F. M. Dekking conjectured the form of the subword complexity function for the Fibonacci–Thue–Morse sequence. In this note we prove his conjecture by purely computational means, using the free software Walnut.     

相对性区域创新指数与经济周期挖掘

提出了一类新的相对性区域创新指数,并采用世界专利申请数据对其进行了具体计算.基于区域创新同经济发展水平之间的超线性关系,该指数消除了经济发展水平对创新能力的影响,可以实现对不同发展水平的经济体之间进行有效的创新能力横纵对比.该创新指数尽管极其简单,却揭示出一系列迥异于传统认知的现象,例如中国大陆地区的技术创新能力在1980年代就已经位居世界前列.采用该指数,不但可以在较高水平上解释世界各国的经济增长,还发现它同经济增长率之间的相关性存在一个20年的经济周期.这些结果显示,该指数作为一个单一性指标,以极小的数据依赖就实现了较高程度的解释性,不但重新定位了世界各经济体的创新能力,对深入理解创新同经济发展之间的关系提供了新的角度,而且暗示着这类相对性经济指标的发展潜力与应用空间.     

Potts models with magnetic field: Arithmetic,geometry, and computation

We give a sheaf theoretic interpretation of Potts models with external magnetic field, in terms of constructible sheaves and their Euler characteristics. We show that the polynomial countability question for the hypersurfaces defined by the vanishing of the partition function is affected by changes in the magnetic field: elementary examples suffice to see non-polynomially countable cases that become polynomially countable after a perturbation of the magnetic field. The same recursive formula for the Grothendieck classes, under edge-doubling operations, holds as in the case without magnetic field, but the closed formulae for specific examples like banana graphs differ in the presence of magnetic field. We give examples of computation of the Euler characteristic with compact support, for the set of real zeros, and find a similar exponential growth with the size of the graph. This can be viewed as a measure of topological and algorithmic complexity. We also consider the computational complexity question for evaluations of the polynomial, and show both tractable and NP-hard examples, using dynamic programming.     

Proportional fair scheduling using water-filling technique for SC-FDMA based D2D communication

The resource allocation in SC-FDMA is constrained by the condition that multiple subchannels should be allocated to a single user only if they are adjacent. Therefore, the scheduling scheme of a D2D-cellular system that uses SC-FDMA must also conform to the so-called adjacency constraint. This paper proposes a heuristic algorithm with low computational complexity that applies proportional fair (PF) scheduling in the D2D-cellular system. The proposed algorithm consists of two main phases: (i) subchannel allocation and (ii) adjustment of data rates, which are executed for both CUEs and DUEs. In the subchannel allocation phase for CUEs (or D2D pairs), the users’ data rates are maximized via optimal power allocation to frequency-contiguous subchannels. In the second phase, a PF scheduling problem is solved to decide the modulation and coding scheme (MCS) of both CUEs and D2D pairs. Both phases of the proposed algorithm benefit from the Water-Filling (WF) technique. The simulation results suggest that the proposed scheme performs similar to optimal PF scheduling from the perspective of users’ data rate and their logarithmic sum. An additional benefit of the proposed scheme is its low computational overhead.     

广义线性多乘积问题的完全多项式时间近似算法

本文针对广义线性多乘积极小化问题,通过一系列的线性规划问题的解提出一种求其全局最优解的完全多项式时间近似算法,并给出该算法的计算复杂性,且数值算例验证该算法是可行的.     

A Note on normalizations of orbit closures

We give a negative answer to a question by J. M. Landsberg on the nature of normalizations of orbit closures. A counterexample originates from the study of complex, ternary, cubic forms.     

Tropical differential equations

Tropical differential equations are introduced and an algorithm is designed which tests solvability of a system of tropical linear differential equations within the complexity polynomial in the size of the system and in the absolute values of its coefficients. Moreover, we show that there exists a minimal solution, and the algorithm constructs it (in case of solvability). This extends a similar complexity bound established for tropical linear systems. In case of tropical linear differential systems in one variable a polynomial complexity algorithm for testing its solvability is designed.We prove also that the problem of solvability of a system of tropical non-linear differential equations in one variable is NP-hard, and this problem for arbitrary number of variables belongs to NP. Similar to tropical algebraic equations, a tropical differential equation expresses the (necessary) condition on the dominant term in the issue of solvability of a differential equation in power series.