The complexity of DNF of parities

DOI10.1145/2840728.2840734MaRDI QIDQ2800552zbMATH OpenOpenAlexFDO

Authors Gil Cohen, Igor Shinkar

Publication date 15 April 2016

Published in Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2840728.2840734

zbMATH Keywords

DNFaffine extractorsaffine disperser

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Approximating Boolean functions with depth-2 circuits
• On the complexity of the disjunctive normal form of threshold functions
• Top-down lower bounds for depth-three circuits
• Approximation by DNF: Examples and Counterexamples
• scientific article; zbMATH DE number 1559525

Cited in

(13)

• Hilbert cubes meet arithmetic sets
• Expander-based cryptography meets natural proofs
• Improving \(3N\) circuit complexity lower bounds
• An elementary proof of a \(3n - o(n)\) lower bound on the circuit complexity of affine dispersers
• scientific article; zbMATH DE number 4047104 (Why is no real title available?)
• scientific article; zbMATH DE number 7471669 (Why is no real title available?)
• Expander-Based Cryptography Meets Natural Proofs
• Tree tribes and lower bounds for switching lemmas
• scientific article; zbMATH DE number 7250145 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Property testing lower bounds via a generalization of randomized parity decision trees
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)

This page was built for publication: The complexity of DNF of parities

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