Publication

A note on chromatic properties of threshold graphs

Publications associées (29)

GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

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

Unambiguous DNFs and Alon-Saks-Seymour

Mika Tapani Göös, Siddhartha Jain

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...

IEEE COMPUTER SOC2022

The micro-world of cographs

Dominique de Werra

Cographs constitute a small point in the atlas of graph classes. However, by zooming in on this point, we discover a complex world, where many parameters jump from finiteness to infinity. In the present paper, we identify several milestones in the world of ...

ELSEVIER2022

Defects in III-N LEDs: experimental identification and impact on electro-optical characteristics

Jean-François Carlin, Nicolas Grandjean, Mauro Mosca, Camille Haller

III-N light-emitting-diodes (LEDs) are subject of intense investigations, thanks to their high efficiency and great reliability. The quality of the semiconductor material has a significant impact on the electro-optical performance of LEDs: for this reason, ...

SPIE-INT SOC OPTICAL ENGINEERING2022

Removing Algorithmic Discrimination (With Minimal Individual Error)

Rachid Guerraoui, El Mahdi El Mhamdi, Le Nguyen Hoang, Alexandre David Olivier Maurer

We address for the first time the problem of correcting group discriminations within a score function, while minimizing the individual error. Each group is described by a probability density function on the set of profiles. We first solve the problem analy ...

2022

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

A Theory of Value for Service Ecosystems

Blagovesta Hristova Kostova

In this thesis, we present a theory of value for the design and analysis of service ecosystems. The theory is based on general systems thinking. The concept of a system is used for relating knowledge from different disciplines (such as software engineering ...

EPFL2022

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

Nathanaël Perraudin, Andreas Loukas, Karolis Martinkus

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

Creating and controlling exceptional points of non-Hermitian Hamiltonians via homodyne Lindbladian invariance

Fabrizio Minganti

The exceptional points (EPs) of non-Hermitian Hamiltonians (NHHs) are spectral degeneracies associated with coalescing eigenvalues and eigenvectors, which are associated with remarkable dynamical properties. These EPs can be generated experimentally in ope ...

AMER PHYSICAL SOC2022