The complexity of DNF of parities

DOI10.1145/2840728.2840734zbMATH Open1334.68065OpenAlexW2282923620MaRDI QIDQ2800552FDOQ2800552

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

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

zbMATH Keywords

DNFaffine extractorsaffine disperser

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (12)

• Expander-Based Cryptography Meets Natural Proofs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Property testing lower bounds via a generalization of randomized parity decision trees
• 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
• Hilbert cubes meet arithmetic sets
• Title not available (Why is that?)
• Mathematical Foundations of Computer Science 2005
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Title not available (Why is that?)

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)