Concept

P versus NP problem

Related publications (252)

A Truthful, Privacy-Preserving, Approximately Efficient Combinatorial Auction For Single-minded Bidders

Boi Faltings, Sujit Prakash Gujar, Sankarshan Damle

Combinatorial auctions are widely used to sell resources/items. The challenges in such auctions are multi-fold. We need to ensure that bidders, the strategic agents, bid their valuations truthfully to the auction mechanism. Besides, the agents may desire p ...

ASSOC COMPUTING MACHINERY2019

Hardness Results for Consensus-Halving

Jie Zhang, Aris Filos Ratsikas

The Consensus-halving problem is the problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions. We study the epsilon-approximate version, which allows each agent to have an epsilon discrepancy on t ...

Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik2018

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

Method and device for proving his identity

Serge Vaudenay, Ioana Cristina Carlson

The invention is related to a method allowing a prover holding a secret key (x) to prove its identity to a verifier and to prove to this verifier that he is within a predetermined distance of this verifier, said method comprising an initialization phase du ...

2018

Block Oriented Programming: Automating Data-Only Attacks

Mathias Josef Payer

With the widespread deployment of Control-Flow Integrity (CFI), control-flow hijacking attacks, and consequently code reuse attacks, are significantly more difficult. CFI limits control flow to well-known locations, severely restricting arbitrary code exec ...

ASSOC COMPUTING MACHINERY2018

Satisfiability-Based Methods for Digital Circuit Design, Debug, and Optimization

Andrew James Becker

Designing digital circuits well is notoriously difficult. This difficulty stems in part from the very many degrees of freedom inherent in circuit design, typically coupled with the need to satisfy various constraints. In this thesis, we demonstrate how for ...

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

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

A unified framework for rich routing problems with stochastic demands

Michel Bierlaire, Sacha Varone, Mohammad Yousef Maknoon, Iliya Dimitrov Markov

We introduce a unified framework for rich vehicle and inventory routing problems with complex physical and temporal constraints. Demands are stochastic, can be non-stationary, and are forecast using any model that provides the expected demands and their er ...

2017

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

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.