32:36A Direct Product Theorem for One-Way Quantum Communication - Srijita Kundu
Advanced
A 33-minute video from Computational Complexity Conference: “A Direct Product Theorem for One-Way Quantum Communication - Srijita Kundu”.
Computational Complexity Conference
256 subscribers on YouTube
Shorts, livestreams, trailers and promos are never listed. Unless a curator approved this channel in full, only individually picked videos appear.
32:36
23:34A Lower Bound for Polynomial Calculus with Extension Rule - Yarolsav Alekseev
Advanced
A 24-minute video from Computational Complexity Conference: “A Lower Bound for Polynomial Calculus with Extension Rule - Yarolsav Alekseev”.
18:02A Lower Bound on Determinantal Complexity - Ben Lee Volk
Advanced
A 18-minute video from Computational Complexity Conference: “A Lower Bound on Determinantal Complexity - Ben Lee Volk”.
25:03A Majority Lemma for Randomised Query Complexity - Gilbert Maystre
Advanced
A 25-minute video from Computational Complexity Conference: “A Majority Lemma for Randomised Query Complexity - Gilbert Maystre”.
28:13A Quadratic Lower Bound for Algebraic Branching Programs and Formulas - Prerona Chatterjee
Advanced
A 28-minute video from Computational Complexity Conference: “A Quadratic Lower Bound for Algebraic Branching Programs and Formulas - Prerona Chatterjee”.
28:25A Simple Proof of a New Set Disjointness with Applications to Data Streams - Akshay Kamath
Advanced
A 28-minute video from Computational Complexity Conference: “A Simple Proof of a New Set Disjointness with Applications to Data Streams - Akshay Kamath”.
27:25A Stress-Free Sum-of-Squares Lower Bound for Coloring - Peter Manohar
Advanced
A 27-minute video from Computational Complexity Conference: “A Stress-Free Sum-of-Squares Lower Bound for Coloring - Peter Manohar”.
29:12A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits - Bhargav Thankey
Advanced
A 29-minute video from Computational Complexity Conference: “A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits - Bhargav Thankey”.
31:09A generalized Sylvester-Gallai type theorem for quadratic polynomials - Shir Peleg
Advanced
A 31-minute video from Computational Complexity Conference: “A generalized Sylvester-Gallai type theorem for quadratic polynomials - Shir Peleg”.
30:10Algebraic Branching Programs, Border Complexity, and Tangent Spaces - Anurag Pandey
Advanced
A 30-minute video from Computational Complexity Conference: “Algebraic Branching Programs, Border Complexity, and Tangent Spaces - Anurag Pandey”.
28:29Algebraic Hardness versus Randomness in Low Characteristic - Robert Andrews
Advanced
A 28-minute video from Computational Complexity Conference: “Algebraic Hardness versus Randomness in Low Characteristic - Robert Andrews”.
26:20Algorithms and lower bounds for de Morgan formulas ... - Dimitrios Myrisiotis
Advanced
A 26-minute video from Computational Complexity Conference: “Algorithms and lower bounds for de Morgan formulas ... - Dimitrios Myrisiotis”.
33:02An Improved Protocol for the Exactly-N Problem - Adi Shraibman
Advanced
A 33-minute video from Computational Complexity Conference: “An Improved Protocol for the Exactly-N Problem - Adi Shraibman”.
22:25Approximability of the eight-vertex model - Tianyu Liu
Advanced
A 22-minute video from Computational Complexity Conference: “Approximability of the eight-vertex model - Tianyu Liu”.
24:55Arithmetic Circuit Complexity of Division and Truncation - Gorav Jindal
Advanced
A 25-minute video from Computational Complexity Conference: “Arithmetic Circuit Complexity of Division and Truncation - Gorav Jindal”.
32:48Barriers for recent methods in geodesic optimization - Philipp Reichenbach
Advanced
A 33-minute video from Computational Complexity Conference: “Barriers for recent methods in geodesic optimization - Philipp Reichenbach”.
25:21Branching Programs with Bounded Repetitions and Flow Formulas - Anastasia Sofronova
Advanced
A 25-minute video from Computational Complexity Conference: “Branching Programs with Bounded Repetitions and Flow Formulas - Anastasia Sofronova”.
28:21Circuit Lower Bounds from NP-Hardness of MCSP under Turing Reductions - Rahul Santhanam
Advanced
A 28-minute video from Computational Complexity Conference: “Circuit Lower Bounds from NP-Hardness of MCSP under Turing Reductions - Rahul Santhanam”.
28:20Communication Complexity with Defective Randomness - Marshall Ball
Advanced
A 28-minute video from Computational Complexity Conference: “Communication Complexity with Defective Randomness - Marshall Ball”.
27:42Deep dive: A generalized Sylvester-Gallai type theorem for quadratic polynomials - Shir Peleg
Advanced
A 28-minute video from Computational Complexity Conference: “Deep dive: A generalized Sylvester-Gallai type theorem for quadratic polynomials - Shir Peleg”.
19:45Deep dive: Multiparty Karchmer-Wigderson Games and Threshold Circuits - Vladimir Podolskii
Advanced
A 20-minute video from Computational Complexity Conference: “Deep dive: Multiparty Karchmer-Wigderson Games and Threshold Circuits - Vladimir Podolskii”.
24:30Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits - Prateek Dwivedi
Advanced
A 24-minute video from Computational Complexity Conference: “Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits - Prateek Dwivedi”.
29:25Error Reduction For Weighted PRGs Against Read Once Branching Programs - Ori Sberlo
Advanced
A 29-minute video from Computational Complexity Conference: “Error Reduction For Weighted PRGs Against Read Once Branching Programs - Ori Sberlo”.
28:53Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and ... - Kilian Risse
Advanced
A 29-minute video from Computational Complexity Conference: “Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and ... - Kilian Risse”.
25:37Factorization of Polynomials Given by Arithmetic Branching Programs - Amit Sinhababu
Advanced
A 26-minute video from Computational Complexity Conference: “Factorization of Polynomials Given by Arithmetic Branching Programs - Amit Sinhababu”.
31:15Finding Small Satisfying Assignments Faster Than Bruteforce - Marvin Künnemann
Advanced
A 31-minute video from Computational Complexity Conference: “Finding Small Satisfying Assignments Faster Than Bruteforce - Marvin Künnemann”.
22:12Fourier Growth of Parity Decision Trees - Kewen Wu
Advanced
A 22-minute video from Computational Complexity Conference: “Fourier Growth of Parity Decision Trees - Kewen Wu”.
27:51Fractional Pseudorandom Generators from Any Fourier Level - Jason Gaitonde
Advanced
A 28-minute video from Computational Complexity Conference: “Fractional Pseudorandom Generators from Any Fourier Level - Jason Gaitonde”.
31:10GSF-locality is not sufficient for proximity-oblivious testing - Noleen Köhler
Advanced
A 31-minute video from Computational Complexity Conference: “GSF-locality is not sufficient for proximity-oblivious testing - Noleen Köhler”.
21:39Geometric Rank of Tensors and Subrank of Matrix Multiplication - Jeroen Zuiddam
Advanced
A 22-minute video from Computational Complexity Conference: “Geometric Rank of Tensors and Subrank of Matrix Multiplication - Jeroen Zuiddam”.
31:22Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems - Markus Lohrey
Advanced
A 31-minute video from Computational Complexity Conference: “Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems - Markus Lohrey”.
33:27Hardness of Bounded Distance Decoding on Lattices in L_p Norms - Huck Bennett
Advanced
A 33-minute video from Computational Complexity Conference: “Hardness of Bounded Distance Decoding on Lattices in L_p Norms - Huck Bennett”.
31:23Hardness of Constant-round Communication Complexity - Rahul Ilango
Advanced
A 31-minute video from Computational Complexity Conference: “Hardness of Constant-round Communication Complexity - Rahul Ilango”.
30:06Hardness of KT Characterizes Parallel Cryptography - Hanlin Ren
Advanced
A 30-minute video from Computational Complexity Conference: “Hardness of KT Characterizes Parallel Cryptography - Hanlin Ren”.
28:10Hitting Sets and Reconstruction for Dense Orbits in VP and ΣΠΣ circuits - Amir Shpilka
Advanced
A 28-minute video from Computational Complexity Conference: “Hitting Sets and Reconstruction for Dense Orbits in VP and ΣΠΣ circuits - Amir Shpilka”.
26:42Hitting sets give two-sided derandomization of small space - William Hoza
Advanced
A 27-minute video from Computational Complexity Conference: “Hitting sets give two-sided derandomization of small space - William Hoza”.