Standard

The complexity of inverting explicit Goldreich's function by DPLL algorithms. / Itsykson, D. M.; Sokolov, D. O.

In: Journal of Mathematical Sciences (United States), Vol. 188, No. 1, 01.01.2013, p. 47-58.

Research output: Contribution to journalArticlepeer-review

Harvard

Itsykson, DM & Sokolov, DO 2013, 'The complexity of inverting explicit Goldreich's function by DPLL algorithms', Journal of Mathematical Sciences (United States), vol. 188, no. 1, pp. 47-58. https://doi.org/10.1007/s10958-012-1105-8

APA

Itsykson, D. M., & Sokolov, D. O. (2013). The complexity of inverting explicit Goldreich's function by DPLL algorithms. Journal of Mathematical Sciences (United States), 188(1), 47-58. https://doi.org/10.1007/s10958-012-1105-8

Vancouver

Itsykson DM, Sokolov DO. The complexity of inverting explicit Goldreich's function by DPLL algorithms. Journal of Mathematical Sciences (United States). 2013 Jan 1;188(1):47-58. https://doi.org/10.1007/s10958-012-1105-8

Author

Itsykson, D. M. ; Sokolov, D. O. / The complexity of inverting explicit Goldreich's function by DPLL algorithms. In: Journal of Mathematical Sciences (United States). 2013 ; Vol. 188, No. 1. pp. 47-58.

BibTeX

@article{4ee26e63d5a24867b1e038fb5c50f2df,
title = "The complexity of inverting explicit Goldreich's function by DPLL algorithms",
abstract = "Goldreich's function has n binary inputs and n binary outputs. Every output depends on d inputs and is computed from them by a fixed predicate of arity d. Every Goldreich's function is determined by its dependency graph G and a predicate P. In 2000, O. Goldreich formulated the conjecture that if G is an expander and P is a random predicate of arity d, then the corresponding function is one-way. In this paper, we give a simple proof of an exponential lower bound on the inversion of Goldreich's function by myopix DPLL algorithms. The dependency graph G in our construction may be based on an arbitrary expander; in particular, one can use an explicit expander; while all previously known results are based on random dependency graphs. The predicate P can be linear or slightly nonlinear. Our construction can be used in the proof of lower bounds for drunken DPLL algorithms as well. Bibliography: 18 titles.",
author = "Itsykson, {D. M.} and Sokolov, {D. O.}",
year = "2013",
month = jan,
day = "1",
doi = "10.1007/s10958-012-1105-8",
language = "English",
volume = "188",
pages = "47--58",
journal = "Journal of Mathematical Sciences",
issn = "1072-3374",
publisher = "Springer Nature",
number = "1",

}

RIS

TY - JOUR

T1 - The complexity of inverting explicit Goldreich's function by DPLL algorithms

AU - Itsykson, D. M.

AU - Sokolov, D. O.

PY - 2013/1/1

Y1 - 2013/1/1

N2 - Goldreich's function has n binary inputs and n binary outputs. Every output depends on d inputs and is computed from them by a fixed predicate of arity d. Every Goldreich's function is determined by its dependency graph G and a predicate P. In 2000, O. Goldreich formulated the conjecture that if G is an expander and P is a random predicate of arity d, then the corresponding function is one-way. In this paper, we give a simple proof of an exponential lower bound on the inversion of Goldreich's function by myopix DPLL algorithms. The dependency graph G in our construction may be based on an arbitrary expander; in particular, one can use an explicit expander; while all previously known results are based on random dependency graphs. The predicate P can be linear or slightly nonlinear. Our construction can be used in the proof of lower bounds for drunken DPLL algorithms as well. Bibliography: 18 titles.

AB - Goldreich's function has n binary inputs and n binary outputs. Every output depends on d inputs and is computed from them by a fixed predicate of arity d. Every Goldreich's function is determined by its dependency graph G and a predicate P. In 2000, O. Goldreich formulated the conjecture that if G is an expander and P is a random predicate of arity d, then the corresponding function is one-way. In this paper, we give a simple proof of an exponential lower bound on the inversion of Goldreich's function by myopix DPLL algorithms. The dependency graph G in our construction may be based on an arbitrary expander; in particular, one can use an explicit expander; while all previously known results are based on random dependency graphs. The predicate P can be linear or slightly nonlinear. Our construction can be used in the proof of lower bounds for drunken DPLL algorithms as well. Bibliography: 18 titles.

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

U2 - 10.1007/s10958-012-1105-8

DO - 10.1007/s10958-012-1105-8

M3 - Article

AN - SCOPUS:84871933216

VL - 188

SP - 47

EP - 58

JO - Journal of Mathematical Sciences

JF - Journal of Mathematical Sciences

SN - 1072-3374

IS - 1

ER -

ID: 49786184