Publication

Rank-Deficient Quadratic-Form Maximization Over M-Phase Alphabet: Polynomial-Complexity Solvability And Algorithmic Developments

Publications associées (92)

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

TCHo: a Hardware-Oriented Trapdoor Cipher

Serge Vaudenay, Willi Meier, Jean-Philippe Aumasson

This paper improves the Finiasz-Vaudenay construction of TCHo, a hardware-oriented public-key cryptosystem, whose security relies in the hardness of finding a low-weight multiple of a given polynomial, and on the decoding of certain noisy cyclic linear cod ...

Springer2007

Conjunctive Queries over Trees

Christoph Koch

We study the complexity and expressive power of conjunctive queries over unranked labeled trees represented using a variety of structure relations such as "child'', "descendant'', and "following'' as well as unary relations for node labels. We establish a ...

2006

Precoloring with cliques and stable sets in cographs

Tinaz Ekim

Precoloring extension problems are known to be NP-complete in several classes of graphs. Here, we consider precolorings of cographs with not only stable sets but also with cliques. We give polynomial time algorithms to extend such a precoloring in an optim ...

2006

Three Algorithms for Interface Synthesis: A Comparative Study

Vasu Singh, Dirk Thilo Beyer

A temporal interface for a system component is a finite automaton that specifies the legal sequences of input events. We evaluate and compare three different algorithms for automatically extracting the temporal interface from the transition graph of a comp ...

2006

When Birds Die: Making Population Protocols Fault-tolerant

Rachid Guerraoui, Eric Ruppert

In the population protocol model introduced by Angluin et al. [2], a collection of agents, which are modelled by finite state machines, move around unpredictably and have pairwise interactions. The ability of such systems to compute functions on a multiset ...

2006

Synthesis of 4-nitrophenyl sulfones and application in the modified Julia olefination

Jieping Zhu

4-Nitrophenyl (NP) sulfones were successfully employed in the modified Julia olefination reaction with carbonyl compds. The olefination reaction proceeds through a sequence of aldol addn., Smiles rearrangement, and elimination. The sulfones are easily prep ...

2006

Failure Location in Transparent Optical Networks: The Asymmetry Between False and Missing Alarms

Patrick Thiran, Xuan Hung Nguyen

Failure location in transparent optical networks is difficult because of the large amount of alarms that a failure can trigger and because of corrupted alarms. One problem that network operators often face is how to set the thresholds in monitoring devices ...

2005

Erweiterung des Funktionalismus 1930-1950

Christoph Wieser

Functionalism serves as the guiding concept of this piece of work, on the example of which shall be traced the changes that took place in modern architecture between 1930 and 1950. This choice seems appropriate since Functionalism is a particularly relevan ...

EPFL2005

Active measurement for multiple link failure diganosis in IP networks

Patrick Thiran, Xuan Hung Nguyen

Simultaneous link failures are common in IP networks \cite{Markopoulou04}. In this paper, we develop a technique for locating multiple failures in Service Provider or Enterprise IP networks using active measurement. We propose a two-phased approach that mi ...

2004

Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm

Thomas Liebling, Jean-Albert Ferrez

We address the weighted max-cut problem, or equivalently the problem of maximizing a quadratic form in n binary variables. If the underlying (symmetric) matrix is positive semidefinite of fixed rank d, then the problem can be reduced to searching the extre ...

2004