Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
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 language | English |
---|---|
Title of host publication | Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings |
Pages | 204-215 |
Number of pages | 12 |
DOIs | |
State | Published - 20 Jul 2010 |
Event | 5th International Computer Science Symposium in Russia, CSR 2010 - Kazan, Russian Federation Duration: 16 Jun 2010 → 20 Jun 2010 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 6072 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 5th International Computer Science Symposium in Russia, CSR 2010 |
---|---|
Country/Territory | Russian Federation |
City | Kazan |
Period | 16/06/10 → 20/06/10 |
ID: 49786845