Publication

Partial Recovery Bounds for the Sparse Stochastic Block Model

Related publications (31)

New Graph Algorithms via Polyhedral Techniques

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

Sparse Sampling for Inverse Problems With Tensors

Guillermo Ortiz Jimenez

We consider the problem of designing sparse sampling strategies for multidomain signals, which can be represented using tensors that admit a known multilinear decomposition. We leverage the multidomain structure of tensor signals and propose to acquire sam ...

2019

Learning and Adaptive Data Analysis via Maximal Leakage

Michael Christoph Gastpar, Ibrahim Issa, Amedeo Roberto Esposito

There has been growing interest in studying connections between generalization error of learning algorithms and information measures. In this work, we generalize a result that employs the maximal leakage, a measure of leakage of information, and explore ho ...

IEEE2019

Statistical Physics Methods for Community Detection

Chun Lam Chan

This thesis is devoted to information-theoretic aspects of community detection. The importance of community detection is due to the massive amount of scientific data today that describes relationships between items from a network, e.g., a social network. I ...

EPFL2019

A reduced basis approach to large-scale pseudospectra computation

Petar Sirkovic

For studying spectral properties of a nonnormal matrix A is an element of Cnxn, information about its spectrum sigma(A) alone is usually not enough. Effects of perturbations on sigma(A) can be studied by computing epsilon-pseudospectra, i.e. the level sets ...

WILEY2019

Low-rank and sparse subspace modeling of speech for DNN based acoustic modeling

Hervé Bourlard, Afsaneh Asaei, Pranay Dighe

Towards the goal of improving acoustic modeling for automatic speech recognition (ASR), this work investigates the modeling of senone subspaces in deep neural network (DNN) posteriors using low-rank and sparse modeling approaches. While DNN posteriors are ...

ELSEVIER SCIENCE BV2019

A priori error for unilateral contact problems with Lagrange multipliers and isogeometric analysis

Annalisa Buffa, Mathieu Jonathan Fabre, Pablo Antolin Sanchez

In this paper, we consider unilateral contact problem without friction between a rigid body and deformable one in the framework of isogeometric analysis. We present the theoretical analysis of the mixed problem. For the displacement, we use the pushforward ...

2019

Finding Perfect Matchings in Bipartite Hypergraphs

Chidambaram Annamalai

Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perf ...

SPRINGER HEIDELBERG2018

Round Compression for Parallel Matching Algorithms

Slobodan Mitrovic, Aleksander Madry

For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture th ...

ASSOC COMPUTING MACHINERY2018

Near-Optimal Noisy Group Testing via Separate Decoding of Items

Volkan Cevher, Jonathan Mark Scarlett

The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of tests, and is relevant in applications such as medical testing, communication protocols, pattern matching, and more. In this pa ...

2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Slobodan Mitrovic, Mohsen Ghaffari

We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum ve ...

ASSOC COMPUTING MACHINERY2018