Publications related to The Complexity of Asynchronous Byzantine Consensus

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

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Serge Vaudenay, Fatma Betül Durak

Feistel Networks (FN) are now being used massively to encrypt credit card numbers through format-preserving encryption. In our work, we focus on FN with two branches, entirely unknown round functions, modular additions (or other group operations), and when ...

2018

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Serge Vaudenay, Fatma Betül Durak

Feistel Networks (FN) are now being used massively to encrypt credit card numbers through format-preserving encryption. In our work, we focus on FN with two branches, entirely unknown round functions, modular additions (or other group operations), and when ...

ePrint2018

Asynchronous Byzantine Machine Learning (the case of SGD)

Rachid Guerraoui, Mahsa Taziki, El Mahdi El Mhamdi, Rhicheek Patra, Georgios Damaskinos

Asynchronous distributed machine learning solutions have proven very effective so far, but always assuming perfectly functioning workers. In practice, some of the workers can however exhibit Byzantine behavior, caused by hardware failures, software bugs, c ...

2018

General Proximal Gradient Method: A Case for Non-Euclidean Norms

Volkan Cevher, Ya-Ping Hsieh, Marwa El Halabi, Cong Bang Vu, Van Quang Nguyen

In this paper, we consider composite convex minimization problems. We advocate the merit of considering Generalized Proximal gradient Methods (GPM) where the norm employed is not Euclidean. To that end, we show the tractability of the general proximity ope ...

2017

On solving LPN using BKW and variants Implementation and Analysis

Serge Vaudenay, Sonia Mihaela Bogos, Florian Tramèr

The Learning Parity with Noise problem (LPN) is appealing in cryptography as it is considered to remain hard in the post-quantum world. It is also a good candidate for lightweight devices due to its simplicity. In this paper we provide a comprehensive anal ...

Springer2016

A Composition Theorem for Conical Juntas

Mika Tapani Göös

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2016

A Thrifty Universal Construction

Rachid Guerraoui, Cheng Wang

A universal construction is an algorithm which transforms any sequential implementation of an object into a concurrent implementation of that same object in a linearizable and wait-free manner. Such constructions require underlying low-level universal shar ...

2015

Category Attentional Search for Fast Object Detection by Mimicking Human Visual Perception

Kwang Moo Yi

In this paper, we propose a novel selective search method to speed up the object detection via category-based attention scheme. The proposed attentional searching strategy is designed to focus on a small set of selected regions where the object category is ...

IEEE2015

Beyond One Third Byzantine Failures

Rachid Guerraoui, Anne-Marie Kermarrec, Cheng Wang

The Byzantine agreement problem requires a set of

n

processes to agree on a value sent by a transmitter, despite a subset of

b

processes behaving in an arbitrary, i.e. Byzantine, manner and sending corrupted messages to all processes in the system. It ...

2015

The Complexity of Asynchronous Byzantine Consensus

Graph Chatbot

Chat with Graph Search

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Asynchronous Byzantine Machine Learning (the case of SGD)

General Proximal Gradient Method: A Case for Non-Euclidean Norms

On solving LPN using BKW and variants Implementation and Analysis

A Composition Theorem for Conical Juntas

A Thrifty Universal Construction

Category Attentional Search for Fast Object Detection by Mimicking Human Visual Perception

Beyond One Third Byzantine Failures

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

General Proximal Gradient Method: A Case for Non-Euclidean Norms

On solving LPN using BKW and variants Implementation and Analysis

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

A Thrifty Universal Construction

Category Attentional Search for Fast Object Detection by Mimicking Human Visual Perception

A Composition Theorem for Conical Juntas

Beyond One Third Byzantine Failures

Asynchronous Byzantine Machine Learning (the case of SGD)