Results 1 to 3 of 3

Thread: Richard M. Karp

  1. #1

  2. #2


    Richard Karp talks about 30 Years of Berkeley Computer Science (1973-2003)

    Jul 31, 2019

    Lecture at the Faculty Club celebrating the 30th anniversary of the CS Division at the University of California, Berkeley on February 28, 2004. Introduction by Randy Katz.

  3. #3


    Richard Karp: Algorithms and Computational Complexity | AI Podcast #111 with Lex Fridman

    Jul 26, 2020

    Richard Karp is a professor at Berkeley and one of the key figures in the history of theoretical computer science. In 1985, he received the Turing Award for his research in the theory of algorithms, including the development of the Edmonds–Karp algorithm for solving the maximum flow problem on networks, Hopcroft–Karp algorithm for finding maximum cardinality matchings in bipartite graphs, and his landmark paper in complexity theory called "Reducibility Among Combinatorial Problems", in which he proved 21 problems to be NP-complete. This paper was probably the most important catalyst in the explosion of interest in the study of NP-completeness and the P vs NP problem. This conversation is part of the Artificial Intelligence podcast.

    Outline:

    0:00 - Introduction
    3:50 - Geometry
    9:46 - Visualizing an algorithm
    13:00 - A beautiful algorithm
    18:06 - Don Knuth and geeks
    22:06 - Early days of computers
    25:53 - Turing Test
    30:05 - Consciousness
    33:22 - Combinatorial algorithms
    37:42 - Edmonds-Karp algorithm
    40:22 - Algorithmic complexity
    50:25 - P=NP
    54:25 - NP-Complete problems
    1:10:29 - Proving P=NP
    1:12:57 - Stable marriage problem
    1:20:32 - Randomized algorithms
    1:33:23 - Can a hard problem be easy in practice?
    1:43:57 - Open problems in theoretical computer science
    1:46:21 - A strange idea in complexity theory
    1:50:49 - Machine learning
    1:56:26 - Bioinformatics
    2:00:37 - Memory of Richard's father

Социальные закладки

Социальные закладки

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •