Standard

Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms. / Itsykson, Dmitry.

Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings. 2010. p. 204-215 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6072 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Itsykson, D 2010, Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms. in Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6072 LNCS, pp. 204-215, 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russian Federation, 16/06/10. https://doi.org/10.1007/978-3-642-13182-0_19

APA

Itsykson, D. (2010). Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms. In Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings (pp. 204-215). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6072 LNCS). https://doi.org/10.1007/978-3-642-13182-0_19

Vancouver

Itsykson D. Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms. In Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings. 2010. p. 204-215. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-13182-0_19

Author

Itsykson, Dmitry. / Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms. Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings. 2010. pp. 204-215 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{d47b64f6322d448d8ffe353b09ba45f0,
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 [AHI05] backtracking algorithms; therefore we resolve the open question stated in [CEMT09]. The Goldreich's function [Gol00] 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 nonliniar predicates of a special type. 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. Our proof technique significantly simplifies the one used in [AHI05] and in [CEMT09].",
author = "Dmitry Itsykson",
year = "2010",
month = jul,
day = "20",
doi = "10.1007/978-3-642-13182-0_19",
language = "English",
isbn = "3642131816",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "204--215",
booktitle = "Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings",
note = "5th International Computer Science Symposium in Russia, CSR 2010 ; Conference date: 16-06-2010 Through 20-06-2010",

}

RIS

TY - GEN

T1 - Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms

AU - Itsykson, Dmitry

PY - 2010/7/20

Y1 - 2010/7/20

N2 - We prove an exponential lower bound on the average time of inverting Goldreich's function by drunken [AHI05] backtracking algorithms; therefore we resolve the open question stated in [CEMT09]. The Goldreich's function [Gol00] 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 nonliniar predicates of a special type. 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. Our proof technique significantly simplifies the one used in [AHI05] and in [CEMT09].

AB - We prove an exponential lower bound on the average time of inverting Goldreich's function by drunken [AHI05] backtracking algorithms; therefore we resolve the open question stated in [CEMT09]. The Goldreich's function [Gol00] 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 nonliniar predicates of a special type. 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. Our proof technique significantly simplifies the one used in [AHI05] and in [CEMT09].

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

U2 - 10.1007/978-3-642-13182-0_19

DO - 10.1007/978-3-642-13182-0_19

M3 - Conference contribution

AN - SCOPUS:77954606694

SN - 3642131816

SN - 9783642131813

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 204

EP - 215

BT - Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings

T2 - 5th International Computer Science Symposium in Russia, CSR 2010

Y2 - 16 June 2010 through 20 June 2010

ER -

ID: 49786845