Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Circuit Satisfiability:
TR14-024 | 19th February 2014
Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

0-1 Integer Linear Programming with a Linear Number of Constraints

We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time $2^{(1-\text{poly}(1/c))n}$ where $n$ is the
number of variables and $cn$ is the number of constraints. The key ... more >>>

TR15-136 | 28th July 2015
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom

In this paper, we present a moderately exponential time algorithm for the circuit satisfiability problem of
depth-2 unbounded-fan-in circuits with an arbitrary symmetric gate at the top and AND gates at the bottom.
As a special case, we obtain an algorithm for the maximum satisfiability problem that runs in ... more >>>

TR17-109 | 22nd June 2017
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

Does Looking Inside a Circuit Help?

The Black-Box Hypothesis, introduced by Barak et al. (JACM, 2012), states that any property of boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an ... more >>>

TR18-162 | 16th September 2018
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit $C$ made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to $C$ in significantly better than ... more >>>

ISSN 1433-8092 | Imprint