On the Number of Matroids

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=5RGBE1HbYkU


Duration: 54:03
438 views
6

I will talk about some recent results on upper bounding the number of matroids on a ground set of size n. The talk will consist of two parts. First, I will describe a technique for bounding the number of stable sets in a graph, where one uses the spectral properties of the graph to represent every stable set using few bits. Second, we will see how this idea, together with some basic properties of matroids, can be used to obtain a compressed representation for any matroid. Our bound substantially improves the previous results and comes quite close to the known lower bound on the number of matroids. Joint work with Rudi Pendavingh and Jorn van der Pol.



Other Videos By Microsoft Research


2016-07-26Analyzing neurological disorders using functional and structural brain imaging data
2016-07-26Collaborative, Large-Scale Data Analytics and Visualization with Python
2016-07-26Gap Probabilities for Zeroes of Stationary Gaussian Functions
2016-07-26Random Walks on Groups and the Kaimanovich-Vershik Conjecture for Lamplighter Groups
2016-07-26Sensing without Sensors
2016-07-26Optimal Falsifications for Cyber-Physical Systems using Trajectory Splicing
2016-07-26A Sensor Fusion Approach towards Gesture Recognition on the Wearable Ring Form Factor
2016-07-26Digital Traces in Online Places: Methods, Software, and Applications for Social Behavioral Research
2016-07-26Stabilizer: Statistically Sound Performance Evaluation
2016-07-26Revenue maximization and prophet inequalities
2016-07-26On the Number of Matroids
2016-07-26RealTime Collaborative Analysis with (Almost) Pure SQL: A Case Study in Biogeochemical Oceanography
2016-07-26Who is Afraid of Vectors�Optimizing Cryptography Using SSE, AVX, NEON, and Co.
2016-07-26Programming with People: Integrating Human-Based and Digital Computation
2016-07-26ISHI Connects Us: Social Gaming with the Skype Team
2016-07-26Monitoring the Snowpack in Remote, Ungauged Mountains from Satellite and Computers
2016-07-26A Logical Revolution
2016-07-26Online Node-weighted Steiner Forest and Extensions
2016-07-26Optimal Pairings on Abelian Varieties with Theta Functions
2016-07-26Using Crowd Agents to Create Deployable Intelligent Systems
2016-07-26Quantum Speedup by Quantum Annealing


Tags:
microsoft research