Abstract 

We show that several online combinatorial optimization problems that admit efficient no-regret algorithms become computationally hard in the sleeping setting where a subset of actions becomes unavailable in each round. Specifically, we show that the sleeping versions of these problems are at least as hard as PAC learning DNF expressions, a long standing open problem. We show hardness for the sleeping versions of O NLINE S HORTEST PATHS, O NLINE M INIMUM S PANNING T REE, O NLINE k-S UBSETS, O NLINE k-T RUNCATED P ERMUTATIONS, O NLINE M INIMUM C UT, and O NLINE B IPARTITE M ATCHING. The hardness result for the sleeping version of the Online Shortest Paths problem resolves an open problem presented at COLT 2015 [Koolen et al., 2015].