Name
Abstract | ||
|---|---|---|
We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polyno- mials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Remote Point Problem (introduced in (3)). More precisely, proving lower bounds for ABPs with help polynomials is related to the Remote Point Problem w.r.t. the rank metric, and for constant-depth circuits with help functions it is related to the Remote Point Problem w.r.t. the Hamming metric. For algebraic branching programs with help polynomials with some degree restrictions we show exponential size lower bounds for explicit polynomials. |
Year | Venue | Keywords |
|---|---|---|
2009 | Clinical Orthopaedics and Related Research | constant-depth circuits,remote point problem.,algebraic branching programs,boolean circuits,lower bound,branching program |
DocType | Volume | Citations |
Journal | abs/0911.4 | 0 |
PageRank | References | Authors |
0.34 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikraman Arvind | 1 | 296 | 38.18 |
| Srikanth Srinivasan | 2 | 132 | 21.31 |