Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression

DOI10.4230/LIPICS.MFCS.2016.82MaRDI QIDQ4608645zbMATH OpenOpenAlexFDO

Authors Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

Publication date 21 March 2018

Full work available at URL http://drops.dagstuhl.de/opus/volltexte/2016/6490/

zbMATH Keywords

circuit complexitycircuit minimizationexponential time algorithmmaximum satisfiability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
• New upper bounds on the Boolean circuit complexity of symmetric functions

Cited in

(6)

• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Satisfiability and derandomization for small polynomial threshold circuits
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
• A \#SAT algorithm for small constant-depth circuits with PTF gates

This page was built for publication: Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression

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