On ϵ-sensitive monotone computations

0531552 - MÚ 2021 RIV CH eng J - Journal Article
Hrubeš, Pavel
On ϵ-sensitive monotone computations.
Computational Complexity. Roč. 29, č. 2 (2020), č. článku 6. ISSN 1016-3328. E-ISSN 1420-8954
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : arithmetic circuit complexity * extension complexity * nonnegative rank
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 1.353, year: 2020
Method of publishing: Limited access
https://doi.org/10.1007/s00037-020-00196-6

We show that strong-enough lower bounds on monotone arithmetic circuits or the nonnegative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial f∈ R[x1, ⋯ , xn] of degree d has an arithmetic circuit of size s then (x1+⋯+xn+1)d+ϵf has a monotone arithmetic circuit of size O(sd2+ nlog n) , for some ϵ> 0. Second, if f: { 0 , 1 } n→ { 0 , 1 } is a Boolean function, we associate with f an explicit exponential-size matrix M(f) such that the Boolean circuit size of f is at least Ω(min ϵ>(rk +(M(f) - ϵJ)) - 2 n) , where J is the all-ones matrix and rk + denotes the nonnegative rank of a matrix. In fact, the quantity min ϵ>(rk +(M(f) - ϵJ)) characterizes how hard is it to distinguish rejecting and accepting inputs of f by means of a linear program. Finally, we introduce a proof system resembling the monotone calculus of Atserias et al. (J Comput Syst Sci 65:626–638, 2002) and show that similar ϵ-sensitive lower bounds on monotone arithmetic circuits imply lower bounds on proof-size in the system.
Permanent Link: http://hdl.handle.net/11104/0310182