On the Implementation of Huge Random Objects

DOI10.1137/080722771zbMath1225.68132OpenAlexW2141431275MaRDI QIDQ5390577

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

zbMATH Keywords

random graphspseudorandomnessmonotone graph propertiesrandom functionsrandom codesrandom walks on regular graphs

Mathematics Subject Classification ID

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 (11)

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

This page was built for publication: On the Implementation of Huge Random Objects