Concept

Complete (complexity)

Related publications (42)

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.

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

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

A Tight Lower Bound for Entropy Flattening

Mika Tapani Göös, Jiapeng Zhang

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

Level crossings induced by a longitudinal coupling in the transverse field Ising chain

Frédéric Mila, Grégoire Vionnet

We study the effect of antiferromagnetic longitudinal coupling on the one-dimensional transverse field Ising model with nearest-neighbor couplings. In the topological phase where, in the thermodynamic limit, the ground state is twofold degenerate, we show ...

2017

The isostatic 3-body problem: a complete solution

Simon Nessim Henein, Florent Cosandier, Ilan Vardi, François Barrot, Johannes Richard Cornelis Geerit Kruis

Kinematic couplings are used when two rigid bodies need to be repeatedly and accurately positioned with respect to each other. They allow for sub-micron positioning repeatability by suppressing play and reducing strains in the bodies. Typical applications ...

2017

LPN in Cryptography

Sonia Mihaela Bogos

The security of public-key cryptography relies on well-studied hard problems, problems for which we do not have efficient algorithms. Factorization and discrete logarithm are the two most known and used hard problems. Unfortunately, they can be easily solv ...

EPFL2017

Progressive Geometric Algorithms

Timur Bagautdinov

Progressive algorithms are algorithms that, on the way to computing a complete solution to the problem at hand, output intermediate solutions that approximate the complete solution increasingly well. We present a framework for analyzing such algorithms, an ...

Carleton Univ, Dept Mathematics & Statistics2015

An optimization framework for the development of efficient one-way car-sharing systems

Nikolaos Geroliminis, Burak Boyaci, Konstantinos Zografos

Electric vehicle-sharing systems have been introduced to a number of cities as a means of increasing mobility, reducing congestion, and pollution. Electric vehicle-sharing systems can offer one or two-way services. One-way systems provide more flexibility ...

Elsevier2015

Learning decision rules for energy efficient building control

Colin Neil Jones

While rule based control (RBC) is current practice in most building automation systems that issue discrete control signals, recent simulation studies suggest that advanced, optimization based control methods such as hybrid model predictive control (HMPC) c ...

Elsevier2014