Name
Abstract | ||
|---|---|---|
We prove that a general family of hard core predicates requires circuits of depth (l-0(1))log n/log log n or super-polynomial size to be realized. This lower bound is essentially tight. For constant depth circuits, an exponential
lower bound on the size is obtained. Assuming the existence of one-way functions, we explicitly construct a one-way function
f(x) such that for any circuit c from a family of circuits as above, c(x) is almost always predictable from f(x).
|
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/BFb0052224 | CRYPTO |
Keywords | Field | DocType |
one-way function,pseudo-randomness,computing hard core predicates,small-depth circuit,one way function,lower bound | Log-log plot,Discrete mathematics,Binary logarithm,Combinatorics,Exponential function,Upper and lower bounds,First-order logic,Almost surely,One-way function,Mathematics,Computational complexity theory | Conference |
Volume | ISSN | ISBN |
1294 | 0302-9743 | 3-540-63384-7 |
Citations | PageRank | References |
3 | 0.47 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mikael Goldmann | 1 | 210 | 27.05 |
| Mats Näslund | 2 | 141 | 21.58 |