Publication

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

Related publications (59)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Robust Adaptive Decision Making: Bayesian Optimization and Beyond

Ilija Bogunovic

The central task in many interactive machine learning systems can be formalized as the sequential optimization of a black-box function. Bayesian optimization (BO) is a powerful model-based framework for \emph{adaptive} experimentation, where the primary go ...

EPFL2019

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

Pairwise Comparisons with Flexible Time-Dynamics

Matthias Grossglauser, Lucas Maystre, Victor Kristof

Inspired by applications in sports where the skill of players or teams competing against each other varies over time, we propose a probabilistic model of pairwise-comparison outcomes that can capture a wide range of time dynamics. We achieve this by replac ...

ASSOC COMPUTING MACHINERY2019

When Stuck, Flip a Coin

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

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

Expectation propagation in the large data limit

Guillaume Philippe Ivan Joseph Dehaene

Expectation propagation (EP) is a widely successful algorithm for variational inference. EP is an iterative algorithm used to approximate complicated distributions, typically to find a Gaussian approximation of posterior distributions. In many applications ...

Wiley2018

LPN in Cryptography

Sonia Mihaela Bogos

The security of public-key cryptography relies on well-studied hard problems, problems for which we do not have efficient algorithms. Factorization and discrete logarithm are the two most known and used hard problems. Unfortunately, they can be easily solv ...

EPFL2017

AC OPF in radial distribution networks – Part II: An augmented Lagrangian-based OPF algorithm, distributable via primal decomposition

Jean-Yves Le Boudec, Mario Paolone, Dan-Cristian Tomozei, Konstantina Christakou

In the first part of this two-part paper we show that the branch-flow convexification of the OPF problem is not exact and that the ADMM-based decomposition of the OPF fails to converge in specific scenarios. Therefore, there is a need to develop algorithms ...

Elsevier2017

Fast iterative retrieval algorithm for ultrashort pulse characterization using dispersion scans

We present an iterative retrieval algorithm based on data constraint for ultrashort pulse characterization using dispersion scan (d-scan). The proposed algorithm is much faster and leads to a drastic reduction of retrieval times, but, compared to the stand ...

Optical Society of America2017

Non-gaussianity of the critical 3d Ising model

Bernardo Zan

We discuss the 4pt function of the critical 3d Ising model, extracted from recent conformal bootstrap results. We focus on the non-gaussianity Q - the ratio of the 4pt function to its gaussian part given by three Wick contractions. This ratio reveals signi ...

2017