On polynomial approximations to AC

Classical approximation results show that any circuit of size and depth has an ‐error probabilistic polynomial over the reals of degree . We improve this upper bound to , which is much better for small values of . We then use this result to show that ‐wise independence fools circuits of size and depth up to error at most , improving on Tal's strengthening of Braverman's result that ‐wise independence suffices. To our knowledge, this is the first PRG construction for that achieves optimal dependence on the error . We also prove lower bounds on the best polynomial approximations to . We show that any polynomial approximating the function on bits to a small constant error must have degree at least . This result improves exponentially on a result of Meka, Nguyen, and Vu (Theory Comput. 2016).     

Weight distributions and weight hierarchies of two classes of binary linear codes

Linear codes with a few weights can be applied to communication, consumer electronics and data storage system. In addition, the weight hierarchy of a linear code has many applications such as on the type II wire-tap channel, dealing with t-resilient functions and trellis or branch complexity of linear codes and so on. In this paper, we present a formula for computing the weight hierarchies of linear codes constructed by the generalized method of defining sets. Then, we construct two classes of binary linear codes with a few weights and determine their weight distributions and weight hierarchies completely. Some codes of them can be used in secret sharing schemes.     

The numerical experiment in the study of polynomial quasisolutions of linear differential-difference equations

In this paper we consider the initial problem with an initial point for a scalar linear inhomogeneous differential-difference equation of neutral type. For polynomial coefficients in the equation we introduce a formal solution, representing a polynomial of a certain degree (“a polynomial quasisolution”); substituting it in the initial equation, one obtains a residual. The work is dedicated to the definition and the analysis (on the base of numerical experiments) of polynomial quasisolutions for the solutions of the initial problem under consideration.     

Banach空间中线性离散时间系统的一致多项式膨胀性

给出了Banach 空间中线性离散时间系统一致多项式膨胀性的概念,并讨论了其离散特征。借助Lyapunov函数给出了线性离散时间系统满足一致多项式膨胀的充要条件。所得结论将一致指数稳定性、指数膨胀性及多项式稳定性中的若干经典结论推广到了一致多项式膨胀性的情形。     

Commutativity of first‐order discrete‐time linear time‐varying systems

After introducing the concept of commutativity for continuous‐time linear time‐varying systems, the related literature and the results obtained so far are presented. For a simple introduction of the commutativity of discrete‐time linear time‐varying systems, the problem is formulated for first‐order systems. Finally, explicit necessary and sufficient conditions for the commutativity of first‐order discrete‐time linear time‐varying systems are derived, and their advantageous use in digital system design is illustrated, which are the main objectives of the paper. The results are verified by examples which include an application in amplitude modulation for digital telecommunication.     

The Polycyclic Monoids P n and the Thompson Groups V n,1

We construct what we call the strong orthogonal completion C _n of the polycyclic monoid P _n on n generators. The inverse monoid C _n is congruence free and its group of units is the Thompson group V _n,1. Copies of C _n can be constructed from partitions of sets into n blocks each block having the same cardinality as the underlying set.     

求解0-1线性整数规划问题的有界单纯形法

提出了一种求解0-1线性整数规划问题的有界单纯形法, 不仅通过数学论证, 讨论了该方法的合理性, 奠定了其数学理论基础, 而且通过求解无容量设施选址问题, 验证了该方法的可行性. 在此基础上, 就该有界单纯形法的不足和存在的问题, 给出了进一步改进的途径和手段.     

Deciding confluence of certain term rewriting systems in polynomial time

We present a characterization of confluence for term rewriting systems, which is then refined for special classes of rewriting systems. The refined characterization is used to obtain a polynomial time algorithm for deciding the confluence of ground term rewrite systems. The same approach also shows the decidability of confluence for shallow and linear term rewriting systems. The decision procedure has a polynomial time complexity under the assumption that the maximum arity of a function symbol in the signature is a constant.     

有界变量线性规划的基线算法

