Publications related to BPP (complexity)

Sub-Logarithmic Test-and-Set Against a Weak Adversary

A randomized implementation is given of a test-and-set register with O(log log it) individual step complexity and O(n) total step complexity against an oblivious adversary. The implementation is linearizable and multi-shot, and shows an exponential complex ...

Springer-Verlag Berlin2011

The Complexity of Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of Omega(k) process steps for deterministic renaming into ...

Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa2011

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Seth Gilbert, Dan Alistarh, Morteza Zadimoghaddam

We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of

n

processes with step complexity $ ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011

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

Anastasios Kyrillidis

The maximization of a positive (semi) definite complex quadratic form over a finite alphabet is NP-hard and achieved through exhaustive search when the form has full rank. However, if the form is rank-deficient, the optimal solution can be computed with on ...

IEEE2011

An algorithmic decomposition of claw-free graphs leading to an O(n^3) algorithm for the weighted stable set problem

Yuri Faenza, Gautier Stauffer

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(n^3)-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free ...

2011

Graph-based classification of multiple observation sets

Pascal Frossard, Effrosyni Kokiopoulou

We consider the problem of classification of multiple observations of the same object, possibly under different transformations. We view this problem as a special case of semi-supervised learning where all unlabelled examples belong to the same unknown cla ...

Elsevier2010

Mutual information measures for subclass error-correcting output codes classification

Nikolaos Arvanitopoulos Darginis

Error-Correcting Output Codes (ECOCs) reveal a common way to model multi-class classification problems. According to this state of the art technique, a multi-class problem is decomposed into several binary ones. Additionally, on the ECOC framework we can a ...

2010

Subclass error correcting output codes using fisher's linear discriminant ratio

Nikolaos Arvanitopoulos Darginis

Error-Correcting Output Codes (ECOC) with subclasses reveal a common way to solve multi-class classification problems. According to this approach, a multiclass problem is decomposed into several binary ones based on the maximization of the mutual informati ...

2010

Collision Attacks against the Knudsen-Preneel Compression Functions

Martijn Stam, Onur Özen

Knudsen and Preneel (Asiacrypt'96 and Crypto'97) introduced a hash function design in which a linear error-correcting code is used to build a wide-pipe compression function from underlying blockciphers operating in Davies-Meyer mode. Their main design goal ...

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

A Randomized Countermeasure Against Parasitic Adversaries in Wireless Sensor Networks

Jean-Pierre Hubaux, Panagiotis Papadimitratos, Jun Luo

Due to their limited capabilities, wireless sensor nodes are subject to physical attacks that are hard to defend against. In this paper, we first identify a typical attacker, called parasitic adversary, who seeks to exploit sensor networks by obtaining mea ...

2010

BPP (complexity)

Graph Chatbot

Chat with Graph Search

Sub-Logarithmic Test-and-Set Against a Weak Adversary

The Complexity of Renaming

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

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

An algorithmic decomposition of claw-free graphs leading to an O(n^3) algorithm for the weighted stable set problem

Graph-based classification of multiple observation sets

Mutual information measures for subclass error-correcting output codes classification

Subclass error correcting output codes using fisher's linear discriminant ratio

Collision Attacks against the Knudsen-Preneel Compression Functions

A Randomized Countermeasure Against Parasitic Adversaries in Wireless Sensor Networks

The Complexity of Renaming

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Mutual information measures for subclass error-correcting output codes classification

Graph-based classification of multiple observation sets

An algorithmic decomposition of claw-free graphs leading to an O(n^3) algorithm for the weighted stable set problem

A Randomized Countermeasure Against Parasitic Adversaries in Wireless Sensor Networks

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

Subclass error correcting output codes using fisher's linear discriminant ratio

Collision Attacks against the Knudsen-Preneel Compression Functions

Sub-Logarithmic Test-and-Set Against a Weak Adversary