Name
Abstract | ||
|---|---|---|
Say that an algorithm solving a Boolean satisfiability problem x on n variables is improved if it takes time poly(|x|)2 cn for some constant c i.e., if it is exponentially better than a brute force search. We show an improved randomized algorithm for the satisfiability problem for circuits of constant depth d and a linear number of gates cn: for each d and c, the running time is 2(1 驴 驴)n where the improvement $\delta\geq 1/O(c^{2^{d-2}-1}\lg^{3\cdot 2^{d-2}-2}c)$, and the constant in the big-Oh depends only on d. The algorithm can be adjusted for use with Grover's algorithm to achieve a run time of $2^{\frac{1-\delta}{2}n}$ on a quantum computer. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-11269-0_6 | IWPEC |
Keywords | Field | DocType |
satisfiability problem,gates cn,time poly,n variable,small depth circuits,improved randomized algorithm,brute force search,boolean satisfiability problem,constant depth,run time,linear number,randomized algorithm,satisfiability,upper bound,grover s algorithm,quantum computer | Discrete mathematics,Randomized algorithm,Combinatorics,Block cipher,Brute-force search,Boolean satisfiability problem,Satisfiability,Quantum computer,Electronic circuit,Mathematics | Conference |
Volume | ISSN | Citations |
5917 | 0302-9743 | 48 |
PageRank | References | Authors |
1.54 | 17 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chris Calabro | 1 | 140 | 6.13 |
| Russell Impagliazzo | 2 | 5444 | 482.13 |
| Ramamohan Paturi | 3 | 1260 | 92.20 |