Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms

Standard

Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms. / Itsykson, Dmitry.

In: Theory of Computing Systems, Vol. 54, No. 2, 01.02.2014, p. 261-276.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{3a7b4a5d87434bf197c1d33e4bdcf803,

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.",

keywords = "DPLL, Expander, Goldreich's function, Lower bound",

author = "Dmitry Itsykson",

year = "2014",

month = feb,

day = "1",

doi = "10.1007/s00224-013-9514-8",

language = "English",

volume = "54",

pages = "261--276",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer Nature",

number = "2",

}

RIS

TY - JOUR

T1 - Lower Bound on Average-Case Complexity of Inversion of Goldreich's Function by Drunken Backtracking Algorithms

AU - Itsykson, Dmitry

PY - 2014/2/1

Y1 - 2014/2/1

N2 - 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.

AB - 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.

KW - DPLL

KW - Expander

KW - Goldreich's function

KW - Lower bound

UR - http://www.scopus.com/inward/record.url?scp=84895065360&partnerID=8YFLogxK

U2 - 10.1007/s00224-013-9514-8

DO - 10.1007/s00224-013-9514-8

M3 - Article

AN - SCOPUS:84895065360

VL - 54

SP - 261

EP - 276

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 2

ER -

ID: 49785972