Publications related to Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling

Reach For the Arcs: Reconstructing Surfaces from SDFs via Tangent Points

We introduce an algorithm to reconstruct a mesh from discrete samples of a shape's Signed Distance Function (SDF). A simple geometric reinterpretation of the SDF lets us formulate the problem through a point cloud, from which a surface can be extracted wit ...

2024

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed p ...

EPFL2023

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

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

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. The input consists of a set of jobs, characterized by their processing times, release time ...

ASSOC COMPUTING MACHINERY2021

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

,

b \in \Z^m

,

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

On the 2D Post-Processing of Brillouin Optical Time-Domain Analysis

Luc Thévenaz, Zhisheng Yang, Simon Adrien Zaslawski

The benefits and limitations inherent to the 2D post-processing of measurements from Brillouin optical time-domain analyzers are investigated from a fundamental point of view. In a preliminary step, the impact of curve fitting on the precision of the estim ...

2020

Fourier Sampling in Signal Processing and Numerical Linear Algebra

Amir Zandieh

This thesis focuses on developing efficient algorithmic tools for processing large datasets. In many modern data analysis tasks, the sheer volume of available datasets far outstrips our abilities to process them. This scenario commonly arises in tasks incl ...

EPFL2020

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

Mikhail Kapralov, Amir Zandieh, Navid Nouri

Random binning features, introduced in the seminal paper of Rahimi and Recht '07, are an efficient method for approximating a kernel matrix using locality sensitive hashing. Random binning features provide a very simple and efficient way to approximate the ...

ADDISON-WESLEY PUBL CO2020

Learning to Play Sequential Games versus Unknown Opponents

Maryam Kamgarpour, Andreas Krause, Ilija Bogunovic

We consider a repeated sequential game between a learner, who plays first, and an opponent who responds to the chosen action. We seek to design strategies for the learner to successfully interact with the opponent. While most previous approaches consider k ...

Curran Associates, Inc.2020

Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling

Graph Chatbot

Chat with Graph Search

Reach For the Arcs: Reconstructing Surfaces from SDFs via Tangent Points

Results on Sparse Integer Programming and Geometric Independent Sets

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

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

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

New Results in Integer and Lattice Programming

On the 2D Post-Processing of Brillouin Optical Time-Domain Analysis

Fourier Sampling in Signal Processing and Numerical Linear Algebra

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

Learning to Play Sequential Games versus Unknown Opponents

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

Reach For the Arcs: Reconstructing Surfaces from SDFs via Tangent Points

Results on Sparse Integer Programming and Geometric Independent Sets

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

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

Fourier Sampling in Signal Processing and Numerical Linear Algebra

New Results in Integer and Lattice Programming

On the 2D Post-Processing of Brillouin Optical Time-Domain Analysis

Learning to Play Sequential Games versus Unknown Opponents

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing