Publication

Generating Fast Indulgent Algorithms

Related publications (112)

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.

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

Novel Algorithms For Clustering

James Peter Newling

Clustering is a method for discovering structure in data, widely used across many scientific disciplines. The two main clustering problems this dissertation considers are K-means and K-medoids. These are NP-hard problems in the number of samples and cluste ...

EPFL2018

SAT-Based Area Recovery in Structural Technology Mapping

Bruno Schmitt Antunes

This paper proposes a fast SAT-based algorithm for recovering area applicable to an already technology mapped circuit. The algorithm considers a sequence of relatively small overlapping regions, called windows, in a mapped network and tries to improve the ...

ASSOC COMPUTING MACHINERY2018

General Proximal Gradient Method: A Case for Non-Euclidean Norms

Volkan Cevher, Ya-Ping Hsieh, Marwa El Halabi, Cong Bang Vu, Van Quang Nguyen

In this paper, we consider composite convex minimization problems. We advocate the merit of considering Generalized Proximal gradient Methods (GPM) where the norm employed is not Euclidean. To that end, we show the tractability of the general proximity ope ...

2017

Cooperative Data Exchange with Weighted Cost based on d-Basis Construction

Michael Christoph Gastpar, Su Li, Abhin Shah

We consider the cooperative data exchange problem, in which nodes are fully connected with each other. Each node initially only has a subset of the K packets making up a file and wants to recover the whole file. Node i can make a broadcast transmission, wh ...

2017

Recompression Of Hadamard Products Of Tensors In Tucker Format

Daniel Kressner, Lana Perisa

The Hadamard product features prominently in tensor-based algorithms in scientific computing and data analysis. Due to its tendency to significantly increase ranks, the Hadamard product can represent a major computational obstacle in algorithms based on lo ...

Siam Publications2017

Collision-Free Pattern Formation

Rachid Guerraoui, Alexandre David Olivier Maurer

Shoals of small fishes can change their collective shape and form a specific pattern. They do so efficiently (in parallel) and without collision. In this paper, we study the analog problem of distributed pattern formation. A set of processes needs to move ...

2016

Pattern formation with voluminous processes

Alexandre David Olivier Maurer

When a shoal of small fishes notices a predator, they typically change their collective shape and form a specific pattern. They do so efficiently (in parallel) and without collision. This motivates us to design algorithms with similar properties. In this p ...

EPFL2016

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

A Dichotomy for Real Weighted Holant Problems

Sangxia Huang

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks can ...

Springer Basel Ag2016