Publications associées à Arbre couvrant

Distributed Optimization with Byzantine Robustness Guarantees

As modern machine learning continues to achieve unprecedented benchmarks, the resource demands to train these advanced models grow drastically. This has led to a paradigm shift towards distributed training. However, the presence of adversariesâ whether ma ...

EPFL2023

Communication-efficient distributed training of machine learning models

Thijs Vogels

In this thesis, we explore techniques for addressing the communication bottleneck in data-parallel distributed training of deep learning models. We investigate algorithms that either reduce the size of the messages that are exchanged between workers, or th ...

EPFL2023

Dimensionality reduction of time-series data, and systems and devices that use the resultant embeddings

Mackenzie Mathis, Steffen Schneider

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for dimensionality reduction of time-series using contrastive learning. A method can include receiving multidimensional input time series data that includes ...

2023

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Mikhail Kapralov, Jakab Tardos

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on ...

IEEE COMPUTER SOC2022

Metric dimension of critical Galton–Watson trees and linear preferential attachment trees

Gergely Odor

The metric dimension of a graph G is the minimal size of a subset R of vertices of G that, upon reporting their graph distance from a distinguished (source) vertex v⋆, enable unique identification of the source vertex v⋆ among all possible vertices of G. I ...

2021

Exceptional graphs for the random walk

Juhan Aru

If W is the simple random walk on the square lattice Z(2), then W induces a random walk W-G on any spanning subgraph G subset of Z(2) of the lattice as follows: viewing W as a uniformly random infinite word on the alphabet {x, -x, y, -y}, the walk W-G star ...

INST MATHEMATICAL STATISTICS2020

Testing for Equivalence of Network Distribution Using Subgraph Counts

Sofia Charlotta Olhede

We consider that a network is an observation, and a collection of observed networks forms a sample. In this setting, we provide methods to test whether all observations in a network sample are drawn from a specified model. We achieve this by deriving the j ...

AMER STATISTICAL ASSOC2020

Benchmark for Bimanual Robotic Manipulation of Semi-deformable Objects

Aude Billard, Kunpeng Yao, Bernardo Fichera, Farshad Khadivar, Konstantinos Chatzilygeroudis, Ilaria Lauzana, Fanjun Bu

We propose a new benchmarking protocol to evaluate algorithms for bimanual robotic manipulation semi-deformable objects. The benchmark is inspired from two real-world applications: (a) watchmaking craftsmanship, and (b) belt assembly in automobile engines. ...

2020

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

Christoph Hunkenschröder

We present a factors 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approxi ...

2019

Finding a Needle in the Haystack of Hardened Interconnect Patterns

Paolo Ienne, Grace Zgheib, Stefan Nikolic

Circuits naturally exhibit recurring patterns of local interconnect. Hardening those patterns when designing Field Programmable Gate Array (FPGA) clusters can both eliminate slow programmable connections from the critical path and remove the need for trans ...

IEEE2019

On Sets Defining Few Ordinary Circles

Frank de Zeeuw

An ordinary circle of a set P of n points in the plane is defined as a circle that contains exactly three points of P. We show that if P is not contained in a line or a circle, then P spans at least ordinary circles. Moreover, we determine the exact minimu ...

Springer2018

Spread of proliferative kidney disease in fish along stream networks: A spatial metacommunity framework

Andrea Rinaldo, Enrico Bertuzzo, Lorenzo Mari, Luca Carraro, Marino Gatto

Proliferative kidney disease (PKD) is a high-mortality pathology that critically affects freshwater salmonid populations. Infection is caused by the endoparasitic myxozoan Tetracapsuloides bryosalmonae, which exploits freshwater bryozoans as primary hosts. ...

2018

Photoinitiator-free Laser Fabrication of Ultra-compact, Low-loss Waveguides in Polydimethylsiloxane

Demetri Psaltis, Christophe Moser, Ye Pu, Giulia Panusa, Jieping Wang

Owing to its excellent elasticity, wide spectral range of transparency, and outstanding chemical and thermal stability, polydimethylsiloxane (PDMS) is an elastomer of great technological importance, being widely used in the fabrication of microfluidic and ...

SPIE-INT SOC OPTICAL ENGINEERING2018

A generalised framework for detailed classification of swimming paths inside the Morris Water Maze

Maria del Carmen Sandi Perez, Eleni Vasilaki

The Morris Water Maze is commonly used in behavioural neuroscience for the study of spatial learning with rodents. Over the years, various methods of analysing rodent data collected during this task have been proposed. These methods span from classical per ...

Nature Research2018

Semi-automatic 3D morphological reconstruction of neurons with densely branching morphology: Application to retinal All amacrine cells imaged with multi -photon excitation microscopy

Bas-Jan Zandt

Background: Accurate reconstruction of the morphology of single neurons is important for morphometric studies and for developing compartmental models. However, manual morphological reconstruction can be extremely time-consuming and error-prone and algorith ...

Elsevier2017

Using the Green's function to simplify and understand dendrites

Willem Anna Mark Wybo

Neurons are endowed with dendrites: tree-like structures that collect and transform inputs. These arborizations are believed to substantially enhance the computational repertoire of neurons. While it has long been known that dendrites are not iso-potential ...

EPFL2017

Fourier dimensionality reduction of radio-interferometric data

Jean-Philippe Thiran, Yves Wiaux, Rafael Eduardo Carrillo Rangel, Vijay Kartik

Next-generation radio-interferometers face a computing challenge with respect to the imaging techniques that can be applied in the big data setting in which they are designed. Dimensionality reduction can thus provide essential savings of computing resourc ...

2017

Exponential extinction time of the contact process on finite graphs

Thomas Mountford, Daniel Rodrigues Valesin, Jean-Christophe Mourrat

We study the extinction time tau of the contact process started with full occupancy on finite trees of bounded degree. We show that, if the infection rate is larger than the critical rate for the contact process on Z, then, uniformly over all trees of degr ...

Elsevier Science Bv2016

Fixed-wing drones for communication networks

Maja Varga

In the last decade, drones became frequently used to provide eye-in-the-sky overview in the outdoor environment. Their main advantage compared to the other types of robots is that they can fly above obstacles and rough terrains and they can quickly cover l ...

EPFL2016

Living on the Edge: Re-shaping the Interface of Synthetic Biology and Nanotechnology

Ardemis Anoush Boghossian, Shang-Jung Wu

A new team of researchers at EPFL is taking an 'anti-disciplinary' approach to creating optical devices. These devices take advantage of the synergy in tuning both nano- and bio-material properties, coupling 'the advantages of two growing, albeit tradition ...

Schweizerische Chemische Gesellschaft2016