Главная
Study mode:
on
You
History
Saved
In progress 0 courses
compleat 0 courses
#Art & Design #Adobe #ChatGPT #GitHub

#Computational Complexity Theory

#NP-Complete Problems #NP-completeness #Circuit Complexity #Derandomization #Parameterized Complexity
Showing: 147 courses
Harvard University

Advanced Algorithms - COMPSCI 224

3 rewiews
Explore cutting-edge algorithmic techniques through comprehensive lectures, enhancing problem-solving skills and deepening understanding of complex computational challenges.
Add to list
25 Lesons
1 day 11 hours
On-Demand
Free-Video
NPTEL

Theory of Automata, Formal Languages and Computation

1 rewiews
Explore automata theory, formal languages, and computation through grammars, finite state automata, pushdown automata, Turing machines, and advanced topics in theoretical computer science.
Add to list
42 Lesons
1 day 15 hours
On-Demand
Free-Video
NPTEL

Design & Analysis of Algorithms

1 rewiews
Comprehensive exploration of algorithm design techniques, analysis frameworks, and problem-solving strategies, covering divide-and-conquer, greedy algorithms, dynamic programming, and NP-completeness.
Add to list
34 Lesons
1 day 6 hours
On-Demand
Free-Video
Massachusetts Institute of Technology

Theory of Computation, Fall 2020

0 rewiews
Explore computability and complexity theory with MIT's in-depth course. Covers automata, Turing machines, undecidability, NP-completeness, and advanced topics in computational theory.
Add to list
25 Lesons
1 day 8 hours
On-Demand
Free-Video
Santa Fe Institute

Tutorial on Computer Science - Josh Grochow

0 rewiews
Explore key concepts in computer science, from model independence to computational complexity theory, with insights on P vs NP and various computational models.
Add to list
19 Lesons
55 minutes
On-Demand
Free-Video
Simons Institute

The Parallelism Tradeoff: Understanding Transformer Expressivity Through Circuit Complexity

0 rewiews
Explore transformer neural nets' computational power and limitations through circuit complexity analysis, revealing insights into parallelism tradeoffs in large-scale model architectures.
Add to list
1 Lesons
45 minutes
On-Demand
Free-Video
Simons Institute

Limitations of Attention Mechanism in Transformers - Implications for Generalization and Optimization

0 rewiews
Explore Transformer's reasoning capabilities and limitations in sequential tasks, examining optimization challenges and out-of-distribution generalization issues compared to RNNs.
Add to list
1 Lesons
48 minutes
On-Demand
Free-Video
Institute for Advanced Study

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen

0 rewiews
Explore advanced topics in computational complexity, including circuit lower bounds, derandomization, and their connections. Gain insights into cutting-edge research and theoretical developments in computer science.
Add to list
14 Lesons
1 hour 7 minutes
On-Demand
Free-Video
Institute for Advanced Study

Proof and Circuit Complexity - Robert Robere

0 rewiews
Explore proof and circuit complexity with Robert Robere, delving into Boolean circuits, monotone circuits, slice functions, and the Click function to understand computational limitations.
Add to list
8 Lesons
24 minutes
On-Demand
Free-Video
GERAD Research Center

Fixed-Parameter Tractability of Scheduling Dependent Tasks on m Machines Subject to Release Times and Deadlines

0 rewiews
Explore fixed-parameter tractability in scheduling dependent tasks on multiple machines with release times and deadlines. Gain insights into parameterized complexity and dynamic programming approaches.
Add to list
1 Lesons
50 minutes
On-Demand
Free-Video
Centre International de Rencontres Mathématiques

Et si SAT était vraiment difficile? Quelques conséquences des hypothèses ETH - Lecture

0 rewiews
Explorez les implications des hypothèses ETH sur la difficulté du problème SAT et ses conséquences en informatique théorique et complexité algorithmique.
Add to list
1 Lesons
58 minutes
On-Demand
Free-Video
Centre International de Rencontres Mathématiques

A Quick and Partial Survey on the Complexity of Query Answering

