Computational Complexity

We show that for any non-real algebraic number q, such that $|q-1|>1$ or $\Re (q)>\frac{3}{2}$ it is #P-hard to compute a multiplicative (resp. additive) approximation to the absolute value (resp. argument) of the chromatic polynomial evaluated at q on planar ...$\mathrm{}\mathrm{}$

A matrix is blocky if it is a "blowup" of a permutation matrix. The blocky rank of a matrix M is the minimum number of blocky matrices that linearly span M. Hambardzumyan, Hatami and Hatami defined blocky rank and showed that it is connected to ...

For a polynomial f, a weighted sum-of-squares representation (SOS) has the form $f={\sum }_{i\in [s]}{c}_i{f}_i^2$, where the weights$c_i$ are field elements. The size of the representation is the number of monomials that appear across the $f_i$'s. Its minimum across all ...

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $P⊈{\mathit{NC}}^1$). Karchmer et al. (Comput Complex 5(3/4):191–204, 1995) suggested to approach this problem by proving that depth ...$$${\mathit{}}^{\mathrm{}}$

It is a classical result that the inner product function cannot be computed by an ${\mathrm{AC}}^0$ circuit. It is conjectured that this holds even if we allow arbitrary preprocessing of each of the two inputs separately. We prove this conjecture when the ...${}^{\mathrm{}}$${\mathrm{}}^{\mathrm{}}$

An ordering constraint satisfaction problem (OCSP) is defined by a family $\mathcal{F}$ of predicates mapping permutations on $\{1,\dots ,k\}$ to $\{0,1\}$. An instance of Max-OCSP($\mathcal{F}$) on n variables consists of a list of constraints, each consisting of a predicate from $\mathcal{F}$ ...$\mathcal{}$$\mathcal{}$$\mathrm{}$$\mathrm{}\mathrm{}$$\sqrt{}$

The constraint satisfaction problem (CSP) on a finite relational structure B is to decide, given a set of constraints on variables where the relations come from B, whether or not there is an assignment to the variables satisfying all of the ...