Paper Info
Title
Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms
Abstract
We prove an exponential lower bound on the average time of inverting Goldreich's function by drunken backtracking algorithms; this resolves the open question stated in Cook et al. (Proceedings of TCC, pp. 521---538, 2009). The Goldreich's function has n binary inputs and n binary outputs. Every output depends on d inputs and is computed from them by the fixed predicate of arity d. Our Goldreich's function is based on an expander graph and on the nonlinear predicates that are linear in Ω(d) variables. Drunken algorithm is a backtracking algorithm that somehow chooses a variable for splitting and randomly chooses the value for the variable to be investigated at first.After the submission to the journal we found out that the same result was independently obtained by Rachel Miller.
Year
DOI
Venue
2014
10.1007/s00224-013-9514-8
Computer Science Symposium in Russia
Keywords
Field
DocType
backtracking algorithm,lower bound,drunken backtracking algorithms,expander graph,drunken backtracking algorithm,inverting goldreich,average-case complexity,average time,drunken algorithm,fixed predicate,n binary output,rachel miller,n binary input
Average-case complexity,Discrete mathematics,Combinatorics,Exponential function,Arity,Expander graph,Upper and lower bounds,Algorithm,DPLL algorithm,Backtracking,Mathematics,Binary number
Journal
Volume
Issue
ISSN
54
2
1432-4350
ISBN
Citations 
PageRank 
3-642-13181-6
8
0.58
References 
Authors
15
1
Name
Order
Citations
PageRank
Dmitry Itsykson13310.09