0 rewiews
Explore the complexity of query answering in this survey, covering key concepts and recent developments in discrete mathematics and logic.
Add to list
1 Lesons
1 hour 1 minute
On-Demand
Free-Video
Simons Institute

Tales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy

0 rewiews
Explores obfuscation's role in theoretical computer science, covering Circuit Range Avoidance, metacomplexity of Kolmogorov complexity, and computational differential privacy, with focus on recent results and open questions.
Add to list
1 Lesons
48 minutes
On-Demand
Free-Video
Insights into Mathematics

Trying to Sidestep the SAT Problem - N J Wildberger

0 rewiews
Explores the SAT problem in Boolean algebra and logic circuits, introducing the Algebra of Boole approach as an alternative for analyzing smaller circuits and potentially addressing larger-scale issues in integrated circuit design.
Add to list
6 Lesons
28 minutes
On-Demand
Free-Video
Ryan O'Donnell

Expander Graph Application 2: Derandomization - Lecture 16c of CS Theory Toolkit

0 rewiews
Explore derandomization techniques using expander graphs to reduce error in randomized algorithms without significantly increasing random bits used.
Add to list
17 Lesons
23 minutes
On-Demand
Free-Video
Simons Institute

A Tale of Turing Machines, Quantum-Entangled Particles, and Operator Algebras

0 rewiews
Explore the convergence of computational complexity, quantum information, and operator algebras in solving long-standing problems, including Connes' Embedding Problem, in this accessible lecture for a general scientific audience.
Add to list
22 Lesons
55 minutes
On-Demand
Free-Video
Institute for Pure & Applied Mathematics (IPAM)

A Framework for Differentiable Discovery of Graph Algorithms

0 rewiews
Explore graph algorithm discovery using deep learning and tree decomposition. Learn effective techniques for NP-complete problems with interpretable results and expanded search space.
Add to list
19 Lesons
29 minutes
On-Demand
Free-Video
Hausdorff Center for Mathematics

Sparse Integer Programming Is FPT

0 rewiews
Explore sparse integer programming's fixed-parameter tractability, its implications for parameterized complexity, and related concepts in variable dimension optimization.
Add to list
7 Lesons
35 minutes
On-Demand
Free-Video
Applied Algebraic Topology Network

Parameterized Complexity of Quantum Invariants of Knots

0 rewiews
Explore quantum invariants of knots, their parameterized complexity, and efficient algorithms for computation using graphical calculus and tree embeddings.
Add to list
9 Lesons
50 minutes
On-Demand
Free-Video
Hausdorff Center for Mathematics

Introduction to Parameterized Algorithms and Applications

0 rewiews
Explore parameterized complexity and its applications in discrete optimization, focusing on LP-guided techniques, Lenstra's algorithm, and structured ILPs using Graver bases.
Add to list
1 Lesons
1 hour 6 minutes
On-Demand
Free-Video
International Centre for Theoretical Sciences

How Hard is it to Solve This? - Computational Complexity in Problem Solving

0 rewiews
Explore problem-solving techniques in mathematics and statistics through lectures, hands-on sessions, and interactions with distinguished researchers. Gain broader exposure to key topics and enhance analytical skills.
Add to list
1 Lesons
44 minutes
On-Demand
Free-Video
Simons Institute

Introduction to Commuting Local Hamiltonian Problems

0 rewiews
Explore quantum complexity through commuting local Hamiltonian problems, focusing on quantum PCP, area laws, and quantum gravity connections.
Add to list
1 Lesons
48 minutes
On-Demand
Free-Video
Institute for Advanced Study

When and How are Promise Constraint Satisfaction Problems Efficiently Solvable

0 rewiews
Delve into the mathematical foundations of Constraint Satisfaction Problems (CSP), exploring algorithmic efficiency, polymorphisms, and promise CSP applications in graph coloring and discrepancy minimization.
Add to list
1 Lesons
1 hour 5 minutes
On-Demand
Free-Video
Centre for Quantum Technologies

NLTS Hamiltonians from Good Quantum Codes - Understanding Low-Energy States and Circuit Complexity

