Mathematics
Anthropomorphising AI Is an Impediment to a Stable Society
Computation, unlike mathematics, is a physical process that takes time, energy, and space. Humans have dominated this planet’s ecosystem by learning to share and consolidate the outcome of their computation in an unprecedented way. Now…
The Matching Problem in General Graphs is in Quasi-NC
We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in polylogarithmic time on quasi-polynomially many processors. The result is obtained by…
The Emerging Theory of Algorithmic Fairness
As algorithms reach ever more deeply into our daily lives, increasing concern that they be “fair” has resulted in an explosion of research in the theory and machine learning communities. This talk surveys key results…
A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of…
Planar Graph Perfect Matching is in NC
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…
Distributive Lattices, Stable Matchings, and Robust Solutions
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 @ FLoC 2018
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.
