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.