Two and a half billion years of distance research

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.

In this note, we study certain sufficient conditions for a set of minimal klt pairs ( X, triangle) with kappa ( X, triangle) = dim( X ) - 1 to be bounded. ...

Data-driven approaches have been applied to reduce the cost of accurate computational studies on materials, by using only a small number of expensive reference electronic structure calculations for a representative subset of the materials space, and using ...

A polyhedral graph is a 3-connected planar graph. We find the least possible order p(k, a) of a polyhedral graph containing a k-independent set of size a for all positive integers k and a. In the case k =1 and a even, we prove that the extremal graphs are ...

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

This paper proposes a method for the construction of quadratic serendipity element (QSE) shape functions on planar convex and concave polygons. Existing approaches for constructing QSE shape functions are linear combinations of the pair-wise products of ge ...

Collapsing cell complexes was first introduced in the 1930's as a way to deform a space into a topological-equivalent subspace with a sequence of elementary moves. Recently, discrete Morse theory techniques provided an efficient way to construct deformatio ...

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...

We construct a regular random projection of a metric space onto a closed doubling subset and use it to linearly extend Lipschitz and C-1 functions. This way we prove more directly a result by Lee and Naor [5] and we generalize the C-l extension theorem by ...

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho aro ...

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...

This article introduces a new class of models for multiple networks. The core idea is to parameterize a distribution on labeled graphs in terms of a Frechet mean graph (which depends on a user-specified choice of metric or graph distance) and a parameter t ...

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius ρ such that there exist balls of radius ρ around ...

Combining diffusion strategies with complementary properties enables enhanced performance when they can be run simultaneously. In this article, we first propose two schemes for the convex combination of two diffusion strategies, namely, the power-normalize ...

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...

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 ...

It is proved that the total length of any set of countably many rectifiable curves whose union meets all straight lines that intersect the unit square U is at least 2.00002. This is the first improvement on the lower bound of 2 known since 1964. A similar ...

Cao and Yuan obtained a Blichfeldt-type result for the vertex set of the edge-to-edge tiling of the plane by regular hexagons. Observing that the vertex set of every Archimedean tiling is the union of translates of a fixed lattice, we take a more general v ...

Two and a half billion years of distance research

Chat with Graph Search

On the boundedness of n-folds with κ(X) = n - 1

Efficient and insightful descriptors for representing molecular and material space

Independence numbers of polyhedral graphs

Results on Sparse Integer Programming and Geometric Independent Sets

Fairness and Explainability in Clustering Problems

Quadratic serendipity element shape functions on general planar polygons

Collapse-invariant properties of spaces equipped with signals or directions

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Adaptive majority problems for restricted query graphs and for weighted sets

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Linear Lipschitz and C-1 extension operators through random projection

Fair colorful k-center clustering

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Modeling Network Populations via Graph Distances

Fair Colorful k-Center Clustering

Convex Combination of Diffusion Strategies Over Networks

Local approximation of the Maximum Cut in regular graphs

Symbolic Algorithms for Token Swapping

A lower bound on opaque sets

A note on discrete lattice-periodic sets with an application to Archimedean tilings