Publication

On the Complexity of Recognizing Iterated Differences of Polyhedra

Related publications (41)

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 Minimal Complexity of Adapting Agents Increases with Fitness

What is the relationship between the complexity and the fitness of evolved organisms, whether natural or artificial? It has been asserted, primarily based on empirical data, that the complexity of plants and animals increases as their fitness within a part ...

Public Library Science2013

Neutralité et engagement. Les relations entre le Comité international de la Croix-Rouge et le gouvernement suisse pendant la Seconde Guerre mondiale

Isabelle Barbara Marie-Hélène Cardia

Since its creation in 1863, the ICRC has maintained a special relationship with Switzerland and its government, based on the pursuit of neutrality and on the perception of a common destiny. Such a perception and the adherence to shared political values wer ...

Société d'histoire de la Suisse romande2012

Complexity of the critical node problem over trees

Marco Di Summa

In this paper we deal with the critical node problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the (weighted or unweighted) number of connections between pairs of nodes in the residual graph. ...

2011

On the Construction of Polar Codes

Emre Telatar, Seyed Hamed Hassani, Ramtin Pedarsani

We consider the problem of efficiently constructing polar codes over binary memoryless symmetric (BMS) channels. The complexity of designing polar codes via an exact evaluation of the polarized channels to find which ones are "good" appears to be exponenti ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011

Repeater Insertion Techniques for 3D Interconnects

Giovanni De Micheli, Vasileios Pavlidis

A new approach for inserting repeaters in 3-D interconnects is proposed. The allocation of repeaters along an interplane interconnect is iteratively determined. The proposed approach is compared with two other techniques based on conventional methods used ...

2010

Iterative Demosaicking Accelerated: Theory and Fast Noniterative Implementations

Martin Vetterli, Yue Lu, Mina Karzand

Color image demosaicking is a key process in the digital imaging pipeline. In this paper, we present a rigorous treatment of a classical demosaicking algorithm based on alternating projections (AP). Since its publication, the AP algorithm has been widely c ...

2009

The Complexity of Distinguishing Distributions

Serge Vaudenay, Thomas Baignères

Cryptography often meets the problem of distinguishing distributions. In this paper we review techniques from hypothesis testing to express the advantage of the best distinguisher limited to a given number of samples. We link it with the Chernoff informati ...

Springer2008

A HW/SW codesign platform for Algorithm-Architecture mapping

Marco Mattavelli, Christophe Lucarz, Julien Dubois

The increasing complexity of signal processing algorithms has lead to the need of developing the algorithms specifications using generic software implementations that become in practice the reference implementation. This fact can be particularly observed i ...

2007

A profiling framework for high level design space exploration for memory and system architectures

In 1971, the first microprocessor produced in mass production had 2300 transistor and was able to compute 60'000 operations per second at 740 kHz. Nowadays, even a common gaming console uses a central unit including 243 millions of transistors running at 4 ...

EPFL2007

Reduced complexity attacks on the alternating step generator

Willi Meier, Shahram Khazaei, Simon Fischer

In this paper, we present some reduced complexity attacks on the Alternating Step Generator (ASG). The attacks are based on a quite general framework and mostly benefit from the low sampling resistance of the ASG, and of an abnormal behavior related to the ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2007