Abstract | ||
---|---|---|
In this paper we report preliminary results of experiments with finding efficient circuits (over binary bases) using SAT-solvers. We present upper bounds for functions with constant number of inputs as well as general upper bounds that were found automatically. We focus mainly on MOD-functions. Besides theoretical interest, these functions are also interesting from a practical point of view as they are the core of the residue number system. In particular, we present a circuit of size 3n + c over the full binary basis computing ${\rm MOD}_3^n$. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/978-3-642-02777-2_5 | SAT |
Keywords | Field | DocType |
efficient circuit,finding efficient,full binary basis computing,binary base,rm mod,general upper bound,constant number,preliminary result,practical point,residue number system,upper bound,sat solver | Boolean function,Discrete mathematics,Mod,Combinatorics,Circuit complexity,Computer science,Truth table,Residue number system,Electronic circuit,Binary number | Conference |
Volume | ISSN | Citations |
5584 | 0302-9743 | 12 |
PageRank | References | Authors |
0.84 | 12 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Arist Kojevnikov | 1 | 102 | 7.43 |
Alexander S. Kulikov | 2 | 280 | 25.63 |
Grigory Yaroslavtsev | 3 | 209 | 17.36 |