Computing Boolean functions by polynomials and threshold circuits

DOI10.1007/S000370050015zbMATH Open0936.94022OpenAlexW2091623775MaRDI QIDQ1293360FDOQ1293360

Authors: Matthias Krause, Pavel Pudlák 

Publication date: 17 April 2000

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

Full work available at URL: https://doi.org/10.1007/s000370050015

Recommendations

• On the power of small-depth threshold circuits
• scientific article; zbMATH DE number 1256716
• The complexity of computing symmetric functions using threshold circuits

zbMATH Keywords

computational complexityBoolean functionspolynomial representationthreshold circuits

Mathematics Subject Classification ID

Probability distributions: general theory (60E05) Boolean functions (06E30)

Cited In (23)

• The hardest halfspace
• Algorithmic Polynomials
• Approximate degree and the complexity of depth three circuits
• A characterization of 2-threshold functions via pairs of prime segments
• The power of asymmetry in constant-depth circuits
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
• Threshold circuits detecting global patterns in two-dimensional maps
• A short list of equalities induces large sign-rank
• Algorithms for synthesis of polynomials implementing weakly specified Boolean functions and systems
• New degree bounds for polynomial threshold functions
• Asymptotics of the number of 2-threshold functions
• On PAC learning algorithms for rich Boolean function classes
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Degree-uniform lower bound on the weights of polynomials with given sign function
• Polynomial threshold functions and Boolean threshold circuits
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Polynomial threshold functions and Boolean threshold circuits
• Title not available (Why is that?)
• A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
• Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
• Polynomial threshold functions, hyperplane arrangements, and random tensors
• Learning unions of \(\omega(1)\)-dimensional rectangles
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits

This page was built for publication: Computing Boolean functions by polynomials and threshold circuits

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