On the computational power of Boolean decision lists
From MaRDI portal
Publication:853647
DOI10.1007/s00037-005-0203-0zbMath1105.68043OpenAlexW2070053951MaRDI QIDQ853647
Publication date: 17 November 2006
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-005-0203-0
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (9)
Hardness Characterisations and Size-width Lower Bounds for QBF Resolution ⋮ Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Lifting Theorem with Applications to Symmetric Functions
This page was built for publication: On the computational power of Boolean decision lists
