Concept

Structure d'incidence

Publications associées (18)

Spectral Hypergraph Sparsifiers of Nearly Linear Size

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

Leveraging topology, geometry, and symmetries for efficient Machine Learning

Michaël Defferrard

When learning from data, leveraging the symmetries of the domain the data lies on is a principled way to combat the curse of dimensionality: it constrains the set of functions to learn from. It is more data efficient than augmentation and gives a generaliz ...

EPFL2022

The emergence of small-scale self-affine surface roughness from deformation

Till Junge

Most natural and man-made surfaces appear to be rough on many length scales. There is presently no unifying theory of the origin of roughness or the self-affine nature of surface topography. One likely contributor to the formation of roughness is deformati ...

AMER ASSOC ADVANCEMENT SCIENCE2020

Realizability of planar point embeddings from angle measurements

Majed El Helou, Adam James Scholefield, Frederike Dümbgen

Localization of a set of nodes is an important and a thoroughly researched problem in robotics and sensor networks. This paper is concerned with the theory of localization from inner-angle measurements. We focus on the challenging case where no anchor loca ...

IEEE2020

Saturation of Berge hypergraphs

Abhishek Methuku

Given a graph F, a hypergraph is a Berge-F if it can be obtained by expanding each edge in F to a hyperedge containing it. A hypergraph H is Berge-F-saturated if H does not contain a subhypergraph that is a Berge-F, but for any edge e is an element of E((H ...

Elsevier2019

Asyrnptotics for the Turan number of Berge-K-2,K-t

Abhishek Methuku

Let F be a graph. A hypergraph is called Berge-F if it can be obtained by replacing each edge in F by a hyperedge containing it. ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

Matching fields and lattice points of simplices

Georg Peter Loho

We show that the Chow covectors of a linkage matching field define a bijection of lattice points and we demonstrate how one can recover the linkage matching field from this bijection. This resolves two open questions from Sturmfels & Zelevinsky (1993) on l ...

2020

Computational development of the nanoporous materials genome

Berend Smit, Peter George Boyd, Yongjin Lee

There is currently a push towards big data and data mining in materials research to accelerate discovery. Zeolites, metal-organic frameworks and other related crystalline porous materials are not immune to this phenomenon, as evidenced by the proliferation ...

Nature Publishing Group2017

Extension complexity of stable set polytopes of bipartite graphs

Yuri Faenza, Manuel Francesco Aprile

The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...

Springer2017

On some algebraic and extremal problems in discrete geometry

Seyed Hossein Nassajianmojarrad

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer

n\ge 3

, we define

e(n)

to be the minimum positive integer such that an ...

EPFL2017

On the Zarankiewicz problem for intersection hypergraphs

János Pach

Let d and t be fixed positive integers, and let denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem ...

Academic Press Inc Elsevier Science2016

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

János Pach

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of ev ...

Society for Industrial and Applied Mathematics2016

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Bartosz Maria Walczak, Michal Lason

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the ...

Springer US2013

Identification of genetic determinants and pharmacological modulators of mitochondrial function

Pénélope Andreux

Increased life expectancy goes hand in hand with a higher incidence of age-related diseases that affect the nervous and metabolic systems, such as type 2 diabetes, cancer, Parkinson’s and Alzheimer’s disease. These complex diseases are a product of the com ...

EPFL2013

Understanding and improving relational matrix factorization in recommender systems

Boi Faltings, Li Pu

Matrix factorization techniques such as the singular value decomposition (SVD) have had great success in recommender systems. We present a new perspective of SVD for constructing a latent space from the training data, which is justified by the theory of hy ...

ACM Press2013

State-resolved reactivity of CH4 on Pt(110)-(1 x 2): The role of surface orientation and impact site

Rainer Beck, Régis Bisson, Marco Sacchi

The reactivity of methane (CH4) on Pt(110)-(1×2) has been studied by quantum state-resolved surface reactivity measurements. Ground state reaction probabilities, S0(v=0) ~ S0(laser-off), as well as state-resolved reaction probabilities S0(2v3), for CH4 exc ...

2010

Coloring axis-parallel rectangles

János Pach, Gábor Tardos

For every k and r, we construct a finite family of axis-parallel rectangles in the plane such that no matter how we color them with k colors, there exists a point covered by precisely r members of the family, all of which have the same color. For r = 2, th ...

2010

The effect of molecular vibrations and surface structure on the chemisorption of methane on platinum

Marco Sacchi

In this thesis, I report state-resolved measurements of the chemisorption probability of CH4 on Pt(111) and Pt(110)-(1×2) for several rovibrationally excited states (2ν3, ν1+ν4, and 2ν2+ν4) in addition to the ground state. Measurements of the state resolve ...

EPFL2008