2026-07-25T22:05:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20513 2024-08-06T05:20:07Z ddc:004 open_access

On the Power of Adaptivity for Function Inversion Gajulapalli, Karthik Golovnev, Alexander King, Samuel Function Inversion Non-Adaptive lower bounds Communication Complexity We study the problem of function inversion with preprocessing where, given a function f : [N] → [N] and a point y in its image, the goal is to find an x such that f(x) = y using at most T oracle queries to f and S bits of preprocessed advice that depend on f. The seminal work of Corrigan-Gibbs and Kogan [TCC 2019] initiated a line of research that shows many exciting connections between the non-adaptive setting of this problem and other areas of theoretical computer science. Specifically, they introduced a very weak class of algorithms (strongly non-adaptive) where the points queried by the oracle depend only on the inversion point y, and are independent of the answers to the previous queries and the S bits of advice. They showed that proving even mild lower bounds on strongly non-adaptive algorithms for function inversion would imply a breakthrough result in circuit complexity. We prove that every strongly non-adaptive algorithm for function inversion (and even for its special case of permutation inversion) must have ST = Ω(N log (N) log (T)). This gives the first improvement to the long-standing lower bound of ST = Ω(N log N) due to Yao [STOC 90]. As a corollary, we conclude the first separation between strongly non-adaptive and adaptive algorithms for permutation inversion, where the adaptive algorithm by Hellman [TOIT 80] achieves the trade-off ST = O(N log N). Additionally, we show equivalence between lower bounds for strongly non-adaptive data structures and the one-way communication complexity of certain partial functions. As an example, we recover our lower bound on function inversion in the communication complexity framework. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karthik Gajulapalli and Alexander Golovnev and Samuel King 2024 Is Part Of LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2024.5 urn:nbn:de:0030-drops-205137 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.5 eng https://creativecommons.org/licenses/by/4.0/legalcode