Publications related to Parameterized complexity

Using SAS functions and high-resolution isotope data to unravel travel time distributions in headwater catchments

Andrea Rinaldo, Paolo Benettin, Gianluca Botter

We use high-resolution tracer data from an experimental site to test theoretical approaches that integrate catchment-scale flow and transport processes in a unified framework centered on selective age sampling by streamflow and evapotranspiration fluxes. T ...

American Geophysical Union2017

Breaking the FF3 Format Preserving Encryption

Serge Vaudenay, Fatma Betül Durak

The NIST standard FF3 scheme (also known as BPS scheme) is a tweakable block cipher based on a 8-round Feistel Network. We break it with a practical attack. Our attack exploits the bad domain separation in FF3 design. The attack works with chosen plaintext ...

2017

How Fast can a Distributed Transaction Commit?

Rachid Guerraoui, Junxiong Wang

The atomic commit problem lies at the heart of distributed database systems. The problem consists for a set of processes (database nodes) to agree on whether to commit or abort a transaction (agreement property). The commit decision can only be taken if al ...

2017

How Fast can a Distributed Transaction Commit?

Rachid Guerraoui, Junxiong Wang

The atomic commit problem lies at the heart of distributed database systems. The problem consists for a set of processes (database nodes) to agree on whether to commit or abort a transaction (agreement property). The commit decision can only be taken if al ...

ACM Press2017

K-Adaptability in Two-Stage Distributionally Robust Binary Programming

Daniel Kuhn, Grani Adiwena Hanasusanto, Wolfram Wiesemann

We propose to approximate two-stage distributionally robust programs with binary recourse decisions by their associated K-adaptability problems, which pre-select K candidate second-stage policies here-and-now and implement the best of these policies once t ...

Elsevier Science Bv2016

A Comment on “Computational Complexity of Stochastic Programming Problems”

Daniel Kuhn, Grani Adiwena Hanasusanto, Wolfram Wiesemann

Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Mathematical Programming A, 106(3):423–432, 200 ...

Springer Heidelberg2016

Multiresponse modeling of variably saturated flow and isotope tracer transport for a hillslope experiment at the Landscape Evolution Observatory

Damiano Pasetto

This paper explores the challenges of model parameterization and process representation when simulating multiple hydrologic responses from a highly controlled unsaturated flow and transport experiment with a physically based model. The experiment, conducte ...

Copernicus GmbH2016

SHAPE: Linear-Time Camera Pose Estimation With Quadratic Error-Decay

Martin Vetterli, Adam James Scholefield, Alireza Ghasemi

We propose a novel camera pose estimation or perspective-n-point (PnP) algorithm, based on the idea of consistency regions and half-space intersections. Our algorithm has linear time-complexity and a squared reconstruction error that decreases at least qua ...

Ieee2016

Collision-Free Pattern Formation

Rachid Guerraoui, Alexandre David Olivier Maurer

Shoals of small fishes can change their collective shape and form a specific pattern. They do so efficiently (in parallel) and without collision. In this paper, we study the analog problem of distributed pattern formation. A set of processes needs to move ...

2016

Exact Algorithms for $ L ^{ 1 } $ -TV Regularization of Real-Valued or Circle-Valued Signals

Michaël Unser, Martin Kurt Storath

We consider

L ^{ 1 }

-TV regularization of univariate signals with values on the real line or on the unit circle. While the real data space leads to a convex optimization problem, the problem is nonconvex for circle-valued data. In this paper, we deriv ...

SIAM2016

Parameterized complexity

Graph Chatbot

Chat with Graph Search

Using SAS functions and high-resolution isotope data to unravel travel time distributions in headwater catchments

Breaking the FF3 Format Preserving Encryption

How Fast can a Distributed Transaction Commit?

How Fast can a Distributed Transaction Commit?

K-Adaptability in Two-Stage Distributionally Robust Binary Programming

A Comment on “Computational Complexity of Stochastic Programming Problems”

Multiresponse modeling of variably saturated flow and isotope tracer transport for a hillslope experiment at the Landscape Evolution Observatory

SHAPE: Linear-Time Camera Pose Estimation With Quadratic Error-Decay

Collision-Free Pattern Formation

Exact Algorithms for $ L ^{ 1 } $ -TV Regularization of Real-Valued or Circle-Valued Signals

Using SAS functions and high-resolution isotope data to unravel travel time distributions in headwater catchments

K-Adaptability in Two-Stage Distributionally Robust Binary Programming

How Fast can a Distributed Transaction Commit?

How Fast can a Distributed Transaction Commit?

Multiresponse modeling of variably saturated flow and isotope tracer transport for a hillslope experiment at the Landscape Evolution Observatory

A Comment on “Computational Complexity of Stochastic Programming Problems”

Breaking the FF3 Format Preserving Encryption

Collision-Free Pattern Formation

Exact Algorithms for $ L ^{ 1 } $ -TV Regularization of Real-Valued or Circle-Valued Signals

SHAPE: Linear-Time Camera Pose Estimation With Quadratic Error-Decay