Dispersion of Mass and the Complexity of Randomized Algorithms

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


Duration: 59:33
62 views
2

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness probably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in R^n (the current best algorithm has complexity roughly n^4 and is conjectured to be n^3). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body, are of independent interest and applicable more generally; in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing. This is joint work with Luis Rademacher.



Other Videos By Microsoft Research


2016-09-06SCS '06 - Microsoft Research Welcome
2016-09-06Enhancing Text Representation through Knowledge-Based Feature Generation [1/12]
2016-09-06SCS '06 - Icebreaker - Part 2
2016-09-06SCS '06 - Lightning Round 1: Learning in and about Virtual Worlds - Talk 2
2016-09-06SCS '06 - Lightning Round 1: Learning in and about Virtual Worlds - Talk 3
2016-09-06Refinding Information on the Web: What do we do?
2016-09-06SCS '06 - Lightning Round 1: Learning in and about Virtual Worlds - Talk 1
2016-09-06Edgenet 2006 - A Data Model for Policy
2016-09-06Why People Around the World Really Are Different, and the Hidden Clues to Understanding Us All [1/2]
2016-09-06SCS '06 - Introductions and Icebreaker - Part 1
2016-09-06Dispersion of Mass and the Complexity of Randomized Algorithms
2016-09-06Edgenet 2006 - Experimental Design for Flexible Network Diagnosis
2016-09-06Edgenet 2006 - Experiences Managing Networks in IBM HPC Grid Infrastructure and Enterprise VoIP
2016-09-06Edgenet 2006 - Is an Office Without Wires Feasible?
2016-09-06Applications of First-order Integer Arithmetic to the Verification of Programs with Lists
2016-09-06Pushing Group Communication to the Edge Will Enable Radically New Distributed Applications
2016-09-06Edgenet 2006 - Virtual LAN as a Network Control Mechanism
2016-09-06Edgenet 2006 - New Directions in Enterprise Network Management
2016-09-06Edgenet 2006 - Problems and Solutions in Enterprise Network Control
2016-09-06Memex Summit (Digital Memories Workshop) - Digital Memories Software
2016-09-06Brain Computer Interface Systems: Progress and Opportunities


Tags:
microsoft research