Concept

Problème P ≟ NP

Publications associées (252)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Neural Anisotropy Directions

Pascal Frossard, Seyed Mohsen Moosavi Dezfooli, Guillermo Ortiz Jimenez, Apostolos Modas

In this work, we analyze the role of the network architecture in shaping the inductive bias of deep classifiers. To that end, we start by focusing on a very simple problem, i.e., classifying a class of linearly separable distributions, and show that, depen ...

2020

On the effect of ligand shell heterogeneity on nanoparticle/protein binding thermodynamics

Francesco Stellacci, Ahmet Bekdemir, Suiyang Liao

Nonspecific protein adhesion to nanoparticle (NP) has been proven to have important implications in nanomedicine. However, there are only a few examples of careful studies relating protein binding thermodynamics to NP physicochemical features. In particula ...

2019

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

Modeling Superlattices of Dipolar and Polarizable Semiconducting Nanoparticles

Federico Giberti

We present an analytical model to describe the stability of arbitrary semiconducting nanoparticle (NP) superlattices as a function of the dipole and polarizability of their constituents. We first validate our model by comparison with density functional the ...

AMER CHEMICAL SOC2019

An Interactive Gameplay to Crowdsource Multiple Sequence Alignment of Genome Sequences: Genenigma

Comparative genomics is a field of research that compares genomes of different organisms to identify common patterns. It is a powerful method used to identify the genetic diseases that cause mutations. Multiple Sequence Alignment (MSA) is an intermediate s ...

ASSOC COMPUTING MACHINERY2019

Adaptive Streaming in Interactive Multiview Video Systems

Pascal Frossard, Laura Toni, Xue Zhang, Yao Zhao

Multiview applications endow final users with the possibility to freely navigate within 3D scenes with minimum-delay. A real feeling of scene navigation is enabled by transmitting multiple high-quality camera views, which can be used to synthesize addition ...

2019

We consider the problem of designing a stabilizing and optimal static controller with a pre-specified sparsity pattern. Since this problem is NP-hard in general, it is necessary to resort to approximation approaches. In this paper, we characterize a class ...

IEEE2019

Graph fragmentation problem: analysis and synthesis

Manuel Francesco Aprile

Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to a network. The graph fragmentation problem (GFP) is the result of a worst-case analysis of a random attack. We can choose a fixed number of indivi ...

WILEY2019

On the Computational Complexity of Blind Detection of Binary Linear Codes

Alexios Konstantinos Balatsoukas Stimming, Aris Filos Ratsikas

In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes C of a given dimension k, for which t ...

IEEE2019

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019