Paper Info
Title
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits
Abstract
We give a nontrivial algorithm for the satisfiability problem for threshold circuits of depth two with a linear number of wires which improves over exhaustive search by an exponential factor. The independently interesting problem of the feasibility of sparse 0-1 integer linear programs is a special case. To our knowledge, our algorithm is the first to achieve constant savings even for the special case of Integer Linear Programming. The key idea is to reduce the satisfiability problem to the Vector Domination problem, the problem of checking whether there are two vectors in a given collection of vectors such that one dominates the other component-wise. Our result generalizes to formulas of arbitrary constant depth. We also provide a satisfiability algorithm with constant savings for depth two circuits with symmetric gates where the total weighted fan-in is at most linear in the number of variables. One of our motivations is proving strong lower bounds for TC0 circuits, exploiting the connection (established by Williams) between satisfiability algorithms and lower bounds. Our second motivation is to explore the connection between the expressive power of the circuits and the complexity of the corresponding circuit satisfiability problem.
Year
DOI
Venue
2013
10.1109/FOCS.2013.58
Foundations of Computer Science
Keywords
Field
DocType
satisfiability problem,interesting problem,special case,threshold circuits,constant saving,sparse depth,vector domination problem,integer linear program,corresponding circuit satisfiability problem,arbitrary constant depth,satisfiability algorithm,linear number,computability,circuit complexity,integer programming,logic gates,linear programming
Maximum satisfiability problem,Discrete mathematics,Combinatorics,Circuit complexity,Computer science,Boolean satisfiability problem,Circuit satisfiability problem,Satisfiability,Algorithm,Computability,Integer programming,Linear programming
Conference
Volume
ISSN
Citations 
abs/1212.4548
0272-5428
18
PageRank 
References 
Authors
0.84
8
3
Name
Order
Citations
PageRank
Russell Impagliazzo15444482.13
Ramamohan Paturi2126092.20
Stefan Schneider3563.07