The complexity of Boolean functions in different characteristics

DOI10.1007/s00037-010-0290-4zbMath1213.68309OpenAlexW2158501005MaRDI QIDQ626677

Parikshit Gopalan, Shachar Lovett, Amir Shpilka

Publication date: 18 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-010-0290-4

zbMATH Keywords

complexitypolynomialslower boundsRepresentations of Boolean functions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Predicate encryption from bilinear maps and one-sided probabilistic rank ⋮ Scalable zero knowledge via cycles of elliptic curves ⋮ On the modulo degree complexity of Boolean functions ⋮ Communication Lower Bounds Using Directional Derivatives

This page was built for publication: The complexity of Boolean functions in different characteristics