Concept

NP-completeness

Related publications (376)

A Tight Lower Bound for Entropy Flattening

We study entropy flattening: Given a circuit C_X implicitly describing an n-bit source X (namely, X is the output of C_X on a uniform random input), construct another circuit C_Y describing a source Y such that (1) source Y is nearly flat (uniform on its s ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2018

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

High-Precision Performance Estimation for the Design Space Exploration of Dynamic Dataflow Programs

Marco Mattavelli, Simone Casale Brunet, Endri Bezati, Malgorzata Maria Michalska

The implementation and optimization of dynamic dataflow programs on multi/many-core platforms require solving a very difficult problem: how to partition and schedule the processing elements and dimension their interconnecting buffers according to given opt ...

2018

Four-Port Broadband Orthomode Transducer Enabling Arbitrary Interelement Spacing

Juan Ramon Mosig, Anja Skrivervik, Emile Jacques de Rijk, Tomislav Debogovic, Maria Garcia Vigueras, Santiago Capdevila Cascante, Esteban Menargues Gomez

This paper reports a novel methodology to design broadband orthomode transducers with two arbitrarily spaced ports carrying orthogonal linear polarizations. The component is based on a combination of two Boifot junctions through a series of power dividers ...

2018

A Benchmark Comparison of Monocular Visual-Inertial Odometry Algorithms for Flying Robots

Davide Scaramuzza

Flying robots require a combination of accuracy and low latency in their state estimation in order to achieve stable and robust flight. However, due to the power and payload constraints of aerial platforms, state estimation algorithms must provide these qu ...

2018

A Scale-out Blockchain for Value Transfer with Spontaneous Sharding

Kelong Cong

Bitcoin, as well as many of its successors, require the whole transaction record to be reliably acquired by all nodes to prevent double-spending. Recently, many blockchains have been proposed to achieve scale-out throughput by letting nodes only acquire a ...

IEEE2018

Proactive Synthesis of Recursive Tree-to-String Functions from Examples

Viktor Kuncak, Mikaël Mayer, Jad Hamza

Synthesis from examples enables non-expert users to generate programs by specifying examples of their behavior. A domain-specific form of such synthesis has been recently deployed in a widely used spreadsheet software product. In this paper we contribute t ...

2017

Optimal Software Patching Plan for PMUs

Jean-Yves Le Boudec, Ola Nils Anders Svensson, Teklemariam Tsegay Tesfay

Phasor measurement units (PMUs) deployed to monitor the state of an electrical grid need to be patched from time to time to prevent attacks that exploit vulnerabilities in the software. Applying some of these patches requires a PMU reboot, which takes the ...

2017

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

On verifying causal consistency

Rachid Guerraoui, Jad Hamza

Causal consistency is one of the most adopted consistency criteria for distributed implementations of data structures. It ensures that operations are executed at all sites according to their causal precedence. We address the issue of verifying automaticall ...

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.