Catalytic Approaches to the Tree Evaluation Problem
Offered By: Association for Computing Machinery (ACM) via YouTube
Course Description
Overview
Explore the Tree Evaluation Problem (TEP) and its catalytic approaches in this 26-minute ACM conference talk. Delve into the pebbling game introduced by Paterson and Hewitt in 1970, and understand the concept of catalytic space. Learn about a key lemma involving multiplication and discover a formula for TEP. Examine the first attempt at solving this problem and gain insights into computational complexity theory.
Syllabus
Intro
Outline
The Tree Evaluation Problem (TEP)
Pebbling game Paterson Hewitt 1970
Catalytic space
Lemma: Multiplication
A formula for TEP
First attempt
Taught by
Association for Computing Machinery (ACM)
Related Courses
Intro to Theoretical Computer ScienceUdacity Power and elegance of computational thinking
The University of Oklahoma via Janux Comparing Genes, Proteins, and Genomes (Bioinformatics III)
University of California, San Diego via Coursera Algoritmi quotidiani
University of Urbino via EMMA Competitive Programmer's Core Skills
Saint Petersburg State University via Coursera