Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TIME/MEMORY TRADEOFF:
TR20-089 | 8th June 2020
Dror Chawin, Iftach Haitner, Noam Mazor

#### Lower Bounds on the Time/Memory Tradeoff of Function Inversion

Revisions: 1

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 >>>

TR20-090 | 10th June 2020
Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian

#### Tight Quantum Time-Space Tradeoffs for Function Inversion

Revisions: 1

In function inversion, we are given a function \$f: [N] \mapsto [N]\$, and want to prepare some advice of size \$S\$, such that we can efficiently invert any image in time \$T\$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower ... more >>>

ISSN 1433-8092 | Imprint