Titlebook: Structural Information and Communication Complexity; 20th International C Thomas Moscibroda,Adele A. Rescigno Conference proceedings 2013 S

aquatic

Distributed Community Detection in Dynamic Graphs propose a distributed protocol based on the popular . and prove that, when the ratio ./. is larger than .. (for an arbitrarily small constant . > 0), the protocol finds the right “planted” partition in .(log.) time even when the snapshots of the dynamic graph are sparse and disconnected (i.e. in the case . = Θ(1/.)).

PHON

亲密

Non-Additive Two-Option Ski Rentalomized algorithms for the general setting and prove matching lower bounds on the competitive ratios for the problem. This is the first non-trivial result for the non-additive model of ski rental, which models non-refundable one-time costs.