Počet záznamů: 1  

On ϵ-sensitive monotone computations

  1. 1.
    0531552 - MÚ 2021 RIV CH eng J - Článek v odborném periodiku
    Hrubeš, Pavel
    On ϵ-sensitive monotone computations.
    Computational Complexity. Roč. 29, č. 2 (2020), č. článku 6. ISSN 1016-3328. E-ISSN 1420-8954
    Grant CEP: GA ČR(CZ) GX19-27871X
    Institucionální podpora: RVO:67985840
    Klíčová slova: arithmetic circuit complexity * extension complexity * nonnegative rank
    Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
    Impakt faktor: 1.353, rok: 2020
    Způsob publikování: Omezený přístup
    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.
    Trvalý link: http://hdl.handle.net/11104/0310182

     
    Název souboruStaženoVelikostKomentářVerzePřístup
    Hrubes1.pdf3365.1 KBVydavatelský postprintvyžádat
     
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.