Publications associées à A Network Coding Approach to Network Tomography

Non-planarity of Markoff graphs mod p

We prove the non-planarity of a family of 3-regular graphs constructed from the solutions to the Markoff equation x2 + y2 + z2 = xyz modulo prime numbers greater than 7. The proof uses Euler characteristic and an enumeration of the short cycles in these gr ...

European Mathematical Soc-Ems2024

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Colin Peter Sandon

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Ieee-Inst Electrical Electronics Engineers Inc2024

BENIGN LANDSCAPES OF LOW-DIMENSIONAL RELAXATIONS FOR ORTHOGONAL SYNCHRONIZATION ON GENERAL GRAPHS

Nicolas Boumal

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...

Siam Publications2024

Network-based kinetic models: Emergence of a statistical description of the graph topology

Matteo Raviola

In this paper, we propose a novel approach that employs kinetic equations to describe the collective dynamics emerging from graph-mediated pairwise interactions in multi-agent systems. We formally show that for large graphs and specific classes of interact ...

Cambridge Univ Press2024

A Note on Lenses in Arrangements of Pairwise Intersecting Circles in the Plane

Rom Pinchasi

Let F be a family of n pairwise intersecting circles in the plane. We show that the number of lenses, that is convex digons, in the arrangement induced by F is at most 2n - 2. This bound is tight. Furthermore, if no two circles in F touch, then the geometr ...

Electronic Journal Of Combinatorics2024

Altruism, reciprocity, and tokens to reward forwarding data: Is that fair?

Verónica del Carmen Estrada Galiñanes, Arman Babaei

Decentralized storage networks offer services with intriguing possibilities to reduce inequalities in an extremely centralized market. Fair distribution of rewards, however, is still a persistent problem in the current generation of decentralized applicati ...

2024

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

Lukas Fritz Felix Vogl

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024

On Speed and Advantage : Results in Information Velocity and Monitoring Problems

Reka Inovan

Information theory has allowed us to determine the fundamental limit of various communication and algorithmic problems, e.g., the channel coding problem, the compression problem, and the hypothesis testing problem. In this work, we revisit the assumptions ...

EPFL2024

Fast and Future: Towards Efficient Forecasting in Video Semantic Segmentation

Evann Pierre Guy Courdier

Deep learning has revolutionized the field of computer vision, a success largely attributable to the growing size of models, datasets, and computational power. Simultaneously, a critical pain point arises as several computer vision applications are deploye ...

EPFL2024

Global, Passive Detection of Connection Tampering

Louis-Henri Manuel Jakob Merino

In-network devices around the world monitor and tamper with connections for many reasons, including intrusion prevention, combating spam or phishing, and country-level censorship. Connection tampering seeks to block access to specific domain names or keywo ...

Assoc Computing Machinery2023

Equivariant Neural Architectures for Representing and Generating Graphs

Clément Arthur Yvon Vignac

Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences. By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entiti ...

EPFL2023

Maximum Independent Set: Self-Training through Dynamic Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

2023

A full characterization of invariant embeddability of unimodular planar graphs

Laszlo Marton Toth

When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry-invariant? This question was answered for one-ended unimodular graphs in Benjamini and Timar, using ...

WILEY2023

Frequent asymmetric migrations suppress natural selection in spatially structured populations

Anne-Florence Raphaëlle Bitbol, Alia Abbara

Natural microbial populations often have complex spatial structures. This can impact their evolution, in particular the ability of mutants to take over. While mutant fixation probabilities are known to be unaffected by sufficiently symmetric structures, ev ...

Oxford Univ Press2023

Equilibria in Network Constrained Energy Markets

Leonardo Massai

We study an energy market composed of producers who compete to supply energy to different markets and want to maximize their profits. The energy market is modeled by a graph representing a constrained power network where nodes represent the markets and lin ...

Elsevier2023

Brain Fingerprinting Using Fmri Spectral Signatures On High-Resolution Cortical Graphs

Dimitri Nestor Alice Van De Ville, Hamid Behjat, Maria Giulia Preti, Stefano Moia, Carlo Ferritto

Resting-state fMRI has proven to entail subject-specific signatures that can serve as a fingerprint to identify individuals. Conventional methods are based on building a connectivity matrix based on correlation between the average time course of pairs of b ...

IEEE2023

Acceleration of graph pattern mining and applications to financial crime

Jovan Blanusa

Various forms of real-world data, such as social, financial, and biological networks, can be represented using graphs. An efficient method of analysing this type of data is to extract subgraph patterns, such as cliques, cycles, and motifs, from graphs. For ...

EPFL2023

Artificial Neural Network Training on an Optical Processor via Direct Feedback Alignment

Florent Gérard Krzakala, Julien Marcel Daniel Emmanuel Launay

Artificial Neural Networks (ANN) are habitually trained via the back-propagation (BP) algorithm. This approach has been extremely successful: Current models like GPT-3 have O(10 11 ) parameters, are trained on O(10 11 ) words and produce awe-inspiring resu ...

IEEE2023

Estimating the Topology of Preferential Attachment Graphs Under Partial Observability

Ali H. Sayed, Michele Cirillo

This work addresses the problem of learning the topology of a network from the signals emitted by the network nodes. These signals are generated over time through a linear diffusion process, where neighboring nodes exchange messages according to the underl ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2023

Short-term dynamics of drainage density based on a combination of channel flow state surveys and water level measurements

Andrea Rinaldo, Izabela Bujak-Ozga, Jana Freiin von Freyberg

Headwater streams often experience intermittent flow. Consequently, the flowing drainage network expands and contracts and the flowing drainage density (DD) varies over time. Monitoring the DD dynamics is essential to understand the processes controlling i ...

Wiley2023