Computational Complexity

We consider the algorithm by Ferson et al. (Reliab Comput 11(3):207--233, 2005) designed for solving the NP-hard problem of computing the maximal sample variance over interval data, motivated by robust statistics. The formulation can be written as ...${}^{\mathrm{}}{\mathrm{}}^{}$${\mathrm{}}^{}$$$${\mathrm{}}^{}{}^{\mathrm{}}$${}^{\mathrm{}}$$\mathrm{}$${\mathrm{}}^{\mathrm{}}$${}^{}$${}^{\mathrm{}\frac{\mathrm{}}{}}$$$

The combinatorial refinement techniques have proven to be an efficient approach to isomorphism testing for particular classes of graphs. If the number of refinement rounds is small, this puts the corresponding isomorphism problem in a low-...${\mathbb{}}_{}$$\mathcal{}$$$${}^{}$$\mathrm{}$$\mathrm{}$$\mathcal{}\mathrm{}$

We introduce the problem of constructing explicit variety evasive subspace families. Given a family $\mathcal{F}$ of subvarieties of a projective or affine space, a collection $\mathcal{H}$ of projective or affine $k$-subspaces is $(\mathcal{F},ϵ)$-evasive if for every $\mathcal{V}\in \mathcal{F}$, all but at ...$$$\mathcal{}$$\mathcal{}$

We use the approximation method of Razborov to analyze the locality barrier which arose from the investigation of the hardness magnification approach to complexity lower bounds. Adapting a limitation of the approximation method obtained by ...${\mathsf{}}^{\mathrm{}}$

We show that, for every homogeneous polynomial of degree $d$, if it has determinantal complexity at most $s$, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most $O(d^{5}s)$. Moreover, we show that for most ...$\mathrm{}$$$

The currently fastest known algorithm for k-SAT is PPSZ, named after its inventors (Paturi et al. in J ACM 52(3):337-364, 2005. ). Analyzing its running time is much easier for input formulas with a unique ...