Registered Data

[CT006]

  • Session Time & Room
    • CT006 (1/1) : 2E @G304 [Chair: Riccardo Dondi]
  • Classification
    • CT006 (1/1) : Graph theory (05C) / Computational aspects and applications of commutative rings (13P) / Tropical geometry (14T) / Finite fields and commutative rings (number-theoretic aspects) (11T)

[00682] Cover Temporal Networks with Densest Subgraphs

  • Session Time & Room : 2E (Aug.22, 17:40-19:20) @G304
  • Type : Contributed Talk
  • Abstract : Temporal networks have been introduced to represent the dynamics of a complex system. In this contribution we consider a problem that asks for a collection of dense temporal subgraphs that covers a given temporal graph. The problem has application in the identification of communities of a complex system, for example of a social network. We present a result on the computational complexity of the problem and a polynomial-time approximation algorithm.
  • Classification : 05C85, 05C90, 68R10, 68R05, 68Q25
  • Format : Talk at Waseda University
  • Author(s) :
    • Riccardo Dondi (Università degli Studi di Bergamo)

[00540] Random product homotopies for decomposing tensors

  • Session Time & Room : 2E (Aug.22, 17:40-19:20) @G304
  • Type : Contributed Talk
  • Abstract : The rank one decomposition of the tensor is considered. The upper bound of rank is derived under which computing the decomposition is equivalent to solving a structured polynomial system that is determined by the full rank factorization of the matricization of the tensor. Under the generic uniqueness conditions, the solutions of the system are isolated and can be efficiently achieved by random product homotopies.
  • Classification : 13P15, 15A69, 15A72
  • Format : Talk at Waseda University
  • Author(s) :
    • Tsung-Lin Lee (National Sun Yat-sen University)

[00459] Tropical linear regression and mean payoff games: or, how to measure the distance to equilibria

  • Session Time & Room : 2E (Aug.22, 17:40-19:20) @G304
  • Type : Contributed Talk
  • Abstract : We study a tropical linear regression problem consisting in finding a best approximation of a set of points by a tropical hyperplane. We establish a strong duality theorem, showing that the value of this problem coincides with the maximal radius of a Hilbert's ball included in a tropical polyhedron. We show that this problem is polynomial-time equivalent to mean payoff games. We illustrate our results by solving an inverse problem from auction theory.
  • Classification : 14T90, 91A25, 91B26
  • Format : Talk at Waseda University
  • Author(s) :
    • Omar Saadi (College of Computing, Mohammed VI Polytechnic University)
    • Marianne Akian (INRIA and CMAP, École polytechnique)
    • Stéphane Gaubert (INRIA and CMAP, École polytechnique)
    • Yang Qi (INRIA and CMAP, École polytechnique)

[02500] Constructing crypto-algorithms using vector-valued functions

  • Session Time & Room : 2E (Aug.22, 17:40-19:20) @G304
  • Type : Contributed Talk
  • Abstract : Binary compositions of vector-valued functions defined on an arbitrary set, including finite sets, are introduced. Some properties of the compositions are investigated. In particular, it is proved that each of them is associative. Using the obtained results, crypto-algorithms with a public key have been obtained.
  • Classification : 11T71, 94A60, 05B15, 20N05, 20N15
  • Author(s) :
    • Fedir Sokhatsky (Vasyl' Stus Donetsk National University)