Extremely Uniform Branching Programs

We propose a new descriptive complexity notion of uniformity for branching programs solving problems defined on structured data. We observe that FO[=]-uniform ( n -way) branching programs are unable to solve the tree evaluation problem studied by Cook, McKenzie, Wehr, Braverman and Santhanam in 2012 because such programs possess their thriftiness property. Similarly, FO[=]-uniform ( n -way) branching programs are unable to solve the P-complete GEN problem because such programs possess the incremental property studied by Gál, Koucký and McKenzie in 2008. Joint work with Andreas Krebs and Pierre McKenzie to appear in NCMA 2014. 11: 45 12: 00 Break

Authors

• Michaël Cadilhac

Keywords

No keywords are indexed for this paper.