Publications associées à Perfect Matchings in O (n(1.5)) Time in Regular Bipartite Graphs

Publications associées (31)

Lamplighters and the bounded cohomology of Thompson's group

We prove the vanishing of the bounded cohomology of lamplighter groups for a wide range of coefficients. This implies the same vanishing for a number of groups with self-similarity properties, such as Thompson's group F. In particular, these groups are bou ...

SPRINGER BASEL AG2022

On the logic of collapsibility for causal effect measures

Mats Julius Stensrud

WILEY2022

BLOOM: Bimodal Lattice One-out-of-Many Proofs and Applications

Ngoc Khanh Karol Nguyen

We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Ly ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

On the Kawamata-Viehweg vanishing theorem for log del Pezzo surfaces in positive characteristic

Emelie Kerstin Arvidsson, Fabio Bernasconi

We prove the Kawamata-Viehweg vanishing theorem for surfaces of del Pezzo type over perfect fields of positive characteristic p > 5. As a consequence, we show that klt threefold singularities over a perfect base field of characteristic p > 5 are rational. ...

CAMBRIDGE UNIV PRESS2022

One- and two-step semi-Lagrangian integrators for arbitrary Lagrangian-Eulerian-finite element two-phase flow simulations

John Richard Thome, Gustavo Rabello Dos Anjos

Semi-Lagrangian (SL) schemes are of utmost relevance to simulate two-phase flows where advection dominates. The combination of SL schemes with the finite element (FE) method and arbitrary Lagrangian-Eulerian (ALE) dynamic meshes yields a strong ingredient ...

WILEY2022

Recent Progresses On The Subconvexity Problem

Philippe Michel

The subconvexity problem aims at providing non-trivial (i.e. subconvex) bounds for central values of automorphic L-functions; the main conjecture in this area is the Generalized Lindelof Hypothesis which itself is a consequence of the Generalized Riemann H ...

2022

Conjugation spaces are cohomologically pure

Jérôme Scherer

Conjugation spaces are equipped with an involution such that the fixed points have the same mod 2 cohomology (as a graded vector space, a ring, and even an unstable algebra) but with all degrees divided by 2, generalizing the classical examples of complex ...

WILEY2021

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. ...

ASSOC COMPUTING MACHINERY2021

Crypt4GH: a file format standard enabling native access to encrypted data

Juan Ramón Troncoso-Pastoriza

Motivation: The majority of genome analysis tools and pipelines require data to be decrypted for access. This potentially leaves sensitive genetic data exposed, either because the unencrypted data is not removed after analysis, or because the data leaves t ...

Oxford University Press2021

Functional Tucker Approximation Using Chebyshev Interpolation

Daniel Kressner, Christoph Max Strössner

This work is concerned with approximating a trivariate function defined on a tensor-product domain via function evaluations. Combining tensorized Chebyshev interpolation with a Tucker decomposition of low multilinear rank yields function approximations tha ...

SIAM PUBLICATIONS2021

Estimation of separable direct and indirect effects in continuous time

Mats Julius Stensrud

Many research questions involve time-to-event outcomes that can be prevented from occurring due to competing events. In these settings, we must be careful about the causal interpretation of classical statistical estimands. In particular, estimands on the h ...

2021

Semi-streaming Algorithms for Submodular Matroid Intersection

Ola Nils Anders Svensson, Paritosh Garg

While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of 2 for the unweighted matching problem, it was only recently that Paz and Schwartzman obtained an analogous result for weighted instances. Their approach is ...

SPRINGER INTERNATIONAL PUBLISHING AG2021

Sparse non-negative super-resolution - simplified and stabilised

Armin Eftekhari, Hemant Tyagi

We consider the problem of non-negative super-resolution, which concerns reconstructing a non-negative signal x = Sigma(k )(i=1)a(i)delta(ti) from m samples of its convolution with a window function phi(s - t), of the form y(s(j)) = Sigma(k)(i=1) a(i) phi( ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2021

Polygonal surface processing and mesh generation tools for the numerical simulation of the cardiac function

Alfio Quarteroni

In order to simulate the cardiac function for a patient-specific geometry, the generation of the computational mesh is crucially important. In practice, the input is typically a set of unprocessed polygonal surfaces coming either from a template geometry o ...

Wiley2021

Gelfand pairs admit an Iwasawa decomposition

Nicolas Monod

Every Gelfand pair (G, K) admits a decomposition G = K P, where P < G is an amenable subgroup. In particular, the Furstenberg boundary of G is homogeneous. Applications include the complete classification of non-positively curved Gelfand pairs, relying on ...

SPRINGER HEIDELBERG2020

On the asymptotic behavior of the solutions to parabolic variational inequalities

Maria Colombo

We consider various versions of the obstacle and thin-obstacle problems, we interpret them as variational inequalities, with non-smooth constraint, and prove that they satisfy a new constrained Lojasiewicz inequality. The difficulty lies in the fact that, ...

2020

A Crossing Lemma for Multigraphs

János Pach

Let G be a drawing of a graph with n vertices and e > 4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi and Leighton, the nu ...

SPRINGER2020

Renormalizing individual performance metrics for cultural heritage management of sports records

Orion B Penner

Individual performance metrics are commonly used to compare players from different eras. However, such cross-era comparison is often biased due to significant changes in success factors underlying player achievement rates (e.g. performance enhancing drugs ...

PERGAMON-ELSEVIER SCIENCE LTD2020

A nonlinear model predictive control scheme for sensor fault tolerance in observation processes

Colin Neil Jones, Andrea Alessandretti

This article addresses the problem of designing a sensor fault-tolerant controller for an observation process where a primary, controlled system observes, through a set of measurements, an exogenous system to estimate the state of this system. We consider ...

WILEY2020

A non-intrusive multifidelity method for the reduced order modeling of nonlinear problems

Jan Sickmann Hesthaven, Mengwu Guo, Mariella Kast

We propose a non-intrusive reduced basis (RB) method for parametrized nonlinear partial differential equations (PDEs) that leverages models of different accuracy. From a collection of low-fidelity (LF) snapshots, parameter locations are extracted for the e ...

ELSEVIER SCIENCE SA2020