The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs
Offered By: IEEE via YouTube
Course Description
Overview
Explore the intricacies of counting cliques in Erdos-Renyi hypergraphs in this 18-minute IEEE conference talk. Delve into uniform hypergraphs, lower bounds, and motivation behind the research. Gain insights into related work and the main theorem presented. Learn about proof techniques, including random KQ accounting and its reduction. Understand the role of binary expansions in the analysis. Conclude by examining open problems in the field, providing a comprehensive overview of average-case complexity in hypergraph clique counting.
Syllabus
Intro
Uniform Hypergraphs
Lower Bounds
Motivation
Related Work
Main Theorem
Proof Techniques
Random KQ Accounting
Reducing KQ Accounting
Binary Expansions
Open Problems
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
Introduction to High Dimensional Expanders - Irit DinurInstitute for Advanced Study via YouTube Graph Representation Learning and Its Applications to Biomedicine
Applied Algebraic Topology Network via YouTube Asaf Shapira - Local vs Global Combinatorics
International Mathematical Union via YouTube Tropical Solutions to Hard Problems in Auction Theory and Neural Networks - Lecture II
Hausdorff Center for Mathematics via YouTube Applied Topology for Discrete Structures
Applied Algebraic Topology Network via YouTube