本文对有界变量线性规划的算法进行了研究，得到了一种解此问题的新算法。文中根据基线算法的算法原理，通过对BL表的旋转，在各变量满足界约束的条件下，使目标函数值不断增大，直至得到有界硬上界，从而得到问题的最优解。文中给出了有界变量线性规划基线算法的计算步骤，并给出了一个例子。与单纯形法相比，采用基线算法解有界变量线性规划操作更简单。迭代次数少，解题速度更快。     

Deterministic computation of the characteristic polynomial in the time of matrix multiplication

This paper describes an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. Our algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form, and relies on new subroutines for transforming shifted reduced matrices into shifted weak Popov matrices, and shifted weak Popov matrices into shifted Popov matrices.     

LU implementation of the modified minimal polynomial extrapolation method for solving linear and nonlinear systems

We give an efficient implementation of the modified minimalpolynomial extrapolation (MMPE) method for solving linear andnonlinear systems. We will show how to choose the auxiliaryvectors in the MMPE method such that the resulting approximationsare always defined. This new implementation, which is basedon an LU factorization with a pivoting strategy, is inexpensiveboth in time and storage as compared with other extrapolationmethods.     

A linear time algorithm for restricted bin packing and scheduling problems

In this paper we are concerned with the subproblem of bin packing, where the set of possible weights of elements is finite. In [5] it was mentioned that this problem could be solved by an exhaustive search procedure in polynomial time, but the degree of the polynomial is high and increases as the cardinality of the set of weights increases. However, we will show that a more careful analysis of the problem leads to a linear time algorithm. The impact of this result on task scheduling is discussed.     

Perfect foresight dynamics in games with linear incentives and time symmetry

This paper investigates absorption and global accessibility under perfect foresight dynamics in games with linear incentives. An action distribution in the society is absorbing if there is no equilibrium path escaping from the distribution, and globally accessible if, from every initial distribution, there exists an equilibrium path which converges to the distribution. Using time symmetry of the dynamics, we show that every absorbing strict Nash equilibrium, if it exists, is globally accessible under zero rate of time preference. With the additional assumption of supermodularity, we prove that there generically exists an absorbing strict Nash equilibrium. Relations with a global game and a reaction-diffusion model also become clear. The definition of absorption used in this paper is slightly different from the original one in Matsui and Matsuyama (1995). This difference is neglected in Sect. 1, and will be discussed in Sect. 2.2.     

Safe bounds in linear and mixed-integer linear programming

Current mixed-integer linear programming solvers are based on linear programming routines that use floating-point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. An example is given where many state-of-the-art MILP solvers fail. It is then shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in a branch-and-cut framework can guarantee that no solution is lost, at least for mixed-integer programs in which all variables can be bounded rigorously by bounds of reasonable size. Mathematics Subject Classification (2000):primary 90C11, secondary 65G20     

Small-time local controllability and continuity of the optimal time function for linear systems

For a finite-dimensional linear system, in which the control is restricted to belong to a completely arbitrary setJ, we give a simple necessary and sufficient condition for small-time local controllability from a pointp. The condition is equivalent to a characterization of the property that the Bellman function for the corresponding minimum-time optimal control problem is continuous atp.This work was partially supported by the National Science Foundation, Grant No. MCS-78-02442.     

Industrial petrochemical production planning and expansion: A multi-objective linear programming approach

This paper considers a strategic model planning for the petrochemical industry. It concerns with the expansion in a firm producing multiple products in several regions of a country. The expansion of the existing facilities and the new ones are considered. It also exists a large amount of interdependencies among the firm’s products, because the output of one particular plant can be used as an input to the production of another plant in the same or different regions and to satisfy the final demand. The decision makers involved in the planning process should identify several objectives. Then, multiple objective programming is used for making trade-offs among the economic and operational factors considered. To define the interval criteria weights into the model we utilized the Analytic Hierarchy Process to bring them closer to the decision makers preferences. This work was sponsored by the Institut National Polytechnique de Toulouse, France, when the author was Associate Professor at the Département Génie des Systèmes Industriels.