Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-028 | 2nd April 2009 00:00

A Candidate Counterexample to the Easy Cylinders Conjecture

RSS-Feed




TR09-028
Authors: Oded Goldreich
Publication: 2nd April 2009 23:25
Downloads: 2059
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint