Publications associées à Decomposition of Multiple Packings with Subquadratic Union Complexity

Publications associées (30)

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

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

Additive and geometric transversality of fractal sets in the integers

Florian Karl Richter

By juxtaposing ideas from fractal geometry and dynamical systems, Furstenberg proposed a series of conjectures in the late 1960's that explore the relationship between digit expansions with respect to multiplicatively independent bases. In this work, we in ...

2024

In Medio Stat Virtus: Combining Boolean and Pattern Matching

Giovanni De Micheli, Alessandro Tempia Calvino, Gianluca Radi

Technology mapping transforms a technology-independent representation into a technology-dependent one given a library of cells. This process is performed by means of local replacements that are extracted by matching sections of the subject graph to library ...

IEEE2024

Mean value theorems for collections of lattices with a prescribed group of symmetries

Nihar Prakash Gargava

Euclidean lattices are mathematical objects of increasing interest in the fields of cryptography and error-correcting codes. This doctoral thesis is a study on high-dimensional lattices with the motivation to understand how efficient they are in terms of b ...

EPFL2024

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

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

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

EPFL2023

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

Thick points of the planar GFF are totally disconnected for all & gamma;=6 0*

Juhan Aru

We prove that the set of-y-thick points of a planar Gaussian free field (GFF) with Dirichlet boundary conditions is a.s. totally disconnected for all-y =6 0. Our proof relies on the coupling between a GFF and the nested CLE4. In particular, we show that th ...

INST MATHEMATICAL STATISTICS-IMS2023

Metastability of the Potts Ferromagnet on Random Regular Graphs

Jean Bernoulli Ravelomanana

We study the performance of Markov chains for the q-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis ...

SPRINGER2023

GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

Daniel Gatica-Perez, Sina Sajadmanesh

In this paper, we study the problem of learning Graph Neural Networks (GNNs) with Differential Privacy (DP). We propose a novel differentially private GNN based on Aggregation Perturbation (GAP), which adds stochastic noise to the GNN's aggregation functio ...

Usenix Assoc2023

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

Akash Kumar

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

IEEE COMPUTER SOC2022

Fourier non-uniqueness sets from totally real number fields

Martin Peter Stoller

Let K be a totally real number field of degree n >= 2. The inverse different of K gives rise to a lattice in Rn. We prove that the space of Schwartz Fourier eigenfunctions on R-n which vanish on the "component-wise square root" of this lattice, is infinite ...

EUROPEAN MATHEMATICAL SOC-EMS2022

Space-Efficient Representations of Graphs

Jakab Tardos

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...

EPFL2022

SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators

Andreas Loukas, Nathanaël Perraudin

We approach the graph generation problem from a spectral perspective by first generating the dominant parts of the graph Laplacian spectrum and then building a graph matching these eigenvalues and eigenvectors. Spectral conditioning allows for direct model ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2022

Graph Neural Networks With Lifting-Based Adaptive Graph Wavelets

Pascal Frossard

Spectral-based graph neural networks (SGNNs) have been attracting increasing attention in graph representation learning. However, existing SGNNs are limited in implementing graph filters with rigid transforms and cannot adapt to signals residing on graphs ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

Negar Kiyavash, Ehsan Mokhtarian, Saber Salehkaleybar

We study experiment design for unique identification of the causal graph of a system where the graph may contain cycles. The presence of cycles in the structure introduces major challenges for experiment design as, unlike acyclic graphs, learning the skele ...

2023

Generalised Implicit Neural Representations

Daniele Grattarola, Pierre Vandergheynst

We consider the problem of learning implicit neural representations (INRs) for signals on non-Euclidean domains. In the Euclidean case, INRs are trained on a discrete sampling of a signal over a regular lattice. Here, we assume that the continuous signal e ...

2022

The exploration process of critical Boltzmann planar maps decorated by a triangular O(n) loop model

Aleksandra Korzhenkova

In this paper we investigate pointed (q, g, n)-Boltzmann loop-decorated maps with loops traversing only inner triangular faces. Using peeling exploration Budd (2018) modified to this setting we show that its law in the non-generic critical phase can be cod ...

IMPA2022

On the constancy theorem for anisotropic energies through differential inclusions

Riccardo Tione

In this paper we study stationary graphs for functionals of geometric nature defined on currents or varifolds. The point of view we adopt is the one of differential inclusions, introduced in this context in the recent papers (De Lellis et al. in Geometric ...

2021

Adaptive majority problems for restricted query graphs and for weighted sets

Doemoetoer Palvoelgyi, Abhishek Methuku, Balázs Keszegh

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

ELSEVIER2021