Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NON-NEGATIVE RANK:
Reports tagged with non-negative rank:
TR17-185 | 28th November 2017
Makrand Sinha

#### Lower Bounds for Approximating the Matching Polytope

We prove that any extended formulation that approximates the matching polytope on $n$-vertex graphs up to a factor of $(1+\varepsilon)$ for any $\frac2n \le \varepsilon \le 1$ must have at least ${n}\choose{{\alpha}/{\varepsilon}}$ defining inequalities where $0<\alpha<1$ is an absolute constant. This is tight as exhibited by the $(1+\varepsilon)$ approximating linear ... more >>>

TR19-034 | 5th March 2019
Pavel Hrubes

#### On $\epsilon$-sensitive monotone computations

We show that strong-enough lower bounds on monotone arithmetic circuits or the non-negative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $f\in {\mathbb {R}}[x_1,\dots, x_n]$ of degree $d$ has an arithmetic circuit of size $s$ then \$(x_1+\dots+x_n+1)^d+\epsilon ... more >>>

ISSN 1433-8092 | Imprint