0 rewiews
Delve into the complexity of NLTS conjecture, quantum LDPC codes, and their connection to local Hamiltonians, exploring circuit lower bounds and many-body entanglement principles.
Add to list
1 Lesons
42 minutes
On-Demand
Free-Video
Squid: Schools for Quantum Information Development

Identity Check Problem for Shallow Quantum Circuits

0 rewiews
Explore an efficient classical algorithm for checking quantum circuit identity, focusing on shallow geometrically local circuits and their distance approximation to identity channels.
Add to list
1 Lesons
25 minutes
On-Demand
Free-Video
Squid: Schools for Quantum Information Development

3D-Local Noisy Shallow Quantum Circuits - A Colossal Advantage Against Classical Computing

0 rewiews
Explore groundbreaking research demonstrating quantum computing superiority using 3D-local noisy circuits, showcasing unprecedented advantages over classical computing in fault-tolerant quantum systems.
Add to list
1 Lesons
24 minutes
On-Demand
Free-Video
Squid: Schools for Quantum Information Development

Parity vs. AC0 with Simple Quantum Preprocessing

0 rewiews
Delve into quantum computation theory exploring the limitations of QNC0 and AC0 circuits in computing parity functions, with insights into decision tree complexity and nonlocal channels.
Add to list
1 Lesons
31 minutes
On-Demand
Free-Video
Squid: Schools for Quantum Information Development

Quantum Advantage from One-Way Functions

0 rewiews
Delve into quantum advantage theory through one-way functions, exploring inefficient-verifier proofs of quantumness and their construction from classical bit commitments in cryptography.
Add to list
1 Lesons
27 minutes
On-Demand
Free-Video
Squid: Schools for Quantum Information Development

Quantum PCPs: On Adaptivity, Multiple Provers and Reductions to Local Hamiltonians

0 rewiews
Delve into advanced quantum PCP theory, exploring adaptivity, multiple unentangled provers, and their connections to local Hamiltonians through rigorous mathematical frameworks and complexity theory analysis.
Add to list
1 Lesons
24 minutes
On-Demand
Free-Video
Squid: Schools for Quantum Information Development

Constant-Depth Circuits for Uniformly Controlled Gates and Boolean Functions

0 rewiews
Explore constant-depth quantum circuits using Fan-Out and Global Tunable gates, focusing on implementations for Uniformly Controlled Gates and quantum memory applications.
Add to list
1 Lesons
25 minutes
On-Demand
Free-Video
Squid: Schools for Quantum Information Development

Computational Quantum Secret Sharing

0 rewiews
Discover groundbreaking advances in quantum secret sharing schemes, exploring computational security approaches that achieve efficient distribution and reconstruction of quantum states with reduced share sizes.
Add to list
1 Lesons
17 minutes
On-Demand
Free-Video
Kolmogorov-Seminar

PAC Learning: From Finite Families to CNF Formulas - Lecture on March 20, 2023

0 rewiews
Dive into PAC learning concepts, exploring finite families, conjunctions, k-CNFs, and NP-completeness in proper learning for 2-term CNF through advanced computational complexity theory.
Add to list
1 Lesons
2 hours 1 minute
On-Demand
Free-Video
Squid: Schools for Quantum Information Development

Quantum State Learning Implies Circuit Lower Bounds

0 rewiews
Delve into groundbreaking research connecting quantum state tomography with circuit complexity, exploring implications for quantum learning algorithms and classical circuit lower bounds.
Add to list
1 Lesons
22 minutes
On-Demand
Free-Video
Paul G. Allen School

Innovations in Theoretical Computer Science 2020 - Session 10

0 rewiews
Explores cutting-edge research in theoretical computer science, covering topics like computational hardness, random strings, decision trees, and pseudorandomness. Features presentations from leading experts in the field.
Add to list
1 Lesons
1 hour 29 minutes
On-Demand
Free-Video
Simons Institute

A Brief Introduction to Algorithms, Game Theory and Risk-Averse Decision Making

