On the Power of Small-Depth Computation

DOI10.1561/0400000033zbMath1187.68245OpenAlexW4205778826MaRDI QIDQ3400006

Emanuele Viola

Publication date: 18 January 2010

Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/0400000033

zbMATH Keywords

cryptography in bounded depth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Correlation lower bounds from correlation upper bounds ⋮ Local reduction ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ The function-inversion problem: barriers and opportunities ⋮ Block-symmetric polynomials correlate with parity better than symmetric ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Arithmetic circuits: the chasm at depth four gets wider ⋮ Unnamed Item ⋮ The minrank of random graphs ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: On the Power of Small-Depth Computation