On the Implementation of Huge Random Objects
From MaRDI portal
Publication:5390577
DOI10.1137/080722771zbMath1225.68132OpenAlexW2141431275MaRDI QIDQ5390577
Shafi Goldwasser, Oded Goldreich, Asaf Nussboim
Publication date: 4 April 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/60920
random graphspseudorandomnessmonotone graph propertiesrandom functionsrandom codesrandom walks on regular graphs
Random graphs (graph-theoretic aspects) (05C80) General topics in the theory of computing (68Q01) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
On mappings on the hypercube with small average stretch ⋮ Multilinear Pseudorandom Functions ⋮ Bi-Lipschitz bijection between the Boolean cube and the Hamming ball ⋮ Derandomized constructions of \(k\)-wise (almost) independent permutations ⋮ Decompositions of graphs of functions and fast iterations of lookup tables ⋮ Security levels in steganography -- insecurity does not imply detectability ⋮ Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ Unnamed Item ⋮ Bounded-depth circuits cannot sample good codes ⋮ Upper and lower bounds on black-box steganography ⋮ Pseudorandom Functions: Three Decades Later
