IEEE FOCS: Foundations of Computer Science Talks & Presentations

IEEE

Rigid Matrices from Rectangular PCPs

Explore rigid matrices, low rank matrices, and rectangular PCPs in this technical talk on advanced mathematical concepts and their applications.

• YouTube
• 22 minutes
• On-Demand
• Conference Talk

IEEE

Proximity Gaps for Reed-Solomon Codes

Explore proximity gaps in Reed-Solomon codes, including error terms, generalizations, and applications. Learn about decoders like Berlekamp-Welch and their implementations.

• YouTube
• 21 minutes
• On-Demand
• Conference Talk

IEEE

Scheduling with Communication Delays via LP Hierarchies and Clustering

Explore scheduling with communication delays using LP hierarchies and clustering, covering techniques like simplifying assumptions, LP scheduling, and clustering for efficient problem-solving.

• YouTube
• 21 minutes
• On-Demand
• Conference Talk

IEEE

Subexponential LPs Approximate Max-Cut

Explore subexponential linear programs for approximating Max-Cut, comparing LPs and SDPs, and examining refutation in pseudorandom graphs. Gain insights into combinatorial optimization techniques.

• YouTube
• 26 minutes
• On-Demand
• Conference Talk

IEEE

Symbolic Determinant Identity Testing - SDIT Is Not a Null Cone Problem; and the Symmetries of Algebraic Varieties

Explore symbolic determinant identity testing, noncommutative identities, and algebraic problems in this IEEE talk by Makam and Wigderson, delving into the symmetries of algebraic varieties.

• YouTube
• 25 minutes
• On-Demand
• Conference Talk

IEEE

Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes

Explore optimization techniques for Sherrington-Kirkpatrick problems using sum-of-squares lower bounds and planted affine planes, with insights on certification and hierarchies.

• YouTube
• 22 minutes
• On-Demand
• Conference Talk

IEEE

Revisiting Tardos’s Framework for Linear Programming - Faster Exact Solutions using Approximate Solvers

Explore advanced linear programming techniques, focusing on Tardos's framework and innovative approaches for faster exact solutions using approximate solvers.

• YouTube
• 24 minutes
• On-Demand
• Conference Talk

IEEE

A Parameterized Approximation Scheme for Min k-Cut

Explore a parameterized approximation scheme for the Min k-Cut problem, covering algorithms, research directions, and proof ingredients like tree decomposition and polynomial time analysis.

• YouTube
• 21 minutes
• On-Demand
• Conference Talk

IEEE

Local Proofs Approaching the Witness Length

Explore probabilistically checkable proofs, interactive oracle proofs, and tensor codes in this talk on local proofs and witness length optimization.

• YouTube
• 27 minutes
• On-Demand
• Conference Talk

IEEE

New Techniques for Proving Fine-Grained Average-Case Hardness

Explore cutting-edge methods for demonstrating fine-grained average-case complexity, focusing on K-Click problems and factored approaches in computational theory.

• YouTube
• 24 minutes
• On-Demand
• Conference Talk

IEEE

Isotropy and Log-Concave Polynomials

Explore isotropy and log-concave polynomials in accelerated sampling and high-precision counting of matroid bases, covering techniques like negative dependence and instant mixing.

• YouTube
• 20 minutes
• On-Demand
• Conference Talk

IEEE

High-Precision Estimation of Random Walks in Small Space

Explore advanced techniques for estimating random walks in limited space, covering pseudorandom generators, graph algorithms, and Laplacian systems for efficient problem-solving.

• YouTube
• 25 minutes
• On-Demand
• Conference Talk

IEEE

Is it Easier to Prove Statements that are Guaranteed to be True?

Explore the intricacies of proving statements in computational complexity, focusing on worst-case vs. average-case hardness and the challenges in NP-Search problems.

• YouTube
• 26 minutes
• On-Demand
• Conference Talk

IEEE

Extractors and Secret Sharing Against Bounded Collusion Protocols

Explore complexity theory, multiparty communication, and leakage-resilient extractors in this talk on bounded collusion protocols and secret sharing techniques.

• YouTube
• 35 minutes
• On-Demand
• Conference Talk

IEEE

Testing Positive Semi-Definiteness via Random Submatrices

Explore efficient algorithms for testing positive semi-definiteness of large matrices using random submatrices, with applications in machine learning and optimization.

• YouTube
• 25 minutes
• On-Demand
• Conference Talk