IEEE FOCS: Foundations of Computer Science Talks & Presentations

IEEE

Coded Trace Reconstruction in a Constant Number of Traces

Learn about coded trace reconstruction for DNA storage, exploring constant-trace methods, coding techniques, and related concepts like BDC capacity and binary upper bounds.

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

IEEE

Explicit Near-Fully X-Ramanujan Graphs

Explore finite graphs resembling infinite ones, focusing on Ramanujan graphs and spectral properties. Learn about matrix-weighted polynomials and permutation-based approaches.

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

IEEE

Network Coding Gaps for Completion Times of Multiple Unicasts

Explore network coding gaps in multiple unicasts, analyzing completion times, protocols, and bounds. Insights on cut bounds, coding gaps, and open questions in network communication.

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

IEEE

An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions

Explore advanced techniques in combinatorial auctions, focusing on subadditive prophet inequalities and their applications in algorithmic game theory and mechanism design.

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

IEEE

Coordinate Methods for Matrix Games

Explore efficient algorithms for solving matrix games, focusing on coordinate methods and their implementation challenges and benefits.

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

IEEE

Binary Interactive Error Resilience Beyond 1/8

Explore advanced binary error resilience techniques, surpassing the 1/8 barrier. Learn about innovative protocols for message exchange and codes with few codewords.

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

IEEE

Independent Set on P_k-Free Graphs in Quasi-Polynomial Time

Explore efficient algorithms for solving the Independent Set problem on P_k-Free Graphs, including novel approaches and complexity analysis.

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

IEEE

Smoothed Complexity of 2-player Nash Equilibria

Explore smoothed complexity in 2-player Nash equilibria, covering algorithmic hardness, approximation challenges, and novel approaches to finding equilibria in perturbed games.

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

IEEE

On Light Spanners, Low-Treewidth Embeddings and Efficient Traversing in Minor-Free Graphs

Explore efficient graph traversal techniques using light spanners and low-treewidth embeddings, with applications to minor-free graphs and approximation algorithms.

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

IEEE

Pseudospectral Shattering the Sign Function and Diagonalization in Nearly Matrix Multiplication Time

Explore advanced matrix algorithms, including pseudospectral shattering and diagonalization techniques, for efficient computation in nearly matrix multiplication time.

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

IEEE

Communication Complexity of Nash Equilibrium in Potential Games

Explore communication complexity in potential games, focusing on Nash equilibrium, congestion games, and proof structures for hardness results.

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

IEEE

LDPC Codes Achieve List Decoding Capacity

Explores LDPC codes' list-decoding capacity, discussing error correction, code families, and local properties of random linear codes. Presents new findings and open problems in coding theory.

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

IEEE

Near Optimal Linear Algebra in the Online and Sliding Window Models

Explore near-optimal linear algebra techniques for streaming and sliding window models, focusing on randomized algorithms and their applications in data analysis.

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

IEEE

Stochastic Weighted Matching - 1-Epsilon Approximation

Explore stochastic weighted matching algorithms, including Monte Carlo analysis, vertex-independent matching, and greedy approaches for efficient approximation solutions.

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

IEEE

Hypergraph K-Cut for Fixed K in Deterministic Polynomial Time

Explore deterministic polynomial-time algorithms for hypergraph k-cut problems, focusing on fixed k values. Learn about structural theorems, techniques, and open questions in this field.

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