THE BOOLEAN FUNCTION WIZARD 1.0
by Scott Aaronson
8/31/2000
INTRODUCTION
The Boolean Function Wizard (BFW) is a library to compute properties of Boolean functions. Most (though not all) of the properties are related to decision tree complexity. The original purpose of the BFW was to help investigate open questions in complexity theory, but the library can be used for other purposes as well.
INCLUDED FILES
WARNING -- The timer code is not ANSI C, so you may need to #undef TIMING (in props.h) to get the code to compile.
All .c and .h files are in the /src directory.
For the BFW:
basic.c Basic properties
comput.c Computational complexity properties
degree.c Degree properties
determin.c Deterministic query complexity properties
f.c Command-line interface
props.h Header file
quantum.c Quantum query complexity properties
random.c Randomized query complexity properties
sensitiv.c Sensitivity-related properties
util.c Utility functions
For the lp_solve library (the things you need to link with):
debug.c
hash.c
lpkit.c
lpkit.h
lptab.c
presolve.c
read.c
readmps.c
solve.c
Documentation:
readme.txt This file
Miscellaneous utilities:
allf.c Finds all Boolean functions of a given size up to
isomorphism
.bf files (in /bf directory):
xor2.bf 2-variable XOR
and2.bf 2-variable AND
rand1.bf to rand15.bf Random Boolean functions (uniform distribution)
3-1.bf to 3-10.bf All 3-variable functions up to isomorphism
4-1.bf to 4-208.bf All 4-variable functions up to isomorphism
.ini files (in /ini directory):
f.ini Default initialization file
Many others Can be used as needed (also it's extremely easy
to create your own)
STRUCTURE
The BFW comprises about 4,400 lines of C code (at last count). The core of the library is a struct called "function," which stores a Boolean function's truth table plus lots of auxiliary information about the function that is computed by various routines. To get an idea of the layout of "function," read the comments in props.h.
Each Boolean function property in the library has its own C function to compute it. The function takes a "function" struct as input, and returns the property value as output. The function also does some other things:
* It starts a timer, which is used to measure how long the algorithm takes.
* It sets the prev field of the "function" struct to a numeric code specific to the property. This notifies other routines which was the last property computed.
* If a flag is set, it checks to see whether an answer is already cached in the "function" struct, and if so returns that answer without recomputing it.
* If a flag is set, it caches its answer in the "function" struct.
* If a flag is set, it prints detailed data to the file x.dat, where x.bf is the input file. For example, x.dat contains an optimal decision tree itself, whereas the function's output is just the tree's height. But beware: if you're not familiar with the source code, x.dat will probably look like junk.
f.c contains a small command-line interface for the library. Alternatively, you can link to the library by linking with all object files except for f.obj, and by putting an #include "props.h" in your program.
Some other notes: the freeware linear programming solver lp_solve 2.3, available at ftp://ftp.es.ele.tue.nl/pub/lp_solve/, is an essential component. Source files for lp_solve are included with the distribution of the BFW.
The file util.c contains numerous utility functions (and more under construction), including the functions to create, copy, and destroy "function" structs, and the functions that handle input and output of "function" structs.
SUPPORTED PROPERTIES
For definitions of these properties and references to the literature, see the paper "Algorithms for Boolean Function Query Measures" by Scott Aaronson. For more detailed definitions (i.e. how non-total functions are handled), see the comments in the source code.
All average-case properties are with reference to the uniform distribution.
Check the source code to see which properties are currently implemented.
BASIC PROPERTIES
unate Unateness [isomorphism to a monotone function]
qsym Quasisymmetry [isomorphism to a symmetric function]
bal Whether f is balanced
vars Dependence
prime Primality
SENSITIVITY-RELATED PROPERTIES
s Sensitivity
su Sensitivity (average)
bs Block sensitivity
bsu Block sensitivity (average)
es Everywhere sensitivity
esu Everywhere sensitivity (average)
Amb Ambainis complexity [a lower bound for Q2(f)]
inf Maximum influence [of any variable of f]
DEGREE AS A POLYNOMIAL
deg Degree as a real polynomial (exact)
degZ2 Degree as a polynomial over Z[2]
deg2 Degree as a real polynomial (2-sided error)
ndeg Degree as a real polynomial (nondeterministic, 1-sided)
deg1 Degree as a real polynomial (1-sided-error)
degs Degree as a real polynomial (nondeterministic, strong)
degw Degree as a real polynomial (nondeterministic, weak)
DETERMINISTIC QUERY COMPLEXITY
D Deterministic query complexity (worst-case)
Du Deterministic query complexity (average-case)
C Certificate complexity
Cu Certificate complexity (average)
RANDOMIZED QUERY COMPLEXITY
R0 Randomized query complexity (0-error, worst-case)
R1 Randomized query complexity (1-sided-error, worst-case)
R1u Randomized query complexity (1-sided-error, average-case)
R2 Randomized query complexity (2-sided-error, worst-case)
R2u Randomized query complexity (2-sided-error, average-case)
NR Randomized query complexity (nondeterministic, 1-sided, worst-case)
NRu Randomized query complexity (nondet, 1-sided, average-case)
NRs Randomized query complexity (nondet, strong, worst-case)
NRsu Randomized query complexity (nondet, 1-sided, average-case)
NRw Randomized query complexity (nondet, weak, worst-case)
NRwu Randomized query complexity (nondet, 1-sided, average-case)
QUANTUM QUERY COMPLEXITY
QE Quantum query complexity (exact, worst-case)
QEu Quantum query complexity (exact, average-case)
Q0 Quantum query complexity (zero-error, worst-case)
Q0u Quantum query complexity (zero-error, average-case)
Q1 Quantum query complexity (1-sided-error, worst-case)
Q1u Quantum query complexity (1-sided-error, average-case)
Q2 Quantum query complexity (2-sided-error, worst-case)
Q2u Quantum query complexity (2-sided-error, average-case)
NQ Quantum query complexity (nondeterministic, 1-sided, worst-case)
NQu Quantum query complexity (nondet, 1-sided, average-case)
NQs Quantum query complexity (nondet, strong, worst-case)
NQsu Quantum query complexity (nondet, strong, average-case)
NQw Quantum query complexity (nondet, weak, worst-case)
NQwu Quantum query complexity (nondet, weak, average-case)
EXECUTION
f.exe is invoked on the command line with the syntax
f [ini_file]
is the name of a file containing a Boolean function's truth table. An extension of .bf is automatically appended to the file name. Here is an example of a .bf file, xor2.bf:
2
00 0
01 1
10 1
11 0
The number on top (which is mandatory) is the number of input variables. What follows is the truth table for a function (in this case the XOR function), with one entry per line. The input strings are optional; it would also work to write
2
0
1
1
0
If a Boolean function is partial, use -1 to specify that the function is undefined on a particular input. If a .bf file causes an error, the problem is probably that the file doesn't have Windows-style carriage returns.
[ini_file] is the name of an initialization file containing a list of properties to compute, one per line. An extension of .ini is automatically appended to the file name. If [ini_file] is left out, f.ini is used as a default. Here is f.ini:
unate
qsym
vars
D
C
bs
es
s
deg
degZ2
deg2
degs
ndeg
R0
R2
prime
Finally, here is an example run:
> f xor2
Boolean Function Wizard by Scott Aaronson
unate(f) 0 0.000 sec
qsym(f) 1 0.000 sec
Preprocessing 0.000 sec
vars(f) 2 0.000 sec
D(f) 2 0.000 sec
C(f) 2 0.000 sec
bs(f) 2 0.000 sec
es(f) 2 0.000 sec
s(f) 2 0.000 sec
deg(f) 2 0.000 sec
degZ2(f) 1 0.000 sec
deg2(f) 2 0.030 sec
degs(f) 2 0.020 sec
ndeg(f) 2 0.030 sec
R0(f) 2.000000 0.010 sec
3R2(f) 2.000000 0.000 sec
prime(f) 1 0.000 sec