Publications related to Millennium Prize Problems

Hands-on tasks make learning visible: a learning analytics lens on the development of mechanistic problem-solving expertise in makerspaces

Richard Lee Davis, Bertrand Roland Schneider

This study investigated the impact of participating in a year-long digital-fabrication course on high-school seniors' problem-solving skills, with a focus on problems involving mechanistic systems. The research questions centered on whether working in a ma ...

Springer2023

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022

Continuation Methods For Riemannian Optimization

Daniel Kressner, Axel Elie Joseph Séguin

Numerical continuation in the context of optimization can be used to mitigate convergence issues due to a poor initial guess. In this work, we extend this idea to Riemannian optimization problems, that is, the minimization of a target function on a Riemann ...

SIAM PUBLICATIONS2022

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

Global Frobenius liftability I

Maciej Emilian Zdanowicz

We formulate a conjecture characterizing smooth projective varieties in positive characteristic whose Frobenius morphism can be lifted modulo p(2)-we expect that such varieties, after a finite stale cover, admit a toric fibration over an ordinary abelian v ...

2021

Atomistic modeling of the solid-liquid interface of metals and alloys

Edoardo Baldi

Solidification is a phase transformation of utmost importance in material science, for it largely controls materials' microstructure on which a wide range of mechanical properties depends. Almost every human artifact undergoes a transformation that leads t ...

EPFL2020

Stationary Structures near the Kolmogorov and Poiseuille Flows in the 2d Euler Equations

Klaus Martin Widmayer

We study the behavior of solutions to the incompressible 2d Euler equations near two canonical shear flows with critical points, the Kolmogorov and Poiseuille flows, with consequences for the associated Navier-Stokes problems. We exhibit a large family of ...

2020

Constraint-aware neural networks for Riemann problems

Jan Sickmann Hesthaven, Deep Ray

Neural networks are increasingly used in complex (data-driven) simulations as surrogates or for accelerating the computation of classical surrogates. In many applications physical constraints, such as mass or energy conservation, must be satisfied to obtai ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2020

Controlling oscillations in high-order Discontinuous Galerkin schemes using artificial viscosity tuned by neural networks

Jan Sickmann Hesthaven, Niccolo' Discacciati, Deep Ray

High-order numerical solvers for conservation laws suffer from Gibbs phenomenon close to discontinuities, leading to spurious oscillations and a detrimental effect on the solution accuracy. A possible strategy to reduce it comprises adding a suitable amoun ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2020

On the asymptotic behavior of the solutions to parabolic variational inequalities

Maria Colombo

We consider various versions of the obstacle and thin-obstacle problems, we interpret them as variational inequalities, with non-smooth constraint, and prove that they satisfy a new constrained Lojasiewicz inequality. The difficulty lies in the fact that, ...

2020

Efficient Greedy Coordinate Descent for Composite Problems

Martin Jaggi, Sebastian Urban Stich, Sai Praneeth Reddy Karimireddy, Anastasiia Koloskova

Coordinate descent with random coordinate selection is the current state of the art for many large scale optimization problems. However, greedy selection of the steepest coordinate on smooth problems can yield convergence rates independent of the dimension ...

2019

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018

From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming

Daniel Kuhn, Peyman Mohajerin Esfahani, John Lygeros, Tobias Sutter

We consider linear programming (LP) problems in infinite dimensional spaces that are in general computationally intractable. Under suitable assumptions, we develop an approximation bridge from the infinite-dimensional LP to tractable finite convex programs ...

2018

State Machine Replication is More Expensive than Consensus

Rachid Guerraoui, Dragos-Adrian Seredinschi, Karolos Antoniadis

Consensus and State Machine Replication (SMR) are generally considered to be equivalent problems. In certain system models, indeed, the two problems are computationally equivalent: any solution to the former problem leads to a solution to the latter, and v ...

2018

Erdos Distinct Distances Problem and Extensions over Finite Spaces

Van Thang Pham

In this thesis we study a number of problems in Discrete Combinatorial Geometry in finite spaces. The contents in this thesis are structured as follows: In Chapter 1 we will state the main results and the notations which will be used throughout the thesis. ...

EPFL2017

A New Framework for Distributed Submodular Maximization

Justin Dean Ward

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algo ...

Ieee2016

On the born approximation for differential microwave imaging using volume integral equation formulation

Juan Ramon Mosig, Michael Mattes, Mina Bjelogrlic, Benjamin Fuchs

The Degree of Non-Linearity (DNL) of scattering problems and specifically of differential Microwave Imaging (dMWI) problems is addressed in this paper. The quantification of the DNL amounts to evaluate the validity range of the Born first order (linear) ap ...

2016

Local discontinuous Galerkin methods for fractional ordinary differential equations

Jan Sickmann Hesthaven

This paper discusses the upwinded local discontinuous Galerkin methods for the one-term/multi-term fractional ordinary differential equations (FODEs). The natural upwind choice of the numerical fluxes for the initial value problem for FODEs ensures stabili ...

2015

Enumeration-based approach to solving parametric linear complementarity problems

Colin Neil Jones

This paper presents a solution method for parametric linear complementarity problems (PLCP) that relies on an enumeration technique to discover all feasible bases. The enumeration procedure is based on evaluating all possible combinations of active constra ...

Elsevier2015

K-Adaptability in Two-Stage Robust Binary Programming

Daniel Kuhn, Grani Adiwena Hanasusanto, Wolfram Wiesemann

Over the last two decades, robust optimization has emerged as a computationally attractive approach to formulate and solve single-stage decision problems affected by uncertainty. More recently, robust optimization has been successfully applied to multi-sta ...

Informs2015