Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching…
Our results are: ** Introduce the problem of finding stable matchings that are robust to errors in the input. ** An efficient algorithm for the following class of errors: Permute arbitrarily the preference list of…
Microsoft is a Silver sponsor of the Federated Logic Conference 2018 (FLoC 2018) July 6–9, 2018 at a variety of venues in Oxford, UK.
Common-sense physical reasoning is facilitated by representing sensory percepts into discrete objects. By decomposing a complex visual scene into distinct objects, humans can describe relations between the objects and reason about their dynamics as well…
Matrix completion is a well-studied problem with many machine learning applications. In practice, the problem is often solved by non-convex optimization algorithms. However, the current theoretical analysis for non-convex algorithms relies heavily on the assumption…
