Hardness of Online Sleeping Combinatorial Optimization Problems
  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 Online Shortest Paths, Online Minimum
Spanning Tree, Online $k$-Subsets, Online $k$-Truncated Permutations, Online
Minimum Cut, and Online Bipartite Matching. 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).
