Publication

A semi-algebraic version of Zarankiewicz's problem

Related publications (30)

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

We develop an algorithm to solve the bottleneck assignment problem (BAP) that is amenable to having computation distributed over a network of agents. This consists of exploring how each component of the algorithm can be distributed, with a focus on one com ...

Ieee-Inst Electrical Electronics Engineers Inc2024

Unlabeled Principal Component Analysis and Matrix Completion

Liangzu Peng, Yunzhen Yao

We introduce robust principal component analysis from a data matrix in which the entries of its columns have been corrupted by permutations, termed Unlabeled Principal Component Analysis (UPCA). Using algebraic geometry, we establish that UPCA is a well-de ...

Microtome Publishing2024

K3 surfaces, cyclotomic polynomials and orthogonal groups

Eva Bayer Fluckiger

Let X be a complex projective K3 surface and let T-X be its transcendental lattice; the characteristic polynomials of isometries of T-X induced by automorphisms of X are powers of cyclotomic polynomials. Which powers of cyclotomic polynomials occur? The ai ...

Springer Int Publ Ag2024

The multivariate Serre conjecture ring

Luc Guyot

It is well-known that for any integral domain R, the Serre conjecture ring R(X), i.e., the localization of the univariate polynomial ring R[X] at monic polynomials, is a Bezout domain of Krull dimension

Academic Press Inc Elsevier Science2023

Nonlocally-resonant metamaterials

Aleksi Antoine Bossart

In this thesis, we unveil a third design path to manipulate elastic waves within architected media, distinct from the traditional phononic crystal and locally-resonant metamaterial concepts. The core innovation lies in the concept of nonlocal resonances, d ...

EPFL2023

Bootstrapping traceless symmetric O(N) scalars

Alessandro Vichi, Maria Refinetti, Marten Jan Reehorst

We use numerical bootstrap techniques to study correlation functions of traceless sym-metric tensors of O(N) with two indices ti j. We obtain upper bounds on operator dimen-sions for all the relevant representations and several values of N. We discover sev ...

SCIPOST FOUNDATION2023

Reliable uncertainties: Error correlation, rotated error bars, and linear regressions in three-isotope plots and beyond

Reto Georg Trappitsch

Correlated errors of experimental data are a common but often neglected problem in physical sciences. Various tools are provided here for thorough propagation of uncertainties in cases of correlated errors. Discussed are techniques especially applicable to ...

ELSEVIER2023

Functional estimation of anisotropic covariance and autocovariance operators on the sphere

Victor Panaretos, Julien René Pierre Fageot, Matthieu Martin Jean-André Simeoni, Alessia Caponera

We propose nonparametric estimators for the second-order central moments of possibly anisotropic spherical random fields, within a functional data analysis context. We consider a measurement framework where each random field among an identically distribute ...

2022

The Jordan property for local fundamental groups

Roberto Svaldi, Stefano Filipazzi

We show the Jordan property for regional fundamental groups of klt singularities of fixed dimension. Furthermore, we prove the existence of effective simultaneous index 1 covers for n-dimensional klt singularities. We give an application to the study of lo ...

2022

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

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

Wind farm layout and unconstrained hub height optimization using genetic algorithms applied to different power densities

Fernando Porté Agel, Nicolas Otto Kirchner Bossi

LES and wind tunnel studies have shown significant benefit when allowing turbines (T) in a wind farm to adopt different heights. This work presents two new genetic algorithms (GA) that perform wind farm layout optimization (WFLO) involving continuous and t ...

2022

Finite free convolutions of polynomials

Adam Wade Marcus

We study three convolutions of polynomials in the context of free probability theory. We prove that these convolutions can be written as the expected characteristic polynomials of sums and products of unitarily invariant random matrices. The symmetric addi ...

SPRINGER HEIDELBERG2022

Application of optimal spline subspaces for the removal of spurious outliers in isogeometric discretizations

Espen Sande

We show that isogeometric Galerkin discretizations of eigenvalue problems related to the Laplace operator subject to any standard type of homogeneous boundary conditions have no outliers in certain optimal spline subspaces. Roughly speaking, these optimal ...

2022

A Shadow Perspective on Equivariant Hochschild Homologies

Kathryn Hess Bellwald, Inbar Klang

Shadows for bicategories, defined by Ponto, provide a useful framework that generalizes classical and topological Hochschild homology. In this paper, we define Hochschild-type invariants for monoids in a symmetric monoidal, simplicial model category V, as ...

OXFORD UNIV PRESS2022

Stabilized isogeometric discretizations on trimmed and union geometries, and weak imposition of the boundary conditions for the Darcy flow

Riccardo Puppi

Modern manufacturing engineering is based on a ``design-through-analysis'' workflow. According to this paradigm, a prototype is first designed with Computer-aided-design (CAD) software and then finalized by simulating its physical behavior, which usually i ...

EPFL2022

Invariant integrals on topological groups

Vasco Schiavo

We generalize the fixed-point property for discrete groups acting on convex cones given by Monod in [23] to topological groups. At first, we focus on describing this fixed-point property from a functional point of view, and then we look at the class of gro ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2022

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Adam Teodor Polak, Alexandra Anna Lassota

We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...

Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022

Spectral Coarse Spaces for the Substructured Parallel Schwarz Method

Tommaso Vanzan

The parallel Schwarz method (PSM) is an overlapping domain decomposition (DD) method to solve partial differential equations (PDEs). Similarly to classical nonoverlapping DD methods, the PSM admits a substructured formulation, that is, it can be formulated ...

2022