Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FUNCTION INVERTERS:
Reports tagged with function inverters:
TR20-089 | 8th June 2020
Dror Chawin, Iftach Haitner, Noam Mazor

Lower Bounds on the Time/Memory Tradeoff of Function Inversion

We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an $s$-bit advice for a randomly chosen function $f\colon [n] \mapsto [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$ (i.e., to find $x$ such that $f(x)=y$). ... more >>>




ISSN 1433-8092 | Imprint