25:00STOC 2022 - Linear Space Streaming Lower Bounds for Approximating CSPs
Advanced
A 25-minute video from SIGACT EC: “STOC 2022 - Linear Space Streaming Lower Bounds for Approximating CSPs”.
SIGACT EC
1.03K subscribers on YouTube
Shorts, livestreams, trailers and promos are never listed. Unless a curator approved this channel in full, only individually picked videos appear.
25:00
25:10STOC 2022 - Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
Advanced
A 25-minute video from SIGACT EC: “STOC 2022 - Learning General Halfspaces with General Massart Noise under the Gaussian Distribution”.
24:17STOC 2022 - Locality-Sensitive Orderings and Applications to Reliable Spanners
Advanced
A 24-minute video from SIGACT EC: “STOC 2022 - Locality-Sensitive Orderings and Applications to Reliable Spanners”.
33:02STOC 2022 - No self-concordant barrier interior point method is strongly polynomial
Advanced
A 33-minute video from SIGACT EC: “STOC 2022 - No self-concordant barrier interior point method is strongly polynomial”.
24:09STOC 2022 - Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
Advanced
A 24-minute video from SIGACT EC: “STOC 2022 - Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy”.
22:38STOC 2023 - 4A - Noise stability on the Boolean hypercube via a renormalized Brownian motion.
Advanced
A 23-minute video from SIGACT EC: “STOC 2023 - 4A - Noise stability on the Boolean hypercube via a renormalized Brownian motion.”.
24:06STOC 2023 - Session 7A - NP-Hardness of Approximating Meta- Complexity: A Cryptographic Approach
Advanced
A 24-minute video from SIGACT EC: “STOC 2023 - Session 7A - NP-Hardness of Approximating Meta- Complexity: A Cryptographic Approach”.
28:44STOC 2023 - 4A - Approximate Graph Colouring and the Hollow Shadow.
Advanced
A 29-minute video from SIGACT EC: “STOC 2023 - 4A - Approximate Graph Colouring and the Hollow Shadow.”.
26:06STOC 2023 - 4A - On Approximability of Satisfiable k-CSPs: II.
Advanced
A 26-minute video from SIGACT EC: “STOC 2023 - 4A - On Approximability of Satisfiable k-CSPs: II.”.
24:59STOC 2023 - 4A - On Approximability of Satisfiable k-CSPs: III
Advanced
A 25-minute video from SIGACT EC: “STOC 2023 - 4A - On Approximability of Satisfiable k-CSPs: III”.
24:59STOC 2023 - 4A - SDPs and Robust Satisfiability of Promise CSP.
Advanced
A 25-minute video from SIGACT EC: “STOC 2023 - 4A - SDPs and Robust Satisfiability of Promise CSP.”.
25:11STOC 2023 - 4B - A Constant Factor Prophet Inequality for Online Combinatorial Auctions.
Advanced
A 25-minute video from SIGACT EC: “STOC 2023 - 4B - A Constant Factor Prophet Inequality for Online Combinatorial Auctions.”.
26:15STOC 2023 - 4B - A proof of the Nisan-Ronen conjecture.
Advanced
A 26-minute video from SIGACT EC: “STOC 2023 - 4B - A proof of the Nisan-Ronen conjecture.”.
21:59STOC 2023 - 4B - Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules.
Advanced
A 22-minute video from SIGACT EC: “STOC 2023 - 4B - Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules.”.
25:27STOC 2023 - 4B - Computing better approximate pure Nash equilibria in cut games via SDPs.
Advanced
A 25-minute video from SIGACT EC: “STOC 2023 - 4B - Computing better approximate pure Nash equilibria in cut games via SDPs.”.
25:08STOC 2023 - 4B - Credible Decentralized Exchange Design via Verifiable Sequencing Rules
Advanced
A 25-minute video from SIGACT EC: “STOC 2023 - 4B - Credible Decentralized Exchange Design via Verifiable Sequencing Rules”.
25:50STOC 2023 - 4B - On the Optimal Fixed-Price Mechanism in Bilateral Trade.
Advanced
A 26-minute video from SIGACT EC: “STOC 2023 - 4B - On the Optimal Fixed-Price Mechanism in Bilateral Trade.”.
22:42STOC 2023 - 4C - Improved and Deterministic Online Service with Deadlines or Delay.
Advanced
A 23-minute video from SIGACT EC: “STOC 2023 - 4C - Improved and Deterministic Online Service with Deadlines or Delay.”.
25:04STOC 2023 - 4C - Local and global expansion in random geometric graphs.
Advanced
A 25-minute video from SIGACT EC: “STOC 2023 - 4C - Local and global expansion in random geometric graphs.”.
19:30STOC 2023 - 4C - New High Dimensional Expanders from Covers.
Advanced
A 20-minute video from SIGACT EC: “STOC 2023 - 4C - New High Dimensional Expanders from Covers.”.
25:21STOC 2023 - 4C - Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse.
Advanced
A 25-minute video from SIGACT EC: “STOC 2023 - 4C - Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse.”.
25:50STOC 2023 - 4C - Pandora Box Problem with Nonobligatory Inspection: Hardness & Approximation Scheme.
Advanced
A 26-minute video from SIGACT EC: “STOC 2023 - 4C - Pandora Box Problem with Nonobligatory Inspection: Hardness & Approximation Scheme.”.
26:38STOC 2023 - 4C - Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS.
Advanced
A 27-minute video from SIGACT EC: “STOC 2023 - 4C - Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS.”.
25:00STOC 2023 - 4C - Towards the Erdős-Gallai Cycle Decomposition Conjecture.
Advanced
A 25-minute video from SIGACT EC: “STOC 2023 - 4C - Towards the Erdős-Gallai Cycle Decomposition Conjecture.”.
25:23STOC 2023 - 5A - An Optimal "It Ain't Over Till It's Over" Theorem.
Advanced
A 25-minute video from SIGACT EC: “STOC 2023 - 5A - An Optimal "It Ain't Over Till It's Over" Theorem.”.
29:18STOC 2023 - 5A - Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees.
Advanced
A 29-minute video from SIGACT EC: “STOC 2023 - 5A - Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees.”.
27:45STOC 2023 - 5A - Optimal Explicit Small-Depth Formulas for the Coin Problem.
Advanced
A 28-minute video from SIGACT EC: “STOC 2023 - 5A - Optimal Explicit Small-Depth Formulas for the Coin Problem.”.
24:49STOC 2023 - 5A - Randomized versus Deterministic Decision Tree Size.
Advanced
A 25-minute video from SIGACT EC: “STOC 2023 - 5A - Randomized versus Deterministic Decision Tree Size.”.
23:24STOC 2023 - 5B - A polynomial-time classical algorithm for noisy random circuit sampling.
Advanced
A 23-minute video from SIGACT EC: “STOC 2023 - 5B - A polynomial-time classical algorithm for noisy random circuit sampling.”.
18:04STOC 2023 - 5B - An efficient decoder for a linear distance quantum LDPC code.
Advanced
A 18-minute video from SIGACT EC: “STOC 2023 - 5B - An efficient decoder for a linear distance quantum LDPC code.”.
30:41STOC 2023 - 5B - Certified Randomness from Quantum Supremacy.
Advanced
A 31-minute video from SIGACT EC: “STOC 2023 - 5B - Certified Randomness from Quantum Supremacy.”.
22:32STOC 2023 - 5B - Good Quantum LDPC Codes with Linear Time Decoders.
Advanced
A 23-minute video from SIGACT EC: “STOC 2023 - 5B - Good Quantum LDPC Codes with Linear Time Decoders.”.
21:57STOC 2023 - 5C - Kneser graphs are Hamiltonian.
Advanced
A 22-minute video from SIGACT EC: “STOC 2023 - 5C - Kneser graphs are Hamiltonian.”.
24:15STOC 2023 - 5C - Nearly all k-SAT functions are unate.
Advanced
A 24-minute video from SIGACT EC: “STOC 2023 - 5C - Nearly all k-SAT functions are unate.”.
23:24STOC 2023 - 5C - Random Walks on Rotating Expanders.
Advanced
A 23-minute video from SIGACT EC: “STOC 2023 - 5C - Random Walks on Rotating Expanders.”.
25:52STOC 2023 - Session 10A - Faster Deterministic Distributed MIS and Approximate Matching
Advanced
A 26-minute video from SIGACT EC: “STOC 2023 - Session 10A - Faster Deterministic Distributed MIS and Approximate Matching”.