NP-complete problems cannot have efficient algorithms unless P = NP. Due to their importance in practice, however, it is useful to improve the known exponential-time algorithms for NP-complete problems. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and the ... more >>>

We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial f computed by a constant-depth circuit over rational numbers, and outputs a list L of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of f computable by constant-depth circuits. This ... more >>>

We present a deterministic 2^{k^{\mathcal{O}(1)}} \text{poly}(n,d) time algorithm for decomposing d-dimensional, width-n tensors of rank at most k over \mathbb{R} and \mathbb{C}. This improves upon the previous randomized algorithm of Peleg, Shpilka, and Volk (ITCS '24) that takes 2^{k^{k^{\mathcal{O}(k)}}} \text{poly}(n,d) time and the deterministic n^{k^k} time algorithms of Bhargava, Saraf, ... more >>>

While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when ... more >>>