PPP-Completeness and Extremal Combinatorics

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=xPZ6v0kCJ-8


Duration: 27:52
136 views
3

Authors: Romain Bourneuf (ENS de Lyon); Lukáš Folwarczný, Pavel Hubáček (Charles University); Alon Rosen (Bocconi University and Reichman University); Nikolaj Ignatieff Schwartzbach (Aarhus University)
ITCS - Innovations in Theoretical Computer Science



Other Videos By Simons Institute for the Theory of Computing


2023-01-04Rounding via Low Dimensional Embeddings
2023-01-04Efficient algorithms for certifying lower bounds on the discrepancy of random matrices
2023-01-04Unsplittable Euclidean Capacitated Vehicle Routing: A 2+\epsilon)(2+ϵ)-Approximation Algorithm
2023-01-04Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
2023-01-04On the computational hardness needed for quantum cryptography
2023-01-04Kolmogorov Complexity Characterizes Statistical Zero Knowledge
2023-01-04Vertex Sparsification for Edge Connectivity in Polynomial Time
2023-01-04Extremal Combinatorics, iterated pigeonhole arguments, and generalizations of PPP
2023-01-04Fractional certificates for bounded functions
2023-01-04Expander Decomposition in Dynamic Streams
2023-01-04PPP-Completeness and Extremal Combinatorics
2023-01-04Incompressiblity and Next-Block Pseudoentropy
2023-01-04Beeping Shortest Paths via Hypergraph Bipartite Decomposition
2023-01-04Unitary property testing lower bounds by polynomials
2023-01-04Quantum space, ground space traversal, and how to embed multi-prover...
2023-01-04Necessary Conditions in Multi-Server Differential Privacy
2023-01-04Making Decisions under Outcome Performativity
2023-01-04A New Conjecture on Hardness of Low-Degree 2-CSP’s with...
2023-01-04On Interactive Proofs of Proximity with Proof-Oblivious Queries
2023-01-04Quantum algorithms and the power of forgetting
2023-01-04Exact Completeness of LP Hierarchies for Linear Codes


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
ITCS - Innovations in Theoretical Computer Science