0 rewiews
Explore algorithms, game theory, and risk-averse decision making, covering shortest paths, NP-Complete problems, equilibria, and various risk frameworks for real-world applications.
Add to list
27 Lesons
1 hour 12 minutes
On-Demand
Free-Video
Simons Institute

Oral History - Russell Impagliazzo in Conversation with Dick Karp

0 rewiews
Explore key developments in theoretical computer science through an engaging conversation between Russell Impagliazzo and Dick Karp, covering topics from NP-completeness to computational biology.
Add to list
16 Lesons
1 hour 24 minutes
On-Demand
Free-Video
Simons Institute

Beyond Worst-Case Analysis - Panel Discussion

0 rewiews
Experts discuss advanced algorithmic analysis, exploring beyond worst-case scenarios to improve efficiency and understanding in computer science and machine learning applications.
Add to list
14 Lesons
1 hour 10 minutes
On-Demand
Free-Video
Association for Computing Machinery (ACM)

Leslie G. Valiant - Turing Award Lecture 2010

0 rewiews
Explore computational learning theory, machine learning, and brain modeling with Leslie G. Valiant, 2010 ACM Turing Award winner, as he discusses his groundbreaking research and insights.
Add to list
14 Lesons
1 hour 4 minutes
On-Demand
Free-Video
Simons Institute

PCPs and Global Hyper-contractivity - Lecture 1

0 rewiews
Explore advanced concepts in theoretical computer science, focusing on Probabilistically Checkable Proofs and global hyper-contractivity with expert Dor Minzer.
Add to list
1 Lesons
59 minutes
On-Demand
Free-Video
Simons Institute

PCPs and Global Hyper-contractivity - Lecture 3

0 rewiews
Explore advanced concepts in PCPs and global hyper-contractivity with Dor Minzer, delving into complex mathematical theories and their applications in analysis and theoretical computer science.
Add to list
1 Lesons
1 hour
On-Demand
Free-Video
Simons Institute

Linearity Testing Over the Biased Cube

0 rewiews
Explores linearity testing in p-biased settings, presenting a 4-query test with optimal soundness. Discusses structural results and direct product tests for functions correlated to linear functions under random restrictions.
Add to list
1 Lesons
1 hour
On-Demand
Free-Video
Simons Institute

PCPs and Global Hyper-contractivity - Lecture 2

0 rewiews
Explore advanced concepts in PCPs and global hyper-contractivity with Dor Minzer, delving into complex mathematical theories and their applications in analysis and theoretical computer science.
Add to list
1 Lesons
1 hour 4 minutes
On-Demand
Free-Video
Simons Institute

PCPs and Global Hyper-contractivity - Lecture 1

0 rewiews
Explore advanced concepts in theoretical computer science, focusing on Probabilistically Checkable Proofs and global hyper-contractivity with expert Dor Minzer.
Add to list
1 Lesons
50 minutes
On-Demand
Free-Video
Simons Institute

Fine-Grained Complexity 2 - Advanced Concepts and Applications

0 rewiews
Explore advanced concepts in fine-grained complexity theory, focusing on algorithmic challenges and computational limits in database theory and AI applications.
Add to list
1 Lesons
1 hour 3 minutes
On-Demand
Free-Video
Simons Institute

Fine-Grained Complexity - Lecture 1

0 rewiews
Explore cutting-edge research in fine-grained complexity theory with MIT expert Virginia Vassilevska Williams, delving into advanced algorithmic concepts and their applications.
Add to list
1 Lesons
1 hour
On-Demand
Free-Video
Simons Institute

Logic and Probabilistic Circuits - Lecture 4

0 rewiews
Explore advanced concepts in logic and probabilistic circuits, focusing on their applications in database theory and artificial intelligence.
Add to list
1 Lesons
1 hour 1 minute
On-Demand
Free-Video
Simons Institute

Logic and Probabilistic Circuits - Part 3

0 rewiews
Explore advanced concepts in logic and probabilistic circuits, focusing on their applications in database theory and AI algorithms.
Add to list
1 Lesons
1 hour
On-Demand
Free-Video
Simons Institute

