Publication

Multiparametric Linear Complementarity Problems

Related publications (31)

Geometrical Treatise on the Modelling of 3D Particulate Inclusion-Matrix Microstructures with an Application to Historical Stone Masonry Walls

As historical stone masonry structures are vulnerable and prone to damage in earthquakes, investigating their structural integrity is important to reduce injuries and casualties while preserving their historical value. Stone masonry is a composite material ...

EPFL2022

Efficient Preparation of Cyclic Quantum States

Giovanni De Micheli, Fereshte Mozafari Ghoraba

Universal quantum algorithms that prepare arbitrary n-qubit quantum states require O(2n) gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum st ...

IEEE2022

Approximate 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 SCIENCE2022

Predicting in Uncertain Environments: Methods for Robust Machine Learning

Paul Thierry Yves Rolland

One of the main goal of Artificial Intelligence is to develop models capable of providing valuable predictions in real-world environments. In particular, Machine Learning (ML) seeks to design such models by learning from examples coming from this same envi ...

EPFL2022

DIVIDE-AND-CONQUER METHODS FOR FUNCTIONS OF MATRICES WITH BANDED OR HIERARCHICAL LOW-RANK STRUCTURE\ast

Daniel Kressner, Stefano Massei, Alice Cortinovis

This work is concerned with approximating matrix functions for banded matrices, hierarchically semiseparable matrices, and related structures. We develop a new divide-and-conquer method based on (rational) Krylov subspace methods for performing low-rank up ...

SIAM PUBLICATIONS2022

Safety Verification for Urban Air Mobility Scheduling

Nils Gustav Nilsson

In Urban Air Mobility (UAM) networks, takeoff and landing sites, called vertiports, are likely to experience intermittent closures due to, e.g., adverse weather. For safety, it will be required that all in-transit Urban Air Vehicles (UAVs) in a UAM network ...

ELSEVIER2022

Knapsack and Subset Sum with Small Items

Adam Teodor Polak, Lars Rohwedder

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

A unifying framework for form-finding and topology-finding of tensegrity structures

Yafeng Wang

This paper presents a unifying framework for the form-finding and topology-finding of tensegrity structures. The novel computational framework is based on rank-constrained linear matrix inequalities. For form-finding, given the topology (i.e., member conne ...

PERGAMON-ELSEVIER SCIENCE LTD2021

Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds

Adam Teodor Polak, Marek Elias

We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between power-saving states of different energy consumption and wake-up costs. We d ...

2021

On Randomized Trace Estimates for Indefinite Matrices with an Application to Determinants

Daniel Kressner, Alice Cortinovis

Randomized trace estimation is a popular and well-studied technique that approximates the trace of a large-scale matrix B by computing the average of x(T) Bx for many samples of a random vector X. Often, B is symmetric positive definite (SPD) but a number ...

2022

An efficient quantum algorithm for the time evolution of parameterized circuits

Giuseppe Carleo, Filippo Vicentini, Stefano Barison

We introduce a novel hybrid algorithm to simulate the real-time evolution of quantum systems using parameterized quantum circuits. The method, named "projected - Variational Quantum Dynamics" (p-VQD) realizes an iterative, global projection of the exact ti ...

VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF2021