Concept

Complete (complexity)

Related publications (32)

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.

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Tensor-Based Numerical Method For Stochastic Homogenization

This paper addresses the complexity reduction of stochastic homogenization of a class of random materials for a stationary diffusion equation. A cost-efficient approximation of the correctors is obtained using a method designed to exploit quasi-periodicity ...

SIAM PUBLICATIONS2022

cRacklet: a spectral boundary integral method library for interfacial rupture simulation

Jean-François Molinari, Thibault Didier Roch, Fabian Barras

The study of dynamically propagating rupture along interfaces is of prime importance in various fields and system sizes, including tribology (nm to m), engineering (mm to m) and geophysics (m to km) (Armstrong-Hélouvry et al., 1994; Ben-Zion, 2008; Vanossi ...

2022

Adversarial training with informed data selection

Pascal Frossard, Javier Alejandro Maroto Morales, Marcele Oliveira Kuhfuss de Mendonça

With the increasing amount of available data and advances in computing capabilities, deep neural networks (DNNs) have been successfully employed to solve challenging tasks in various areas, including healthcare, climate, and finance. Nevertheless, state-of ...

IEEE2022

A method for faster application of process integration techniques in retrofit situations

Numerous process integration techniques were proved to be highly effective for identifying and estimating potential energy savings in the industry. However, they require high time and effort to collect and analyse process data. As a result, they do not con ...

ELSEVIER SCI LTD2021

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem

Mika Tapani Göös

We study the search problem class PPA_q defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p. ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2020

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...

ASSOC COMPUTING MACHINERY2020

Fast Block Sequential Decoding of Polar Codes

Kirill Ivanov

A reduced complexity sequential decoding algorithm for polar (sub) codes is described. The proposed approach relies on a decomposition of the polar (sub) code being decoded into a number of outer codes, and on-demand construction of codewords of these code ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches

Aris Filos Ratsikas

We resolve the computational complexity of two problems known as NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the ...

ACM2019

Improved decoding of second-order Reed-Muller codes

Rüdiger Urbanke, Kirill Ivanov

In this paper, we consider low-complexity decoding of second-order Reed-Muller codes. A class of polynomial-time algorithms, based on the projections onto first-order codes, is studied. An old representative of this class, originally developed for binary s ...

IEEE2019