Hardness of Approximation Between P and NP

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


Duration: 49:50
891 views
8

The first question we computer scientists ask when facing a new algorithmic challenge is: is it NP-hard, or is it in P? Surprisingly, for many important problems, the answer is "neither!" I will discuss recent progress towards understanding the complexity of those problems.

See more on this video at https://www.microsoft.com/en-us/research/video/hardness-approximation-p-np/



Other Videos By Microsoft Research


2016-12-06Rock & Rails
2016-12-06SenseShapes
2016-12-06Motion Prediction Approaches to Reducing Latency in Dynamic Projector-Camera Systems
2016-12-06Mutual Dissambiguation of 3D Multimodal Interaction in Augmented and Virtual Reality
2016-12-06MirageTable: Freehand Interaction on a Projected Augmented Reality Tabletop.
2016-12-06Constructionist Design Methodology for Interactive Intelligences
2016-12-06FoveAR
2016-12-06DepthTouch: Using Depth-Sensing Camera to Enable Freehand Interactions On and Above the Surface
2016-12-06Enhancing Input On and Above the Interactive Surface with Muscle Sensing
2016-12-06Pinch-the-Sky Dome: Freehand Multi-Point Interactions with Immersive Omni-Directional Data
2016-12-02Hardness of Approximation Between P and NP
2016-12-01The bullet problem with discrete speeds
2016-12-01Boosting Developer Productivity: How Personal Data Will Revolutionize Software Development
2016-12-01Project Malmo – Enabling AI technology that can collaborate with humans
2016-11-30The Intern Experience at Microsoft Research Cambridge
2016-11-28Ignite Talks-Bill Bliss
2016-11-28Flexible Paxos
2016-11-28Developing PDE-compartment hybrid frameworks for modelling cell migration
2016-11-23Mobile Holoportation
2016-11-18HAMS Visualization Demo
2016-11-18HAMS Vehicle Ranging Demo


Tags:
microsoft research