7

If you modify a balanced binary search tree (whose inorder traversal is the sequence order) so that each node stores the minimum value of its descendants (and if you know the path to x) then you can easily find the nearest smaller value: it must either be on the path to x, or in a left subtree descending from the path. In the first case, you have a ...


7

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 maintain the value at each gate in the circuit. When you change the $i$-th bit of $y$, simply propagate that change along the DAG of the circuit, starting from the ...


5

One can reverse the roles of elements and sets. This can be seen by considering a Boolean matrix of size $m\times n$ where there are $m$ sets and $n$ is the size of the universe. The $i$th row corresponds to the characteristic vector of the $i$th set. Transposing this matrix reverses the roles of sets and elements ($n$ sets and $m$ elements). Now the ...


5

A first observation in the direction of decidability of ODEs is this paper by Avigad, Clarke and Gao, which classifies the complexity of $\delta$-decidability, in which solutions are to be found within a certain bounded error (the "delta") in one direction. one of the main results is that $\delta$-solvability of (Lipschitz-continuous) ODEs is $\mathrm{...


5

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 and subtracting the old value for each changed monomial. If you have a read-once formula for $P$ (i.e. every variable appears at a single leaf of the formula ...


4

The best I can find for this is $O(\log n)$ amortized update time with constant query time. The basic idea is that if you know both preorder and postorder for a tree, you can recover reachability: there is a path from $x$ to $y$ iff $x$ is before $y$ in preorder and after it in postorder. There are several data structures that can maintain a list of items, ...


3

Think about your question in reverse: suppose you have a dynamic data structure for some problem — does that imply that you can solve it statically, faster by a log? Why should it? And in fact it is not true. Consider range counting in one-dimensional intervals, in a comparison model of computation. That is, the data is a set $S$ of numbers, the query is an ...


2

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$: https://eccc.weizmann.ac.il/report/2011/128/ Another nice $TC^0$-decomposition is based on so-called TSLPs in the paper "A Universal Tree Balancing Theorem" (...


1

There is an $\tilde{O}(nK)$ time algorithm given by Chao Xu: Faster pseudo-polynomial time algorithms for PARTITION


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