Fine-Grained Complexity - Lecture 4

0 rewiews
Explore advanced concepts in fine-grained complexity theory, focusing on algorithmic challenges and their implications for database theory and AI applications.
Add to list
1 Lesons
58 minutes
On-Demand
Free-Video
Simons Institute

Fine-Grained Complexity 3 - Logic and Algorithms in Database Theory and AI

0 rewiews
Explore advanced concepts in fine-grained complexity theory, focusing on algorithmic challenges and their implications for database theory and AI.
Add to list
1 Lesons
1 hour 7 minutes
On-Demand
Free-Video
Simons Institute

Top-Down Lower Bounds for Depth-Four Circuits

0 rewiews
Explores new proof techniques for depth-4 boolean circuit complexity, applying robust sunflowers and block unpredictability to demonstrate exponential lower bounds for the parity function.
Add to list
1 Lesons
1 hour 1 minute
On-Demand
Free-Video
Simons Institute

Fully Linear PCPs and Their Cryptographic Applications

0 rewiews
Explore probabilistically checkable proofs, distributed verifiers, and cryptographic applications with a focus on fully linear PCPs and their impact on secure protocols and communication complexity.
Add to list
18 Lesons
1 hour 8 minutes
On-Demand
Free-Video
Simons Institute

How to Do Fiat-Shamir in the Standard Model

0 rewiews
Explore interactive protocols, Fiat-Shamir transformation, and delegation in cryptography. Learn about security assumptions, hash functions, and correlation intractability in probabilistic proof systems.
Add to list
15 Lesons
1 hour 10 minutes
On-Demand
Free-Video
Simons Institute

How to Delegate Computations Publicly

0 rewiews
Explore probabilistically checkable and interactive proof systems, focusing on publicly verifiable arguments and non-interactive protocols for delegating computations.
Add to list
11 Lesons
28 minutes
On-Demand
Free-Video
Simons Institute

Transparent SNARKs from DARK Compilers

0 rewiews
Explore transparent SNARKs and DARK compilers in cryptography. Learn about polynomial commitments, interactive proof systems, and recent advancements in zero-knowledge proofs for blockchain applications.
Add to list
28 Lesons
48 minutes
On-Demand
Free-Video
Simons Institute

Efficient Zero Knowledge Proof from Interactive Proofs

0 rewiews
Explore efficient zero-knowledge proofs derived from interactive proofs, focusing on new algorithms, performance improvements, and comparisons to existing systems.
Add to list
19 Lesons
48 minutes
On-Demand
Free-Video
Simons Institute

Probabilistically Checkable Proofs - Part I

0 rewiews
Explore probabilistically checkable proofs, focusing on proof verification, randomized verifiers, and proof rewriting techniques in this advanced theoretical computer science lecture.
Add to list
9 Lesons
59 minutes
On-Demand
Free-Video
Association for Computing Machinery (ACM)

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

0 rewiews
Explore circuit lower bounds and derandomization, focusing on AC circuits, algorithmic methods, and pseudorandom generators. Learn about recent developments in average-case circuit analysis.
Add to list
16 Lesons
21 minutes
On-Demand
Free-Video
Simons Institute

Crash Course on Probabilistically Checkable Proofs - Introduction

0 rewiews
Explore probabilistically checkable proofs, including recoloring, constraint satisfaction, and the PCP theorem. Learn about verifier parameters and hardness of approximation in this comprehensive introduction.
Add to list
12 Lesons
1 hour 1 minute
On-Demand
Free-Video
Simons Institute

Crash Course on Probabilistically Checkable Proofs - PCP

0 rewiews
Explore probabilistically checkable proofs, their formulation, global vs local tests, and computational implications in this comprehensive lecture on advanced theoretical computer science concepts.
Add to list
13 Lesons
1 hour 18 minutes
On-Demand
Free-Video
Simons Institute

Derandomization: A Quick Tutorial

0 rewiews
Explore efficient methods for transforming interactive protocols into NP-type verifiers, using targeted pseudorandom generators and complexity-theoretic assumptions.
Add to list
1 Lesons
1 hour 1 minute
On-Demand
Free-Video
Simons Institute

