1 citations · 1 across the 6 of their papers we have counts for
8 papers
Tight Lower Bounds for Algebraic Communication and Applications
Manon Blanc, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen +2
Communication complexity studies how much information must be exchanged to solve a problem whose input is split among two or more parties. In this work, we study an algebraic varia…
The complexity of computing in continuous time: space complexity is precision
Manon Blanc, Olivier Bournez
Models of computations over the integers are equivalent from a computability and complexity theory point of view by the Church-Turing thesis. It is not possible to unify discrete-t…
The domino problem is decidable for robust tilesets
Nathalie Aubrun, Manon Blanc, Olivier Bournez
One of the most fundamental problems in tiling theory is the domino problem: given a set of tiles and tiling rules, decide if there exists a way to tile the plane using copies of t…
Simulation of Turing machines with analytic discrete ODEs: FPTIME and FPSPACE over the reals characterised with discrete ordinary differential equations
Manon Blanc, Olivier Bournez
We prove that functions over the reals computable in polynomial time can be characterised using discrete ordinary differential equations (ODE), also known as finite differences. We…
Measuring robustness of dynamical systems. Relating time and space to length and precision
Manon Blanc, Olivier Bournez
Verification of discrete time or continuous time dynamical systems over the reals is known to be undecidable. It is however known that undecidability does not hold for various clas…
A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary differential equations
Manon Blanc, Olivier Bournez
In a recent article, the class of functions from the integers to the integers computable in polynomial time has been characterized using discrete ordinary differential equations (O…
Polynomial time computable functions over the reals characterized using discrete ordinary differential equations
Manon Blanc, Olivier Bournez
The class of functions from the integers to the integers computable in polynomial time has been characterized recently using discrete ordinary differential equations (ODE), also kn…
Computational Complexity of Multi-Player Evolutionarily Stable Strategies
Manon Blanc, Kristoffer Arnsfelt Hansen
In this paper we study the computational complexity of computing an evolutionary stable strategy (ESS) in multi-player symmetric games. For two-player games, deciding existence of…