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

DOI10.1016/j.jcss.2019.04.004zbMath1423.68218OpenAlexW2942099076WikidataQ127993794 ScholiaQ127993794MaRDI QIDQ2316930

Takayuki Sakai, Junichi Teruyama, Kazuhisa Seto, Suguru Tamaki

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 functionrestrictioncircuit complexityshrinkagemaximum satisfiabilitylinear threshold functionbeating brute force

Mathematics Subject Classification ID

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of a threshold gate at the top
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Exponential lower bound for bounded depth circuits with few threshold gates
• On the power of small-depth threshold circuits
• A moderately exponential time algorithm for \(k\)-IBDD satisfiability
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Majority gates vs. general weighted threshold gates
• Approximation algorithms for combinatorial problems
• The expressive power of voting polynomials
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• Complex polynomials and circuit lower bounds for modular counting
• Which problems have strongly exponential complexity?
• Local reduction
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• PP is closed under intersection
• Mining circuit lower bound proofs for meta-algorithms
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
• Threshold circuits of bounded depth
• Theory of majority decision elements
• A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP
• Natural Proofs versus Derandomization
• Improving Exhaustive Search Implies Superpolynomial Lower Bounds
• Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases
• Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
• NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth
• Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
• Nonuniform ACC Circuit Lower Bounds
• Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
• Learning and Lower Bounds for AC 0 with Threshold Gates
• The Complexity of Satisfiability of Small Depth Circuits
• Simulating Threshold Circuits by Majority Circuits
• Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
• Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression
• New algorithms and lower bounds for circuits with linear threshold gates
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• On Problems as Hard as CNF-SAT
• Short PCPs with Projection Queries
• Mathematical Foundations of Computer Science 2004
• More Applications of the Polynomial Method to Algorithm Design
• Learning algorithms from natural proofs
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Automata, Languages and Programming
• Natural proofs
• On the complexity of \(k\)-SAT

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