7 votes
Accepted

Maintaining the value of a polynomial over a dynamically updated input

Your idea generalizes as follows: given an algebraic circuit (over the finite field) or Boolean circuit (computing the bit-wise representation of your finite field elements) computing $P$, then ...
Joshua Grochow's user avatar
5 votes

Maintaining the value of a polynomial over a dynamically updated input

It's easy to modify your monomial-storing approach so that each update takes time only proportional to the number of changed monomials: just update the total polynomial value by adding the new value ...
David Eppstein's user avatar
2 votes
Accepted

What are some techniques for "balancing" a tree beside heavy-light and centroid decomposition?

The paper "Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth" (Elberfeld, Jacobi, Tantau) gives a nice balanced tree decomposition based on tree contraction in $TC^0$: ...
Danny's user avatar
  • 500
1 vote

Interesting variation to the subset sum problem

There is an $\tilde{O}(nK)$ time algorithm given by Chao Xu: Faster pseudo-polynomial time algorithms for PARTITION
hqztrue's user avatar
  • 112

Only top scored, non community-wiki answers of a minimum length are eligible