Title: A Fixed-Point Approach to Stable MatchingsSpeaker: Akshay Ramachandran Affiliation: University of Waterloo Room: MC 5479
This talk will be independent of the previous reading group talk. Three classical results in stable matching are the correctness of Gale Shapley’s deferred acceptance algorithm, the result of Conway that Stable Matchings form a distributive lattice, and Vande Vate and later Rothblum’s result that the convex hull of stable matchings has a polynomial-sized linear description.
Title: Quantum Log-Approximate-Rank Conjecture is also FalseSpeaker: Anurag Anshu Affiliation: Institute for Quantum Computing - University of Waterloo Room: MC 5501
In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function `f', hence refuting the log approximate rank conjecture of Lee and Shraibman .