Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
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 июн 2010 → 20 июн 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/10 → 20/06/10 |
ID: 49786845