A Candidate Counterexample to the Easy Cylinders Conjecture

Webpage for a paper by Oded Goldreich

Abstract

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

Back to either Oded Goldreich's homepage. or general list of papers.