Fundamenta Informaticae - Volume 177, issue 2

Authors: Berghammer, Rudolf | Schnoor, Henning | Winter, Michael

Article Type: Research Article

Abstract: Finite topological spaces and their dimensions have many applications in computer science, e.g., in digital topology, computer graphics and the analysis and synthesis of digital images. Georgiou et. al. [11] provided a polynomial algorithm for computing the covering dimension dim (X ; 𝒯 ) of a finite topological space (X; 𝒯 ). In addition, they asked whether algorithms of the same complexity for computing the small inductive dimension ind (X ; 𝒯 ) and the large inductive dimension Ind (X ; 𝒯 ) can be developed. The first problem was solved in a previous paper [4]. Using results of the …that paper, we also solve the second problem in this paper. We present a polynomial algorithm for Ind (X ; 𝒯 ), so that there are now efficient algorithms for the three most important notions of a dimension in topology. Our solution reduces the computation of Ind (X ; 𝒯 ), where the specialisation pre-order of (X ; 𝒯 ) is taken as input, to the computation of the maximal height of a specific class of directed binary trees within the partially ordered set. For the latter an efficient algorithm is presented that is based on order- and graph-theoretic ideas. Also refinements and variants of the algorithm are discussed. Show more

DOI: 10.3233/FI-2020-1981

Citation: Fundamenta Informaticae, vol. 177, no. 2, pp. 95-113, 2020

Authors: Cho, Gook Hwa | Lim, Seongan | Lee, Hyang-Sook

Article Type: Research Article

Abstract: In LATTE, a lattice based hierarchical identity-based encryption (HIBE) scheme, each hierarchical level user delegates a trapdoor basis to the next level by solving a generalized NTRU equation of level ℓ ≥ 3. For ℓ = 2, Howgrave-Graham, Pipher, Silverman, and Whyte presented an algorithm using resultant and Pornin and Prest presented an algorithm using a field norm with complexity analysis. Even though their ideas of solving NTRU equations can be conceptually extended for ℓ ≥ 3, no explicit algorithmic extensions with the storage analysis are known so far. In this paper, we interpret the generalized NTRU equation as the …determinant of a matrix. By using the mathematical properties of the determinant, we show that how to construct algorithms for solving the generalized NTRU equation either using resultant or a field norm for any ℓ ≥ 3. We also obtain an upper bound of the size of solutions by using the properties of the determinant. From our analysis, the storage requirement of the algorithm using resultant is O (ℓ2 n 2 logB ) and that of the algorithm using a field norm is O (ℓ2 n logB ), where B is an upper bound of the coefficients of the input polynomials of the generalized NTRU equations. We present examples of our algorithms for ℓ = 3 and the average storage requirements for ℓ = 3; 4. Show more

Keywords: NTRU, LATTE, hierarchical identity-based encryption

DOI: 10.3233/FI-2020-1982

Citation: Fundamenta Informaticae, vol. 177, no. 2, pp. 115-139, 2020

Authors: Kheirfam, Behrouz

Article Type: Research Article

Abstract: In this paper, we propose a Mizuno-Todd-Ye type predictor-corrector infeasible interior-point method for linear optimization based on a wide neighborhood of the central path. According to Ai-Zhang’s original idea, we use two directions of distinct and orthogonal corresponding to the negative and positive parts of the right side vector of the centering equation of the central path. In the predictor stage, the step size along the corresponded infeasible directions to the negative part is chosen. In the corrector stage by modifying the positive directions system a full-Newton step is removed. We show that, in addition to the predictor step, our …method reduces the duality gap in the corrector step and this can be a prominent feature of our method. We prove that the iteration complexity of the new algorithm is 𝒪 (n log ɛ −1 ), which coincides with the best known complexity result for infeasible interior-point methods, where ɛ > 0 is the required precision. Due to the positive direction new system, we improve the theoretical complexity bound for this kind of infeasible interior-point method [1] by a factor of n . Numerical results are also provided to demonstrate the performance of the proposed algorithm. Show more

Keywords: Predictor-corrector methods, interior-point methods, wide neighborhood, polynomial complexity

DOI: 10.3233/FI-2020-1983

Citation: Fundamenta Informaticae, vol. 177, no. 2, pp. 141-156, 2020

Authors: Laue, Sören | Mitterreiter, Matthias | Giesen, Joachim

Article Type: Research Article

Abstract: Computing derivatives of tensor expressions, also known as tensor calculus, is a fundamental task in machine learning. A key concern is the efficiency of evaluating the expressions and their derivatives that hinges on the representation of these expressions. Recently, an algorithm for computing higher order derivatives of tensor expressions like Jacobians or Hessians has been introduced that is a few orders of magnitude faster than previous state-of-the-art approaches. Unfortunately, the approach is based on Ricci notation and hence cannot be incorporated into automatic differentiation frameworks from deep learning like TensorFlow, PyTorch, autograd, or JAX that use the simpler Einstein notation. …This leaves two options, to either change the underlying tensor representation in these frameworks or to develop a new, provably correct algorithm based on Einstein notation. Obviously, the first option is impractical. Hence, we pursue the second option. Here, we show that using Ricci notation is not necessary for an efficient tensor calculus and develop an equally efficient method for the simpler Einstein notation. It turns out that turning to Einstein notation enables further improvements that lead to even better efficiency. The methods that are described in this paper for computing derivatives of matrix and tensor expressions have been implemented in the online tool www.MatrixCalculus.org . Show more

Keywords: tensor calculus, matrix calculus, algorithmic differentiation, tensor notation

DOI: 10.3233/FI-2020-1984

Citation: Fundamenta Informaticae, vol. 177, no. 2, pp. 157-179, 2020

Authors: Lin, Cheng-Kuan | Kung, Tzu-Liang | Wang, Dajin | Teng, Yuan-Hsiang

Article Type: Research Article

Abstract: The ability of identifying all the faulty devices in a multiprocessor system is known as diagnosability. The PMC model is the test-based diagnosis with a processor performing the diagnosis by testing the neighboring processors via the links between them. In this paper, we discuss the diagnosability of a (K 4 – {e })-free graph under the PMC model.

Keywords: system diagnosis, diagnosability, PMC model

DOI: 10.3233/FI-2020-1985

Citation: Fundamenta Informaticae, vol. 177, no. 2, pp. 181-188, 2020

Authors: Qi, Bin | Ma, Jie | Lv, Kewei

Article Type: Research Article

Abstract: The interval discrete logarithm problem(IDLP) is to find a solution n such that g n = h in a finite cyclic group G = 〈g 〉, where h ∈ G and n belongs to a given interval. To accelerate solving IDLP, a restricted jump method is given to speed up Pollard’s kangaroo algorithm in this paper. Since the Pollard’ kangaroo-like method need to compute the intermediate value during every iteration, the restricted jump method gives another way to reuse the intermediate value so that each iteration is speeded up at least 10 …times. Actually, there are some variants of kangaroo method pre-compute the intermediate value and reuse the pre-computed value in each iteration. Different from the pre-compute method that reuse the pre-computed value, the restricted jump method reuse the value naturally arised in pervious iteration, so that the improved algorithm not only avoids precomputation, but also speeds up the efficiency of each iteration. So only two or three large integer multiplications are needed in each iteration of the restricted jump method. And the average large integer multiplication times is (1:633 + o (1)) N in restricted jump method, which is verified in the experiment. Show more

Keywords: Interval Discrete Logarithm Algorithm, Pollards Kangaroo Algorithm, Jumping Distance Set, Coverage Rate

DOI: 10.3233/FI-2020-1986

Citation: Fundamenta Informaticae, vol. 177, no. 2, pp. 189-201, 2020