Publication

Strategy construction for parity games with imperfect information

Publications associées (31)

Robust Collaborative Learning with Linear Gradient Overhead

Rachid Guerraoui, Le Nguyen Hoang, John Stephan, Sadegh Farhadkhani, Nirupam Gupta, Rafaël Benjamin Pinot

Collaborative learning algorithms, such as distributed SGD (or D-SGD), are prone to faulty machines that may deviate from their prescribed algorithm because of software or hardware bugs, poisoned data or malicious behaviors. While many solutions have been ...

PLMR2023

Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update

Efstratios Panteleimon Skoulakis

In this paper we provide a novel and simple algorithm, Clairvoyant Multiplicative Weights Updates (CMWU), for convergence to \textit{Coarse Correlated Equilibria} (CCE) in general games. CMWU effectively corresponds to the standard MWU algorithm but where ...

2022

Reduced representations of complexes, signals, and multifiltrations

Celia Camille Hacker

The field of computational topology has developed many powerful tools to describe the shape of data, offering an alternative point of view from classical statistics. This results in a variety of complex structures that are not always directly amenable for ...

EPFL2022

Invariant integrals on topological groups

Vasco Schiavo

We generalize the fixed-point property for discrete groups acting on convex cones given by Monod in [23] to topological groups. At first, we focus on describing this fixed-point property from a functional point of view, and then we look at the class of gro ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2022

Learning V1 Simple Cells with Vector Representation of Local Content and Matrix Representation of Local Motion

Yufan Ren, Siyuan Huang

This paper proposes a representational model for image pairs such as consecutive video frames that are related by local pixel displacements, in the hope that the model may shed light on motion perception in primary visual cortex (V1). The model couples the ...

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2022

Hybrid Flock - Formation Control Algorithms

Alcherio Martinoli, Cyrill Silvan Baumann, Jonas Perolini, Emna Tourki

Two prominent categories for achieving coordinated multirobot displacement are flocking and navigation in formation. Both categories have their own body of literature and characteristics, including their respective advantages and disadvantages. While typic ...

Springer Nature Switzerland2022

Approximate CVPp in time 2(0.802n)

Friedrich Eisenbrand, Moritz Andreas Venzin

We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2022

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Adam Teodor Polak, Alexandra Anna Lassota

We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...

Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Viktor Kuncak, Simon Guilloud

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...

Springer2022

Geometrical Treatise on the Modelling of 3D Particulate Inclusion-Matrix Microstructures with an Application to Historical Stone Masonry Walls

Mahmoud S. M. Shaqfa

As historical stone masonry structures are vulnerable and prone to damage in earthquakes, investigating their structural integrity is important to reduce injuries and casualties while preserving their historical value. Stone masonry is a composite material ...

EPFL2022

Attacks on some post-quantum cryptographic protocols: The case of the Legendre PRF and SIKE

Novak Kaluderovic

Post-quantum cryptography is a branch of cryptography which deals with cryptographic algorithms whose hardness assumptions are not based on problems known to be solvable by a quantum computer, such as the RSA problem, factoring or discrete logarithms. This ...

EPFL2022