ITC Conference: P4-Free Partition and Cover Numbers & Applications

Explore a conference talk from the 2021 ITC Conference focusing on P4-free partition and cover numbers and their applications. Delve into the research presented by Alex R. Block, Simina Branzei, Hemanta K. Maji, Himanshi Mehta, Tamalika Mukherjee, and Hai H. Nguyen from Purdue University. Learn about distilling shared keys and private randomness, cryptographic complexity lower bounds, and leakage resilience upper bounds. Examine the communication complexity of computing Boolean functions relative to the EQ-oracle and understand the significance of P4-free bipartite graphs. Discover the connections between flat joint distributions, bipartite graphs, and joint distributions requiring no genie assistance. Investigate the relationship between P-graphs and leakage resilience, and explore the link to shared key and randomness extraction. Analyze the hardness of P4-free partition and cover numbers, their connections to non-deterministic communication complexity, and examine graphs with high P4-free partition and cover numbers. Gain insights into tight estimations and draw conclusions from this comprehensive exploration of P4-free partitions and covers in various applications.

Intro
Distilling Shared Keys & Private Randomness
Application 1: Cryptographic Complexity Lower Bounds
Cryptographic Leakge Resilience Upper Bounds BMN17
Communication Complexity Computation of Boolean function () relative to the EQ-oracle
PA-free Bipartite Graphs: The Protagonist
Intuition: P4-free Bipartite Graphs
Flat Joint Distribution
Flat Distributions as Bipartite Graphs
Joint Distributions Needing No Genie Assistance
P-Graphs have no Leakage Resilience
Illustrative Example
Connection to Shared Key & Randomness Extraction
Existing Information-theoretic & Edge-covering Measures are Imprecise
Hardness of P-free Partition Number
Graphs with High PA-free Partition Number
Connection to Non-deterministic Communication Complexity
Hardness of P-free Cover Number
Graphs with High PA-free Cover Number
Tight Estimations
Conclusions