Study notebook

Press N to jot a timestamped note or B to pin a moment while watching.

A Fine-Grained Analogue of Schaefer's Theorem in P

Marvin KunnemanMax Planck Institute for Informatics

Researcher

20:25·2020·research level·Research Seminar

Explore an advanced analysis of computational complexity, examining a fine-grained analogue of Schaefer's Theorem to delineate the boundaries of polynomial-time solvability.

Theory & Algos Computational Complexity fine-grained complexity Schaefer's Theorem P-completeness

Theory-Fest 2019-2020: Fine-Grained Complexity

Source: Computational Complexity via YouTubeWatch on YouTube

LecturerAll lecturers →

Marvin Kunneman

Researcher

Comments

Add a comment...Sign in

Related lectures

Efficient Fine-Grained Algorithms

Barna Saha · UC Berkeley

Shared subfield · Computational Complexity & fine-grained complexity

From P-Completeness to PSPACE-Completeness

Ryan O'Donnell · Carnegie Mellon University

Shared subfield · Computational Complexity & P-completeness

Conditional Hardness for the Fréchet Distance Under Translation

Andre Nusser · Max Planck Institute for Informatics

Shared subfield · Computational Complexity

Beyond Naïve Approximation for Longest Common Subsequence

Debarati Das · University of Copenhagen

Shared subfield · Computational Complexity

Learning Representations: A Challenge for Learning Theory, COLT 2013

Yann LeCun · New York University

Shared subfield · Computational Complexity

Complexity of Answering Unions of Conjunctive Queries

Nofar Carmeli · Harvard University

Shared subfield · Computational Complexity