When and how can we compute approximate solutions to NP-hard problems?
Event details
| Date | 07.06.2013 |
| Hour | 11:15 › 12:15 |
| Speaker | Prof. Sanjeev Arora, Princeton University |
| Location | |
| Category | Conferences - Seminars |
Can efficient algorithms find approximately optimal solutions (provably) to NP-hard problems? This question has animated a big research effort in theoretical CS in the past few decades. This included the PCP Theorems and many exciting approximation algorithms.
For several problems we even know the precise approximation threshold that can be achieved by efficient algorithms, and also know that improving upon that threshold is no easier than exact optimization. This theory makes connections with a host of other disciplines. Even the PCP Theorem (which says that proofs can be probabilistically checked by examining a constant number of bits in them) seems at first sight to have nothing to do with approximation. This talk, which is geared to a broad scientific audience, will survey this field.
For several problems we even know the precise approximation threshold that can be achieved by efficient algorithms, and also know that improving upon that threshold is no easier than exact optimization. This theory makes connections with a host of other disciplines. Even the PCP Theorem (which says that proofs can be probabilistically checked by examining a constant number of bits in them) seems at first sight to have nothing to do with approximation. This talk, which is geared to a broad scientific audience, will survey this field.
Links
Practical information
- General public
- Free
Organizer
- SuRI 2013
Contact
- Simone Muller