On the Power of Small-Depth Computation
From MaRDI portal
Publication:3400006
DOI10.1561/0400000033zbMath1187.68245MaRDI QIDQ3400006
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
68Q25: Analysis of algorithms and problem complexity
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, The minrank of random graphs, Unnamed Item, Unnamed Item, Correlation lower bounds from correlation upper bounds, Arithmetic circuits: the chasm at depth four gets wider, Local reduction, The function-inversion problem: barriers and opportunities, Block-symmetric polynomials correlate with parity better than symmetric