YoVDO

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

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Algorithm Analysis Courses Theoretical Computer Science Courses Complexity Theory Courses Hypergraphs Courses

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

The Next Generation of Infrastructure
Delft University of Technology via edX
The Beauty and Joy of Computing - AP® CS Principles Part 2
University of California, Berkeley via edX
Advanced Data Structures in Java
University of California, San Diego via Coursera
Theory of Computation
Indian Institute of Technology Kanpur via Swayam
离散数学
Shanghai Jiao Tong University via Coursera