文章基本信息

标题：Limits of Preprocessing
本地全文：下载
作者：Yuval Filmus ; Yuval Ishai ; Avi Kaplan 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：169
页码：17:1-17:22
DOI：10.4230/LIPIcs.CCC.2020.17
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：It is a classical result that the inner product function cannot be computed by an ACâ° circuit [Merrick L. Furst et al., 1981; MiklÃ³s Ajtai, 1983; Johan HÃ¥stad, 1986]. It is conjectured that this holds even if we allow arbitrary preprocessing of each of the two inputs separately. We prove this conjecture when the preprocessing of one of the inputs is limited to output n + n/(log^{Ï(1)} n) bits. Our methods extend to many other functions, including pseudorandom functions, and imply a (weak but nontrivial) limitation on the power of encoding inputs in low-complexity cryptography. Finally, under cryptographic assumptions, we relate the question of proving variants of the main conjecture with the question of learning ACâ° under simple input distributions.
关键词：circuit; communication complexity; IPPP; preprocessing; PRF; simultaneous messages