4 papers
Smoothed analysis of policy iteration and value iteration for deterministic discounted and mean-payoff games played on any graph
Bruno Loff, Mateusz Skomra
Our understanding of turn-based stochastic games is reminiscent of our understanding of linear programming in the 1970s. Instead of the simplex method, we have two families of algo…
Key-agreement exists if and only if the "interactive vs non interactive Kolmogorov problem" is not in ioBPP: a short proof
Bruno Bauwens, Bruno Loff
Ball, Liu, Mazor and Pass proved that the existence of key-agreement protocols is equivalent to the hardness of a certain problem about interactive Kolmogorov complexity. We genera…
A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
Pavel Dvořák, Bruno Loff, Suhail Sherif
We study semidefinite relaxations of combinatorial statements. By relaxing the pigeonhole principle, we obtain a new "quantum" pigeonhole principle which is a stronger statem…
Smoothed analysis of deterministic discounted and mean-payoff games
Bruno Loff, Mateusz Skomra
We devise a policy-iteration algorithm for deterministic two-player discounted and mean-payoff games, that runs in polynomial time with high probability, on any input where each pa…