DOI

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

Язык оригиналаанглийский
Название основной публикацииComputer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings
Страницы204-215
Число страниц12
DOI
СостояниеОпубликовано - 20 июл 2010
Событие5th International Computer Science Symposium in Russia, CSR 2010 - Kazan, Российская Федерация
Продолжительность: 16 июн 201020 июн 2010

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том6072 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция5th International Computer Science Symposium in Russia, CSR 2010
Страна/TерриторияРоссийская Федерация
ГородKazan
Период16/06/1020/06/10

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 49786845