most citedOn Separation Logic, Computational Independence, and Pseudorandomness (Extended Version)

1 citations · 1 across the 2 of their papers we have counts for

collaborators
Showing cs.CCShow all

1 paper · 1 filter

cs.CC2023

An Arithmetic Theory for the Poly-Time Random Functions

Melissa Antonelli, Ugo Dal Lago, Davide Davoli +2

We introduce a new bounded theory RS^1_2 and show that the functions which are Sigma^b_1-representable in it are precisely random functions which can be computed in polynomial time…