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

affine disperseraffine extractorsDNF

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

(16)

• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Property testing lower bounds via a generalization of randomized parity decision trees
• Expander-based cryptography meets natural proofs
• Hilbert cubes meet arithmetic sets
• 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?)
• Tree tribes and lower bounds for switching lemmas
• scientific article; zbMATH DE number 7471669 (Why is no real title available?)
• Expander-Based Cryptography Meets Natural Proofs
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)
• scientific article; zbMATH DE number 7250145 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• Improving \(3N\) circuit complexity lower bounds
• Explicit directional affine extractors and improved hardness for linear branching programs
• Bounded simultaneous messages
• Low-degree polynomials are good extractors

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)