Efficient Zero-Knowledge Proofs: A Modular Approach

0 rewiews
Explore modular techniques for creating efficient zero-knowledge proofs, focusing on probabilistically checkable and interactive proof systems in cryptography.
Add to list
1 Lesons
1 hour 12 minutes
On-Demand
Free-Video
Simons Institute

Recent Structure Lemmas for Depth-Two Threshold Circuits

0 rewiews
Explore recent advancements in structure lemmas for depth-two threshold circuits, focusing on Boolean devices and their implications in computational complexity theory.
Add to list
1 Lesons
28 minutes
On-Demand
Free-Video
Simons Institute

Berkeley in the 80s - Richard Karp and the Theory of Computing

0 rewiews
In-depth interview with Turing Laureate Richard Karp, exploring his groundbreaking research on computational theory at Berkeley in the 1980s and its lasting impact on computer science.
Add to list
1 Lesons
1 hour 24 minutes
On-Demand
Free-Video
Hausdorff Center for Mathematics

Introduction to Parameterized Algorithms, Lecture I

0 rewiews
Gentle introduction to parameterized complexity, focusing on basic techniques like branching, color coding, and kernelization. Explores connections to linear programming and discrete optimization.
Add to list
1 Lesons
1 hour 8 minutes
On-Demand
Free-Video
Hausdorff Center for Mathematics

Recent Hardness of Approximation Results in Parameterized Complexity

0 rewiews
Survey of recent hardness of approximation results in parameterized complexity, focusing on k-clique problem inapproximability, with technical insights and open problems discussion.
Add to list
1 Lesons
57 minutes
On-Demand
Free-Video
Hausdorff Center for Mathematics

Parametrized Algorithms and Possible Future Directions

0 rewiews
Explore current research and future directions in Parameterized Complexity, focusing on algorithmic approaches and potential areas for further investigation.
Add to list
1 Lesons
1 hour
On-Demand
Free-Video
Hausdorff Center for Mathematics

Michal Pilipczuk: Introduction to Parameterized Algorithms, Lecture II

0 rewiews
Explore parameterized complexity, focusing on LP-related methods. Learn branching, color coding, kernelization, and dynamic programming techniques for algorithm design and optimization.
Add to list
1 Lesons
1 hour 9 minutes
On-Demand
Free-Video
International Centre for Theoretical Sciences

Computational Complexity in Theory and in Practice by Richard M. Karp

0 rewiews
Explore the contrast between theoretical and practical approaches to algorithm efficiency, covering complexity classes, NP-completeness, approximation algorithms, and real-world applications.
Add to list
1 Lesons
1 hour 17 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - Oracle Turing Machines and P^NP

0 rewiews
Explore oracle Turing machines and P^NP in computational complexity theory, focusing on solving algorithms, consequences, and the Minimum Circuit Problem.
Add to list
15 Lesons
1 hour 22 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - BPP

0 rewiews
Explore probabilistic algorithms and complexity class BPP in this advanced lecture on computational theory, featuring axis property amplification and upper bounds.
Add to list
8 Lesons
1 hour 20 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - Randomized Complexity- RP, coRP, and ZPP

0 rewiews
Explore randomized complexity classes RP, coRP, and ZPP, covering probabilistic Turing machines, error amplification, and nondeterminism in computational complexity theory.
Add to list
10 Lesons
1 hour 22 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - The Immerman-Szelepcsényi Theorem

0 rewiews
Explore the Immerman--Szelepcsényi Theorem in computational complexity theory, covering key concepts, proofs, and implications for nondeterministic space complexity classes.
Add to list
9 Lesons
1 hour 21 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - From P-Completeness to PSPACE-Completeness

0 rewiews
Explore P-completeness, reductions, and PSPACE-completeness in computational complexity theory, covering key concepts like the Cook-Levin Theorem and TQBF.
Add to list
7 Lesons
1 hour 20 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - Savitch's Theorem and NL

