IEEE FOCS: Foundations of Computer Science Talks & Presentations

IEEE

The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs

Explore average-case complexity of counting cliques in Erdos-Renyi hypergraphs, covering proof techniques, random KQ accounting, and binary expansions.

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

IEEE

Spectral Analysis of Matrix Scaling and Operator Scaling

Explore spectral analysis techniques for matrix and operator scaling, covering algorithms, applications, and key theorems in this advanced mathematical topic.

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

IEEE

Faster Polytope Rounding, Sampling, and Volume Computation via a Sublinear Ball Walk

Explore advanced algorithms for efficient polytope analysis, including rounding, sampling, and volume computation using innovative Markov chain techniques.

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

IEEE

More Barriers for Rank Methods, via a "Numeric to Symbolic" Transfer

Explore advanced concepts in tensor rank, including numeric-to-symbolic transfer techniques and their applications in mathematics and computer science.

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

IEEE

Noise Sensitivity on the p-Biased Hypercube

Explore noise sensitivity on p-biased hypercubes, examining shell thresholds and speculating on results in this concise mathematical analysis.

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

IEEE

Breaking of 1RSB in Random MAX-NAE-SAT

Explore the intricacies of random MAX-NAE-SAT, focusing on 1RSB breaking, solution spaces, and key concepts like garnet transition and moment bounds.

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

IEEE

Approximating Constraint Satisfaction Problems on High Dimensional Expanders

Explore high-dimensional expanders and their role in approximating constraint satisfaction problems, with insights on natural collections and general expanders.

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

IEEE

Sampling Graphs Without Forbidden Subgraphs and Unbalanced Expanders With Negligible Error

Explore efficient graph sampling techniques and unbalanced expanders, focusing on avoiding forbidden subgraphs and achieving negligible error rates in computational applications.

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

IEEE

Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

Explore quantum communication's exponential advantage over logarithmic approximate rank, focusing on the SINK function and its implications for communication complexity theory.

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

IEEE

Finding Monotone Patterns in Sublinear Time

Explore efficient algorithms for detecting monotone patterns in large datasets, focusing on sublinear time complexity and adaptive techniques for various pattern types.

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

IEEE

Polylogarithmic Guarantees for Generalized Reordering Buffer Management

Explore polylogarithmic guarantees for generalized reordering buffer management, covering special cases, previous work, and applications in scheduling block devices.

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

IEEE

Relaxed Locally Decodable Codes

Explore advanced concepts in coding theory, focusing on relaxed locally decodable codes and their applications in data storage and transmission.

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

IEEE

Relaxed Locally Decodable Codes - Part 1

Explore coding theory, locally decodable codes, and their relaxed variants, focusing on applications, logical polynomials, and synthesis techniques in this IEEE presentation.

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

IEEE

Indistinguishability Obfuscation from Well Founded Assumptions - Part 1

Explore the concept of indistinguishability obfuscation, its historical perspective, and related topics like pseudorandom objects and learning with errors in computer science.

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

IEEE

Indistinguishability Obfuscation from Well Founded Assumptions - Part 3

Explore advanced cryptographic concepts like indistinguishability obfuscation, learning parity with noise, and structured seed PRGs. Delve into degree-2.5 integer PRGs and their applications in cryptography.

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