A Duality Between One-Way Functions and Average-Case Symmetry of Information

ePrint Report: A Duality Between One-Way Functions and Average-Case Symmetry of Information

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira

Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) established that if SoI holds for time-bounded …

case complexity duality eprint report functions information problem report strings understanding