KARPfest80
| title | author | length |
|---|---|---|
| Practical, Efficient ZKPs, Economic and Social Processes | Michael Rabin | 26m |
Describes an efficient zero-knowledge toolkit that represents each secret x as a split-value representation u,v with x = u+v mod p (p ≤ 2^128) and posts… | ||
| Karp Plays a Game | Richard Lipton | 33m |
Claim: given two engines with one blunder each and the blunders never coincide, a simple randomized procedure lets a nonexpert win a winning chess position… | ||
| Five Things I Learned from Dick Karp | Prabhakar Raghavan | 25m |
Shows five concrete lessons: a one-line indicator proof that the expected number of quicksort comparisons equals the sum of 2/(j-i+1) giving ~2n ln n; a… | ||
| Back to the Future: Going Beyond Worst Case Analysis | Sanjeev Arora | 28m |
Argues that worst-case NP-hardness misses real instances and shows concrete alternatives: assumes separable (anchor) words in topic models, uses convex… | ||
| Some Current Computational Challenges in Bioinformatics | Ron Shamir | 28m |
Overview of concrete problems and a working solution: sequencing volume grows exponentially (about 600 billion bases per day on new machines) and the $1,000… | ||
| Some New Results on Random Points in the Unit Square | Alan Frieze | 23m |
Random points in the unit square get Euclidean weights but edges are kept independently with probability p, and the analysis shows that for constant p there is… | ||
| Perfect Matchings | Avi Wigderson | 32m |
Avi Widgerson, Institute for Advanced Study, Princeton
KARPfest80
https://simons.berkeley.edu/karpfest/avi-wigderson-2015-10-17 | ||
| Quantum NP and Beyond | Sandy Irani | 25m |
Defines QMA as NP with a quantum witness and highlights the 5-local Hamiltonian result showing local Hamiltonian is QMA-complete, an eigenvalue decision… | ||
| Human Computation | Manuel Blum | 35m |
A live demo builds and tests human‑computable password schemas that transform site names into passwords by combining a memorized telephone number with a… | ||
| The Computational Benefit of Correlated Instances | Shafi Goldwasser | 32m |
Defines a model where hard CSP instances come with extra correlated instances produced by small perturbations of the hidden solution, and studies two… | ||
| A Personal History (With Karp Reductions!) | Jeremy Karp | 19m |
Chronological takeaways: the Held-Karp subtour LP remains the fundamental relaxation for TSP and modern solvers like Concord now solve instances up to ~25,000… | ||
| Orthogonal Remarks | Donald Knuth | 31m |
A 1959 thesis converts flowcharts to directed graphs and uses matrix and topological arguments to reason about program paths, then includes a full UNIVAC I… | ||
| nothing matches | ||