Approximating Boolean Functions with Depth-2 Circuits

DOI10.1137/14097402XzbMath1330.68100MaRDI QIDQ3451753

Li-Yang Tan, Eric Blais

Publication date: 18 November 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

approximationBoolean functionsdepth-2 circuits

Mathematics Subject Classification ID

Uses Software

• JBool

Cites Work

• The average sensitivity of bounded-depth circuits
• The average sensitivity of an intersection of half spaces
• Learning intersections and thresholds of halfspaces
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• Constant depth circuits, Fourier transform, and learnability
• Parity, circuits, and the polynomial-time hierarchy
• Covering codes with improved density
• Variable Influences in Conjunctive Normal Forms
• The shortest disjunctive normal form of a random Boolean function
• On the Correlation of Parity and Small-Depth Circuits
• Approximation by DNF: Examples and Counterexamples
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating Boolean Functions with Depth-2 Circuits