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

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings
Pages204-215
Number of pages12
DOIs
StatePublished - 20 Jul 2010
Event5th International Computer Science Symposium in Russia, CSR 2010 - Kazan, Russian Federation
Duration: 16 Jun 201020 Jun 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6072 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Computer Science Symposium in Russia, CSR 2010
Country/TerritoryRussian Federation
CityKazan
Period16/06/1020/06/10

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 49786845