Tag: networks

Complexity of neural network training and complexity proofs bypassing frontier issues

-- Valentin Dardilhac (LISN, Galac)

summary: We study the complexity of the neural network training decision
problem in two different contexts. First, in the general context, this
problem has been shown to be in extensions of the class ∃R. We have
been able to show that whenever the activation functions are Lipschitz
functions and the ...

Complexité en états : Renverser un langage réduit la complexité de l'opération racine.

-- Alexandre Durand (LITIS, Rouen)

summary: Les automates (DFA) sont des machines à états qui acceptent ou rejettent des mots. L'ensemble des mots reconnus par un automate est son langage. Les langages rationnels coïncident avec les langages reconnaissable par des automates. Ici nous allons nous intéresser à une mesure, à savoir la complexité en ...

Forecasting multivariate time series with attention mechanism and unsupervised learning

-- Philippe Rambaud (LISN, Galac)

summary: In the realm of newborn healthcare, identifying neurological pathologies has traditionally relied on the expertise of medical professionals, who perform visual assessments. However, due to the limited number of such experts available, there is an urgent need to develop a pre-diagnostic tool capable of early detection of abnormal neurological ...

Quantifiying the robustness of dynamical systems: relating time and space to length and precision

-- Manon Blanc (LISN, Galac)

summary: Reasoning about dynamical systems evolving over the reals is well-known to lead to undecidability. In particular, it is known there cannot be decision procedures for first-order theories over the reals, or decision procedures for state reachability. However, various results in the literature have shown that decision procedures exist when ...

Boolean dimension of boolean lattices

-- Hoang La (Jagiellonian University, Cracovie (Pologne))

summary: Partially ordered sets (or posets for short) are structures that arise naturally in mathematics in the study of binary relations between objects. A poset consists of a ground set -- a set of elements -- and a partial order among them, and are usually visualled with directed acyclic graphs (DAGs). Indeed ...

Efficient maximal cliques enumeration in weakly closed graphs

-- George Manoussakis (Université de Versailles Saint-Quentin-en-Yvelines)

summary: We show that the algorithm presented in [J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein. Finding cliques in social networks: A new distribution-free model. SIAM journal on computing, 49(2):448-464, 2020] can be modified to have enumeration time complexity αO(n·poly(c)). Here parameter ...

Auction mechanisms for allocation and pricing in Edge Computing

-- João Paulo Silva (LISN, Galac)

summary: Soon, billions of devices will be connected to the Internet, and most of them will need external resources to store and process their data. Edge Computing can benefit these devices by making these resources available at the network's edges to be closer to the user. However, these offered ...

A Closure Lemma for tough graphs and Hamiltonian degree conditions

-- Cléophée Robin (Wilfrid Laurier University, Waterloo (Canada))

summary: A graph G is Hamiltonian if there exists a cycle in G containing all vertices of G exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G−S is at most |S|/t. We extended the theorem of ...

Memory-Optimization for Self-Stabilizing Distributed Algorithms

-- Gabriel Le Bouder (LIP6)

summary: Self-stabilization is a suitable paradigm for distributed systems, particularly prone to transient faults. Errors such as memory or messages corruption, break of a communication link, can put the system in an inconsistent state. A protocol is self-stabilizing if, whatever the initial state of the system, it guarantees that it ...

Complexity of positional games

-- Valentin Gledel (Umeå Universitet)

summary: Positional games are two-player games played on a hypergraph. The players alternate selecting vertices of the hypergraph, and the winning conditions depend solely on the filling of the hyperedges. Tic-tac-toe is a famous example of a positional game, with the rows, columns, and diagonals forming the hyperedges and the ...

Page 1 / 2 »