0 rewiews
Explore Savitch's Theorem and NL in computational complexity theory, focusing on space complexity, recursion, and pseudocode implementation for advanced undergraduate-level understanding.
Add to list
8 Lesons
1 hour 21 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - NP

0 rewiews
Explore NP complexity, verification, and key features in computational theory. Delve into stronger conjectures, brute force algorithms, and proofs for squares and colors.
Add to list
12 Lesons
1 hour 21 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - SAT

0 rewiews
Explore the intricacies of SAT in computational complexity theory, covering Boolean circuits, algorithms, and CNF formulas in this comprehensive undergraduate lecture.
Add to list
8 Lesons
1 hour 20 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - Problems in P

0 rewiews
Explore computational complexity theory, focusing on problems in P, simulations, and Turing machine variants. Learn about time hierarchy, natural problems, and efficient algorithms.
Add to list
16 Lesons
1 hour 22 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - Turing Machines

0 rewiews
Explore Turing Machines in computational complexity theory, covering formalization, the Turing Thesis, examples, and mathematical definitions for a comprehensive understanding.
Add to list
8 Lesons
1 hour 20 minutes
On-Demand
Free-Video
Ryan O'Donnell

Quantum Complexity - Quantum Computation at CMU

0 rewiews
Explore quantum complexity, error probabilities, and complexity classes in this advanced lecture on quantum computation and information theory.
Add to list
9 Lesons
1 hour 23 minutes
On-Demand
Free-Video
Ryan O'Donnell

Razborov-Smolensky Lower Bounds for AC0[p] - Graduate Complexity Lecture at CMU

0 rewiews
Explore Razborov-Smolensky lower bounds for AC0[p] circuits, covering key theorems, gate replacements, and error bounds in computational complexity theory.
Add to list
13 Lesons
1 hour 13 minutes
On-Demand
Free-Video
Ryan O'Donnell

Permanent is #P-Complete: Graduate Complexity Lecture at CMU

0 rewiews
Explore the #P-completeness of the Permanent problem in this advanced computational complexity theory lecture, covering key concepts and reduction techniques.
Add to list
16 Lesons
1 hour 14 minutes
On-Demand
Free-Video
Ryan O'Donnell

The Switching Lemma - PRST Version - Graduate Complexity Lecture at CMU

0 rewiews
Explore the Switching Lemma in computational complexity theory, focusing on the PRST version and its proof, with insights on decision trees and probability bounds.
Add to list
12 Lesons
55 minutes
On-Demand
Free-Video
Ryan O'Donnell

IP = PSPACE - Graduate Complexity Lecture at CMU

0 rewiews
Explore interactive proof systems and their relationship to complexity classes, focusing on the IP = PSPACE theorem and its implications for computational theory.
Add to list
15 Lesons
1 hour 19 minutes
On-Demand
Free-Video
Ryan O'Donnell

Approximate Counting - Graduate Complexity Lecture at CMU

0 rewiews
Explore advanced computational complexity theory, focusing on approximate counting techniques, Chebyshev's Inequality, and interactive proofs in this graduate-level lecture.
Add to list
7 Lesons
1 hour 20 minutes
On-Demand
Free-Video
Ryan O'Donnell

More on Constant-Round Interactive Proof Systems - Graduate Complexity Lecture at CMU

0 rewiews
Explore constant-round interactive proof systems in computational complexity theory, covering MA, AM, BPP, and efficient error reduction techniques.
Add to list
27 Lesons
1 hour 21 minutes
On-Demand
Free-Video
Ryan O'Donnell

Time-Space Tradeoffs for SAT - Graduate Complexity Lecture at CMU

0 rewiews
Explore time/space tradeoffs for SAT in this graduate-level complexity theory lecture, covering key results, proofs, and techniques like padding and alternation elimination.
Add to list
12 Lesons
1 hour 32 minutes
On-Demand
Free-Video
Ryan O'Donnell

The Polynomial Time Hierarchy: Graduate Complexity Lecture at CMU

0 rewiews
Explore the Polynomial Time Hierarchy in computational complexity theory, covering definitions, examples, and key concepts like quantifying over circuits and alternation.
Add to list
11 Lesons
1 hour 19 minutes
On-Demand
Free-Video
Ryan O'Donnell

