Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Home

Person

Moritz Andreas Venzin

This person has left EPFL

About
Privacy
Disclaimer

Graph Chatbot

Related publications (5)

Page 1 of 1

Covering Convex Bodies and the Closest Vector Problem

Moritz Andreas Venzin, Márton Naszódi

We present algorithms for the (1+epsilon)-approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms in dimension n has running time of 2(O(n)) (1/epsilon)(n) . We improve th ...

2022

Approximate CVP in Time 2(0.802n) - Now in Any Norm!

Moritz Andreas Venzin

We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time 2(0.802 n). This contrasts the corresponding 2(n) time, (gap)-SETH based lower bounds for these problems that even apply for ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Efficient 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

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

Geometric Considerations in Lattice Programming

Moritz Andreas Venzin

We provide faster algorithms and fine-grained reductions for lattice problems in general norms. ...

EPFL2023