Name
Title | ||
|---|---|---|
Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees. |
Abstract | ||
|---|---|---|
We show exponential lower bounds for circuits with up to an exponential number of parse trees, strengthening the work of Lagarde et al. [Electronic Colloquium on Comput Complexity (ECCC) vol 23, no 94, 2016], who prove such a result for Unique Parse Tree (UPT) circuits which have a single parse tree. The polynomial we prove a lower bound for is in fact computable by a polynomial-sized non-commutative circuit. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.4230/LIPIcs.MFCS.2017.41 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | DocType | Volume |
Non-commutative arithmetic circuits, Algebraic branching programs, Formulas, Lower bounds, Polynomial identity testing, Parse trees of circuits, 12Y05, 68Q17, 68Q25 | Conference | 24 |
Issue | ISSN | Citations |
3 | 1420-8954 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guillaume Lagarde | 1 | 0 | 0.68 |
| Nutan Limaye | 2 | 134 | 20.59 |
| Srikanth Srinivasan | 3 | 132 | 21.31 |