Publication

Paris (Monde) : géographies du 13 novembre 2015

Publications associées (32)

Discrete Optimal Transport with Independent Marginals is #P-Hard

Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

2022

A combination technique for optimal control problems constrained by random PDEs

Fabio Nobile, Tommaso Vanzan

We present a combination technique based on mixed differences of both spatial approximations and quadrature formulae for the stochastic variables to solve efficiently a class of Optimal Control Problems (OCPs) constrained by random partial differential equ ...

EPFL2022

Fast Transformers with Clustered Attention

François Fleuret, Angelos Katharopoulos, Apoorv Vyas

Transformers have been proven a successful model for a variety of tasks in sequence modeling. However, computing the attention matrix, which is their key component, has quadratic complexity with respect to the sequence length, thus making them prohibitivel ...

2020

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...

ASSOC COMPUTING MACHINERY2020

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Serge Vaudenay, Fatma Betül Durak

Feistel Networks (FN) are now being used massively to encrypt credit card numbers through format-preserving encryption. In our work, we focus on FN with two branches, entirely unknown round functions, modular additions (or other group operations), and when ...

2018

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Serge Vaudenay, Fatma Betül Durak

ePrint2018

Breaking The FF3 Format-Preserving Encryption Standard Over Small Domains

Serge Vaudenay, Fatma Betül Durak

The National Institute of Standards and Technology (NIST) recently published a Format-Preserving Encryption standard accepting two Feistel structure based schemes called FF1 and FF3. Particularly, FF3 is a tweakable block cipher based on an 8-round Feistel ...

2017

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

Artist-Oriented 3D Character Posing from 2D Strokes

Ronan Boulic, Benoît Le Callennec, Mentar Mahmudi, Pawan Kumar Harish

In this paper we present an intuitive tool suitable for 2D artists using touch-enabled pen tablets. An artist-oriented tool should be easy-to-use, real-time, versatile, and locally refinable. Our approach uses an interactive system for 3D character posing ...

Elsevier2016

Complexity Constrained Representation Selection for Dynamic Adaptive Streaming

Pascal Frossard, Laura Toni, Chenglin Li

In this paper, we propose a representation selection optimization problem for complexity constrained adaptive video streaming that properly takes into account the different complexity-rate-distortion (C-R-D) characteristics of the videos when implementing ...

Ieee2016

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search