scientific article; zbMATH DE number 5605137

MaRDI QIDQ3396635zbMATH OpenFDO

Authors Alexander A. Sherstov

Publication date 19 September 2009

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Measures of information, entropy (94A17)

Cited in

(15)

• The hardest halfspace
• Degree-uniform lower bound on the weights of polynomials with given sign function
• Polynomial threshold functions and Boolean threshold circuits
• Hardness amplification and the approximate degree of constant-depth circuits
• An Algebraic Perspective on Boolean Function Learning
• A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
• How low can approximate degree and quantum query complexity be for total Boolean functions?
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Algorithmic Polynomials
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• One-way multiparty communication lower bound for pointer jumping with applications
• Rectangles are nonnegative juntas
• On the degree of Boolean functions as polynomials over \(\mathbb{Z}_m\)
• The approximate degree of DNF and CNF formulas
• On the parity complexity measures of Boolean functions

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3396635)