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 ...
- 37.8k
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 ...
- 51.1k
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$:
...
- 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
- 112
Only top scored, non community-wiki answers of a minimum length are eligible