Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › 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