Showing 2024Show all
2 papers · 1 filter
cs.CC2024
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…
cs.GT2024
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…