PreviousNext

__
TR24-138
| 8th September 2024
__

Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker#### Fully Characterizing Lossy Catalytic Computation

__
TR24-137
| 9th September 2024
__

Dean Doron, William Hoza#### Implications of Better PRGs for Permutation Branching Programs

__
TR24-136
| 4th September 2024
__

Shuichi Hirahara, Zhenjian Lu, Igor Oliveira#### One-Way Functions and pKt Complexity

PreviousNext

Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker

A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, "catalytic" tape, which, while being available as a work tape, has the caveat of being initialized with an arbitrary string, which must be preserved at the end of the computation. ... more >>>

Dean Doron, William Hoza

We study the challenge of derandomizing constant-width standard-order read-once branching programs (ROBPs). Let $c \in [1, 2)$ be any constant. We prove that if there are explicit pseudorandom generators (PRGs) for width-$6$ length-$n$ permutation ROBPs with error $1/n$ and seed length $\widetilde{O}(\log^c n)$, then there are explicit hitting set generators ... more >>>

Shuichi Hirahara, Zhenjian Lu, Igor Oliveira

We introduce $\mathrm{pKt}$ complexity, a new notion of time-bounded Kolmogorov complexity that can be seen as a probabilistic analogue of Levin's $\mathrm{Kt}$ complexity. Using $\mathrm{pKt}$ complexity, we upgrade two recent frameworks that characterize one-way functions ($\mathrm{OWFs}$) via symmetry of information and meta-complexity, respectively. Among other contributions, we establish the following ... more >>>

PreviousNext