Publications related to Factorial Lower Bounds for (Almost) Random Order Streams

Related publications (25)

Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement

Rachid Guerraoui, Jovan Komatovic, Manuel José Ribeiro Vidigueira, Pierre Philippe Civit

Byzantine agreement allows n processes to decide on a common value, in spite of arbitrary failures. The seminal Dolev-Reischuk bound states that any deterministic solution to Byzantine agreement exchanges Ω(n2) bits. In synchronous networks, with a known u ...

Society for Industrial and Applied Mathematics2025

Singular quadratic eigenvalue problems: linearization and weak condition numbers

Ivana Sain Glibic, Daniel Kressner

The numerical solution of singular eigenvalue problems is complicated by the fact that small perturbations of the coefficients may have an arbitrarily bad effect on eigenvalue accuracy. However, it has been known for a long time that such perturbations are ...

SPRINGER2023

The JPEG AI Standard: Providing Efficient Human and Machine Visual Data Consumption

Touradj Ebrahimi

The Joint Photographic Experts Group (JPEG) AI learning-based image coding system is an ongoing joint standardization effort between International Organization for Standardization (ISO), International Electrotechnical Commission (IEC), and International Te ...

IEEE COMPUTER SOC2023

Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution

Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen

Semi-discrete optimal transport problems, which evaluate the Wasserstein distance between a discrete and a generic (possibly non-discrete) probability measure, are believed to be computationally hard. Even though such problems are ubiquitous in statistics, ...

2023

On the Validity of Consensus

Rachid Guerraoui, Seth Gilbert, Jovan Komatovic, Manuel José Ribeiro Vidigueira, Pierre Philippe Civit

The Byzantine consensus problem involves.. processes, out of which t < n could be faulty and behave arbitrarily. Three properties characterize consensus: (1) termination, requiring correct (nonfaulty) processes to eventually reach a decision, (2) agreement ...

Assoc Computing Machinery2023

Human-machine interface for two-dimensional steering control with the auricular muscles

Daniel Jose Lins Leal Pinheiro, Silvestro Micera, Solaiman Shokur

Human-machine interfaces (HMIs) can be used to decode a user's motor intention to control an external device. People that suffer from motor disabilities, such as spinal cord injury, can benefit from the uses of these interfaces. While many solutions can be ...

FRONTIERS MEDIA SA2023

Some Physical Implications Of Absolute Geometries In The Description Of Complex Systems Dynamics

Maria-Alexandra Paun

Some implications of absolute geometries in the description of complex systems dynamics, at various scale resolutions are highlighted. In such context, by means of an analytic geometry of 2 x 2 matrices, a generalization of the standard velocities space in ...

UNIV POLITEHNICA BUCHAREST, SCI BULL2023

A stable loosely-coupled scheme for cardiac electro-fluid-structure interaction

Alfio Quarteroni

We present a loosely coupled scheme for the numerical simulation of the cardiac electrofluid-structure interaction problem, whose solution is typically computationally intensive due to the need to suitably treat the coupling of the different submodels. Our ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2023

Distribution Inference Risks: Identifying and Mitigating Sources of Leakage

Robert West, Maxime Jean Julien Peyrard, Valentin Hartmann

A large body of work shows that machine learning (ML) models can leak sensitive or confidential information about their training data. Recently, leakage due to distribution inference (or property inference) attacks is gaining attention. In this attack, the ...

IEEE COMPUTER SOC2023

OSLO: On-the-Sphere Learning for Omnidirectional Images and Its Application to 360-Degree Image Compression

Pascal Frossard, Thomas Maugey, Roberto Gerson De Albuquerque Azevedo

State-of-the-art 2D image compression schemes rely on the power of convolutional neural networks (CNNs). Although CNNs offer promising perspectives for 2D image compression, extending such models to omnidirectional images is not straightforward. First, omn ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

FLEET: Online Federated Learning via Staleness Awareness and Performance Prediction

Rachid Guerraoui, Anne-Marie Kermarrec, Rhicheek Patra

Federated learning (FL) is very appealing for its privacy benefits: essentially, a global model is trained with updates computed on mobile devices while keeping the data of users local. Standard FL infrastructures are however designed to have no energy or ...

ASSOC COMPUTING MACHINERY2022

A chance-constraint approach for optimizing Social Engagement-based services

Michel Bierlaire

Social Engagement is a novel business model transforming final users of a service from passive into active components. In this framework, people are contacted by a company and they are asked to perform tasks in exchange for a reward. This arises the compli ...

IEEE2022

On the transition times in a loss model of wireless networks

Patrick Thiran

SPRINGER2022

Preface-Special Issue on Misinformation on the Web

Karl Aberer, Quoc Viet Hung Nguyen

PERGAMON-ELSEVIER SCIENCE LTD2022

Putting ridesharing to the test: efficient and scalable solutions and the power of dynamic vehicle relocation

Boi Faltings, Panayiotis Danassis, Marija Sakota

We study the optimization of large-scale, real-time ridesharing systems and propose a modular design methodology, Component Algorithms for Ridesharing (CAR). We evaluate a diverse set of CARs (14 in total), focusing on the key algorithmic components of rid ...

SPRINGER2022

A Modular Workflow for Model Building, Analysis, and Parameter Estimation in Systems Biology and Neuroscience

Daniel Keller

Neuroscience incorporates knowledge from a range of scales, from single molecules to brain wide neural networks. Modeling is a valuable tool in understanding processes at a single scale or the interactions between two adjacent scales and researchers use a ...

HUMANA PRESS INC2022

tweedledum: A Compiler Companion for Quantum Computing

Giovanni De Micheli, Bruno Schmitt Antunes

This work presents tweedledum-an extensible open-source library aiming at narrowing the gap between high-level algorithms and physical devices by enhancing the expressive power of existing frameworks. For example, it allows designers to insert classical lo ...

IEEE2022

High-order accurate entropy stable adaptive moving mesh finite difference schemes for special relativistic (magneto)hydrodynamics

Junming Duan

This paper develops high-order accurate entropy stable (ES) adaptive moving mesh finite difference schemes for the two- and three-dimensional special relativistic hydrodynamic (RHD) and magnetohydrodynamic (RMHD) equations, which is the high-order accurate ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2022

BLURtooth: Exploiting Cross-Transport Key Derivation in Bluetooth Classic and Bluetooth Low Energy

Mathias Josef Payer, Daniele Antonioli

Bluetooth is a pervasive wireless technology specified in an open standard. The standard defines Bluetooth Classic (BT) for high-throughput wireless services and Bluetooth Low Energy (BLE) very low-power ones. The standard also specifies security mechanism ...

ASSOC COMPUTING MACHINERY2022

Unbiased Inverse Volume Rendering with Differential Trackers

Wenzel Alban Jakob, Merlin Eléazar Nimier-David

Volumetric representations are popular in inverse rendering because they have a simple parameterization, are smoothly varying, and transparently handle topology changes. However, incorporating the full volumetric transport of light is costly and challengin ...

ASSOC COMPUTING MACHINERY2022