scientific article
From MaRDI portal
Publication:3396635
zbMath1169.68438MaRDI QIDQ3396635
Publication date: 19 September 2009
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Hardness Amplification and the Approximate Degree of 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 Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Algorithmic Polynomials ⋮ How low can approximate degree and quantum query complexity be for total Boolean functions? ⋮ The hardest halfspace ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ On the parity complexity measures of Boolean functions ⋮ Degree-uniform lower bound on the weights of polynomials with given sign function ⋮ Rectangles Are Nonnegative Juntas ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ An Algebraic Perspective on Boolean Function Learning ⋮ Unnamed Item ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities
