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

DOI10.1016/j.jcss.2019.04.004zbMath1423.68218MaRDI QIDQ2316930

Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama, Takayuki Sakai

Publication date: 7 August 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

symmetric function; restriction; circuit complexity; shrinkage; maximum satisfiability; linear threshold function; beating brute force

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)