Cluster-and-Conquer: When Randomness Meets Graph Locality

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information. First, we consider two stochastic models called query-commit and price-of-information where the algo ...

This work presents tweedledum-an extensible open-source library aiming at narrowing the gap between high-level algorithms and physical devices by enhancing the expressive power of existing frameworks. For example, it allows designers to insert classical lo ...

Can we use machine learning to compress graph data? The absence of ordering in graphs poses a significant challenge to conventional compression algorithms, limiting their attainable gains as well as their ability to discover relevant patterns. On the other ...

Neuroscience incorporates knowledge from a range of scales, from single molecules to brain wide neural networks. Modeling is a valuable tool in understanding processes at a single scale or the interactions between two adjacent scales and researchers use a ...

We present a technique for Model Order Reduction (MOR) of frequency-domain problems relying on rational interpolation of vector-valued functions. The selection of the sample points is carried out adaptively according to a greedy procedure. We describe seve ...

This paper develops high-order accurate entropy stable (ES) adaptive moving mesh finite difference schemes for the two- and three-dimensional special relativistic hydrodynamic (RHD) and magnetohydrodynamic (RMHD) equations, which is the high-order accurate ...

In this paper we revisit the kernel density estimation problem: given a kernel K(x, y) and a dataset of n points in high dimensional Euclidean space, prepare a data structure that can quickly output, given a query q, a (1 + epsilon)-approximation to mu := ...

Understanding epidemic propagation in large networks is an important but challenging task, especially since we usually lack information, and the information that we have is often counter-intuitive. An illustrative example is the dependence of the final siz ...

Bluetooth is a pervasive wireless technology specified in an open standard. The standard defines Bluetooth Classic (BT) for high-throughput wireless services and Bluetooth Low Energy (BLE) very low-power ones. The standard also specifies security mechanism ...

We study the optimization of large-scale, real-time ridesharing systems and propose a modular design methodology, Component Algorithms for Ridesharing (CAR). We evaluate a diverse set of CARs (14 in total), focusing on the key algorithmic components of rid ...

We propose GoldFinger, a new compact and fast-to-compute binary representation of datasets to approximate Jaccard’s index. We illustrate the effectiveness of GoldFinger on the emblematic big data problem of K-Nearest-Neighbor (KNN) graph construction and s ...

Volumetric representations are popular in inverse rendering because they have a simple parameterization, are smoothly varying, and transparently handle topology changes. However, incorporating the full volumetric transport of light is costly and challengin ...

Many important problems in contemporary machine learning involve solving highly non- convex problems in sampling, optimization, or games. The absence of convexity poses significant challenges to convergence analysis of most training algorithms, and in some ...

In this paper we introduce and study the STREAMINGCYCLES problem, a random order streaming version of the Boolean Hidden Hypermatching problem that has been instrumental in streaming lower bounds over the past decade. In this problem the edges of a graph G ...

The use of drones in search and rescue (SAR) missions can be very cognitively demanding. Since high levels of cognitive workload can negatively affect human performance, there is a risk of compromising the mission and leading to failure with catastrophic o ...

We propose a versatile framework based on random search, Sparse-RS, for score-based sparse targeted and untargeted attacks in the black-box setting. Sparse-RS does not rely on substitute models and achieves state-of-the-art success rate and query efficienc ...

We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in e ...

Optimizing resource utilization in target platforms is key to achieving high performance during DNN inference. While optimizations have been proposed for inference latency, memory footprint, and energy consumption, prior hardware-aware neural architecture ...

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

Millimeter wave (mmWave) radars are becoming a more popular sensing modality in self-driving cars due to their favorable characteristics in adverse weather. Yet, they currently lack sufficient spatial resolution for semantic scene understanding. In this pa ...

Cluster-and-Conquer: When Randomness Meets Graph Locality

Chat with Graph Search

How to Match in Modern Computational Settings

tweedledum: A Compiler Companion for Quantum Computing

Partition and Code: learning how to compress graphs

A Modular Workflow for Model Building, Analysis, and Parameter Estimation in Systems Biology and Neuroscience

MATHICSE Technical Report : Frequency-domain non-intrusive greedy Model Order Reduction based on minimal rational approximation

High-order accurate entropy stable adaptive moving mesh finite difference schemes for special relativistic (magneto)hydrodynamics

Kernel Density Estimation through Density Constrained Near Neighbor Search

The Role of Adaptivity in Source Identification with Time Queries

BLURtooth: Exploiting Cross-Transport Key Derivation in Bluetooth Classic and Bluetooth Low Energy

Putting ridesharing to the test: efficient and scalable solutions and the power of dynamic vehicle relocation

Smaller, Faster & Lighter KNN Graph Constructions

Unbiased Inverse Volume Rendering with Differential Trackers

Convergence without Convexity: Sampling, Optimization, and Games

Factorial Lower Bounds for (Almost) Random Order Streams

Cognitive workload monitoring in virtual reality based rescue missions with drones

Sparse-RS: A Versatile Framework for Query-Efficient Sparse Black-Box Adversarial Attacks

Symbolic Algorithms for Token Swapping

U-Boost NAS: Utilization-Boosted Differentiable Neural Architecture Search

New Results in Integer and Lattice Programming

Radatron: Accurate Detection Using Multi-resolution Cascaded MIMO Radar