Publications related to Randomized algorithm

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

Nematodynamics and random homogenization

Tudor Ratiu

We study the homogenization problem for the system of equations of dynamics of a mixture of liquid crystals with random structure. We consider a simplified form of the Ericksen-Leslie equations for an incompressible medium with inhomogeneous density with r ...

Taylor & Francis2016

MATHICSE Technical Report : Dimensionality reduction of parameter-dependent problems through proper orthogonal decomposition

Alfio Quarteroni, Andrea Manzoni, Federico Negri

The numerical solution of partial differential equations (PDEs) depending on para- metrized or random input data is computationally intensive. Reduced order modeling techniques, such as the reduced basis methods, have been developed to alleviate this compu ...

MATHICSE2016

From Acoustic Room Reconstruction to SLAM

Martin Vetterli, Ivan Dokmanic

Recent works on reconstruction of room geometry from echoes assume that the geometry of the sensor array is known. In this paper, we show that such an assumption is not essential; echoes provide sufficient clues to reconstruct the room’s and the array’s ge ...

Ieee2016

Fast Robust PCA on Graphs

Pierre Vandergheynst, Gilles Puy, Nathanaël Perraudin, Nauman Shahid, Vasilis Kalofolias

Mining useful clusters from high dimensional data has received significant attention of the computer vision and pattern recognition community in the recent years. Linear and non-linear dimensionality reduction has played an important role to overcome the c ...

Ieee-Inst Electrical Electronics Engineers Inc2016

Algorithms for reconstructing geometries from echoes

Fan Zhang

We have recently witnessed the appearance of algorithms that can reconstruct a room’s geometry from echoes, as well as algorithms that use echoes to localize many microphones. This project will consist in implementing a framework for microphone localizatio ...

2016

On solving LPN using BKW and variants Implementation and Analysis

Serge Vaudenay, Sonia Mihaela Bogos, Florian Tramèr

The Learning Parity with Noise problem (LPN) is appealing in cryptography as it is considered to remain hard in the post-quantum world. It is also a good candidate for lightweight devices due to its simplicity. In this paper we provide a comprehensive anal ...

Springer2016

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Lukas Polacek

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [2012] ...

Assoc Computing Machinery2016

A Bi-Criteria Approximation Algorithm for k-Means

Justin Dean Ward

We consider the classical k-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output beta*k > k clusters, and must produce a clustering with cost at most alpha times the to the cost of the optimal set ...

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik2016

Accelerated Spectral Clustering Using Graph Filtering of Random Signals

Pierre Vandergheynst, Rémi Gribonval, Gilles Puy, Nicolas Tremblay

We build upon recent advances in graph signal processing to propose a faster spectral clustering algorithm. Indeed, classical spectral clustering is based on the computation of the first

k

eigenvectors of the similarity matrix' Laplacian, whose computati ...

Ieee2016

Randomized algorithm

Graph Chatbot

Chat with Graph Search

A Comment on “Computational Complexity of Stochastic Programming Problems”

Nematodynamics and random homogenization

MATHICSE Technical Report : Dimensionality reduction of parameter-dependent problems through proper orthogonal decomposition

From Acoustic Room Reconstruction to SLAM

Fast Robust PCA on Graphs

Algorithms for reconstructing geometries from echoes

On solving LPN using BKW and variants Implementation and Analysis

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

A Bi-Criteria Approximation Algorithm for k-Means

Accelerated Spectral Clustering Using Graph Filtering of Random Signals

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

MATHICSE Technical Report : Dimensionality reduction of parameter-dependent problems through proper orthogonal decomposition

A Comment on “Computational Complexity of Stochastic Programming Problems”

Fast Robust PCA on Graphs

From Acoustic Room Reconstruction to SLAM

A Bi-Criteria Approximation Algorithm for k-Means

Accelerated Spectral Clustering Using Graph Filtering of Random Signals

Nematodynamics and random homogenization

Algorithms for reconstructing geometries from echoes

On solving LPN using BKW and variants Implementation and Analysis