Hierarchy Theorems - Time, Space, and Nondeterministic: Graduate Complexity Lecture at CMU

0 rewiews
Explore hierarchy theorems in computational complexity, covering time, space, and nondeterministic aspects. Gain insights into encoding schemes, Turing machines, and nondeterministic certificates.
Add to list
13 Lesons
1 hour 21 minutes
On-Demand
Free-Video
Ryan O'Donnell

Hopcroft-Paul-Valiant Theorem - Graduate Complexity Lecture at CMU

0 rewiews
Explore the Hopcroft-Paul-Valiant theorem in computational complexity, covering simulation, graph analysis, and pebble games. Gain insights into low space simulation and depth reduction techniques.
Add to list
18 Lesons
1 hour 20 minutes
On-Demand
Free-Video
Ryan O'Donnell

Circuits - Graduate Complexity Lecture 4 at CMU

0 rewiews
Explore graduate-level computational complexity theory, focusing on circuits, complexity measures, and lower bounds in this advanced lecture from Carnegie Mellon University.
Add to list
15 Lesons
1 hour 20 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - Why is P vs. NP Difficult?

0 rewiews
Explore the challenges of the P vs. NP problem in computational complexity theory, including negative results, Ladner's theorem, and simulations.
Add to list
10 Lesons
1 hour 20 minutes
On-Demand
Free-Video
Ryan O'Donnell

Undergrad Complexity at CMU - Hardness within P

0 rewiews
Explore computational complexity theory, focusing on hardness within P, time hierarchy theorem, and fine-grained complexity. Delve into reductions, algorithms, and open questions in this advanced undergraduate lecture.
Add to list
12 Lesons
1 hour 22 minutes
On-Demand
Free-Video
Alan Turing Institute

Alan Turing and the Other Theory of Computing and Can a Machine Be Conscious?

0 rewiews
Explore neuroscience advances in understanding consciousness, including the Global Workspace Model and its computational implications, with insights on free will and determinism.
Add to list
1 Lesons
1 hour 20 minutes
On-Demand
Free-Video
IEEE

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions

0 rewiews
Explore the randomized query complexity of partial functions and its tight composition theorem, advancing understanding in computational complexity theory.
Add to list
1 Lesons
23 minutes
On-Demand
Free-Video
IEEE

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

0 rewiews
Explore groundbreaking research on circuit complexity theory, focusing on the connection between derandomization techniques and establishing lower bounds for circuit sizes across various computational models.
Add to list
1 Lesons
24 minutes
On-Demand
Free-Video
IEEE

On One-way Functions and Kolmogorov Complexity

0 rewiews
Explore the relationship between one-way functions and Kolmogorov complexity in this insightful IEEE talk by Cornell researchers Liu and Pass.
Add to list
1 Lesons
23 minutes
On-Demand
Free-Video
IEEE

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds

0 rewiews
Explore connections between computational complexity theories, focusing on exponential-time hypotheses, derandomization techniques, and circuit lower bounds in theoretical computer science.
Add to list
1 Lesons
21 minutes
On-Demand
Free-Video
IEEE

Stoquastic PCP vs. Randomness

0 rewiews
Explore the intriguing relationship between stoquastic PCP and randomness in quantum computing, delving into cutting-edge research and its implications for complexity theory.
Add to list
1 Lesons
22 minutes
On-Demand
Free-Video
IEEE

NEXP is Contained in MIP* - Complexity Theory Breakthrough

0 rewiews
Explore groundbreaking results in computational complexity theory, examining the relationship between NEXP and MIP* with insights from experts Anand Natarajan and John Wright.
Add to list
1 Lesons
22 minutes
On-Demand
Free-Video
IEEE

Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits

0 rewiews
Explore the complexity theory concept of non-deterministic quasi-polynomial time and its average-case hardness for ACC circuits in this advanced computer science presentation.
Add to list
1 Lesons
20 minutes
On-Demand
Free-Video