A function f mapping n-bit strings to m-bit strings can be constructed from a bipartite graph with n vertices on the left and m vertices on the right having right-degree d together with a predicate P:01d01 . The vertices on the left correspond to the bits of the input to the function and the vertices on the right correspond to the bits of the output. The value of each output bit is computed by evaluating the predicate over the input bits corresponding to its neighbors. Goldreich (ECCC 2000) conjectured that this function f is one-way for m=n and d=(1) or d=(logn), when the vertices on the right ``expand'' and the predicate P is a random non-linear predicate.

Inverting f as a one-way function by definition means finding an element in the preimage f−1(f(x)) of the image of a random input x under the function f. We bound the expected size of this preimage when the bipartite graph is a random bipartite graph with right-degree d. Our result is for when the predicate P is a typical random predicate or P(x1xd)=x1xd−hQ(xd−h+1xd) where Q is an arbitrary predicate having at most d−(d) variables.

Inverting the function can be seen as a constraint satisfaction problem with a ``planted solution''. One can use backtracking algorithms to find this solution. Using the bound on the size of the preimage, we prove those backtracking algorithms that are ``myopic'' and those backtracking algorithms that are ``drunk'' cannot invert the function in better than exponential time on average.

Myopic backtracking algorithms are ones in which during the first levels of the backtracking tree, the algorithm has a limited view of the image f(x) for which the algorithm wants to find an element in the preimage f−1(f(x)). Our proof for myopic backtracking algorithms builds upon the work of Alekhnovich, Hirsch, and Itsykson (2005) where they instead consider solving a system of linear equations each with three variables, that is, when P=x1x2x3.

Drunk backtracking algorithms for a constraint satisfaction problem are ones in which at each point in the backtracking tree, even though the algorithm can choose any variable to fix next, the bit that is first tried for that variable has to be random.Our proof for drunk backtracking algorithms is similar to those of Itsykson (CSR 2010) and Miller (thesis 2009).

We show that these lower bounds also hold when the backtracking algorithm is allowed to eliminate ``pure literals" and ``unit clauses" as in DPLL algorithms.

Since both being myopic and being drunk are merely theoretical restrictions that allowed us to prove lower bounds, we also performed an experimental analysis by running one of the best available SAT solvers on the SAT instance equivalent to the constraint satisfaction problem corresponding to inverting the function. The solver seemed to take exponential running time