Registered Data
Contents
- 1 [CT006]
- 1.1 [00682] Cover Temporal Networks with Densest Subgraphs
- 1.2 [00933] Hankel Matrices of Finite Rank and Generalized Fibonacci Sequences
- 1.3 [02500] Constructing crypto-algorithms using vector-valued functions
- 1.4 [00540] Random product homotopies for decomposing tensors
- 1.5 [00459] Tropical linear regression and mean payoff games: or, how to measure the distance to equilibria
[CT006]
[00682] Cover Temporal Networks with Densest Subgraphs
- Session Date & Time : 2E (Aug.22, 17:40-19:20)
- 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
- Author(s) :
- Riccardo Dondi (Università degli Studi di Bergamo)
[00933] Hankel Matrices of Finite Rank and Generalized Fibonacci Sequences
- Session Date & Time : 2E (Aug.22, 17:40-19:20)
- Type : Contributed Talk
- Abstract : In this talk, we show the existence of the generalized Fibonacci sequence as a tool to study the infinite Hankel matrix of finite rank, associated to a nonzero sequence $S = \{s_n\}_ {n\geq 0}$ of real numbers. We make use this data to give some characterizations of the generating and representing measure for a sequence whose associated Hankel matrix is of finite rank.
- Classification : 11B99, 44A60, 15B99, 40A99, 30C15
- Author(s) :
- RAJAE BEN BEN TAHER (Faculty of Sciences, University Moulay Ismail- MEKNES- Morocco)
- RAJAE BEN TAHER ( University Moulay Ismail, Meknes)
[02500] Constructing crypto-algorithms using vector-valued functions
- Session Date & Time : 2E (Aug.22, 17:40-19:20)
- 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)
[00540] Random product homotopies for decomposing tensors
- Session Date & Time : 2E (Aug.22, 17:40-19:20)
- 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
- 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 Date & Time : 2E (Aug.22, 17:40-19:20)
- 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
- Author(s) :
- Omar Saadi (MSDA, 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)