Concept
Big O notation
Related publications (72)
Exponential convergence to steady-states for trajectories of a damped dynamical system modeling adhesive strings
We study the global well-posedness and asymptotic behavior for a semilinear damped wave equation with Neumann boundary conditions, modeling a one-dimensional linearly elastic body interacting with a rigid substrate through an adhesive material. The key fea ...
World Scientific Publ Co Pte Ltd2024Static Worst-Case Resource Analysis for Substrate Pallets
We present saft, the first attempt of a static analyzer that extracts the asymptotic function complexity for the Polkadot/Substrate ecosystem, where the burden of accounting for computation resource consumption is put on the developer. saft is a tool meant ...
2023The splay-list: a distribution-adaptive concurrent skip-list
Amirkeivan Mohtashami, Dan Alistarh
The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good worst-case guarantees, although, in real workloads, objects are often ...
SPRINGER2023Physics-Inspired Equivariant Descriptors of Nonbonded Interactions
Michele Ceriotti, Philip Robin Loche, Kevin Kazuki Huguenin-Dumittan
One essential ingredient in many machine learning (ML) based methods for atomistic modeling of materials and molecules is the use of locality. While allowing better system-size scaling, this systematically neglects long-range (LR) effects such as electrost ...
Washington2023A combination technique for optimal control problems constrained by random PDEs
We present a combination technique based on mixed differences of both spatial approximations and quadrature formulae for the stochastic variables to solve efficiently a class of Optimal Control Problems (OCPs) constrained by random partial differential equ ...
EPFL2022Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost
We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of w workers and a multiset T ⊆ [t] of |T| = w tasks, a memoryless worker-task assignment function is any function ϕ that assigns the workers ...
Schloss Dagstuhl -- Leibniz-Zentrum fur Informatik2022Approximate CVPp in time 2(0.802n)
Friedrich Eisenbrand, Moritz Andreas Venzin
We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...
ACADEMIC PRESS INC ELSEVIER SCIENCE2022Safety in Numbers: Asymptotic Analysis of a Monitoring Problem
In this work, we introduce a setup where a monitoring entity attempts to distinguish a cheating player among a group of regular players where all players behave in order to maximize their reward. We assume that the cheating player has an "information advan ...
IEEE2022On the asymptotic behavior of solutions to the Vlasov-Poisson system
We prove small data modified scattering for the Vlasov-Poisson system in dimension using a method inspired from dispersive analysis. In particular, we identify a simple asymptotic dynamic related to the scattering mass. ...
2021Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity
Friedrich Eisenbrand, Moritz Andreas Venzin, Jana Tabea Cslovjecsek
We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021