Name
Abstract | ||
|---|---|---|
In this paper, we consider a biologically-inspired Boolean function, called (P^n_D), which models a task for detecting specific global spatial arrangements of local visual patterns on a 2-dimensional map. We prove that (P^n_D) is computable by a threshold circuit of size (O(sqrt{n}log n)), which is improvement on the previous upper bound O(n). We also show that the size of our circuit is almost optimal up to logarithmic factor: we show that any threshold circuit computing (P^n_D) needs size (Omega(sqrt{n}/log n)). |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-15612-5_27 | WALCOM |
Field | DocType | Citations |
Boolean function,Binary logarithm,Discrete mathematics,Combinatorics,Computer science,Upper and lower bounds,Omega,Logarithm,Electronic circuit,Visual patterns | Conference | 1 |
PageRank | References | Authors |
0.37 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kei Uchizawa | 1 | 74 | 12.89 |
| Daiki Yashima | 2 | 1 | 0.71 |
| Xiao Zhou | 3 | 325 | 43.69 |