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
Automata TheoryStanford University via edX Intro to Theoretical Computer Science
Udacity Computing: Art, Magic, Science
ETH Zurich via edX 理论计算机科学基础 | Introduction to Theoretical Computer Science
Peking University via edX Quantitative Formal Modeling and Worst-Case Performance Analysis
EIT Digital via Coursera