Big Data All Hands Meeting

Mary Wootters (University of Michigan)
One-bit Matrix Completion

I'll describe a theory of matrix completion for noisy, one-bit measurements.  Instead of observing a few real-valued entrie of a low-rank matrix M (as one does in standard matrix completion), we observe a few coin flips, which come from a distribution parameterized by M. A natural application of this model is rating data, say on Pandora (internet radio).  Users' preferences for songs form a low-rank matrix, but we never observe it---we see only "thumbs up" or "thumbs down," and the probability of a "thumbs up" is higher if a user's true preference for a song is higher.   I'll show (or at least assert, given time constraints) that under reasonable conditions, one can efficiently fill in the missing ratings and also recover M.  This is joint work with Mark Davenport, Yaniv Plan, and Ewout van den Berg.

Ely Porat (Bar-Ilan University)
Orienting Fully Dynamic Graphs of Low Arboricity with Worst-Case Time Bounds

Consider an undirected graph G that has bounded arboricity – which includes all planar and excluded-minor graphs – and is fully dynamic i.e., admits edge insertions and deletions. We devise an algorithm that maintains an orientation of the graph’s edges such that the maximum out-degree is always bounded, and the running time of all update operations is bounded in the worst-case; in contrast, all previous non-trivial results bound the amortized update time. Specifically, our algorithm maintains a maximum out-degree ∆ ≤ infβ>1{β · α(G) + logβ n}, where α(G) is the graph’s arboricity, and n is its number of vertices. Moreover, each update changes the orientation of at most O(∆) edges, and the worst-case running time for insertion and deletion are O(∆2) and O(∆), respectively. In contrast with the previous (amortized) results, the algorithm is not required to know any bound on α(G).

Our results can be used in several dynamic graph problems to obtain worst-case time bounds instead of the current amortized time bounds.