Some Algebraic Problems with Connections to Circuit Complexity of Dynamic Data Structures

摘要

While researching dynamic data structures of polynomial size thatare updated by extremely simple circuits, we have come acrossmany interesting algebraic problems. Some of these simplequestions about small sums and products in an algebra wouldgive lower bounds on the complexity of dynamic data structures.