A Candidate Counterexample to the Easy Cylinders Conjecture
Webpage for a paper by Oded Goldreich
We present a candidate counterexample to the easy cylinders
conjecture, which was recently suggested by
Manindra Agrawal and Osamu Watanabe (see ECCC, TR09-019).
Loosely speaking, the conjecture asserts that any 1-1 function
in $P/poly$ can be decomposed into ``cylinders'' of sub-exponential
size that can each be inverted by some polynomial-size circuit.
Although all popular one-way functions have such easy (to invert) cylinders,
we suggest a possible counterexample. Our suggestion builds on
the candidate one-way function based on expander graphs
(see ECCC, TR00-090), and essentially consists of iterating
this function polynomially many times.
Material available on-line
- First version posted:
- Revisions: none yet.
either Oded Goldreich's homepage.
or general list of papers.