Under the auspices of the Computational Complexity Foundation (CCF)
We present a candidate counterexample to the
easy cylinders conjecture, which was recently suggested
by Manindra Agrawal and Osamu Watanabe (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.