One-way permutations, computational asymmetry and distortion

Details One-way permutations, computational asymmetry and distortion One-way permutations, computational asymmetry and distortion

2007-04-12

arxiv.org/abs/0704.1569v1

Mathematics

Group Theory

33 pages

Scientific paper

Computational asymmetry, i.e., the discrepancy between the complexity of transformations and the complexity of their inverses, is at the core of one-way transformations. We introduce a computational asymmetry function that measures the amount of one-wayness of permutations. We also introduce the word-length asymmetry function for groups, which is an algebraic analogue of computational asymmetry. We relate boolean circuits to words in a Thompson monoid, over a fixed generating set, in such a way that circuit size is equal to word-length. Moreover, boolean circuits have a representation in terms of elements of a Thompson group, in such a way that circuit size is polynomially equivalent to word-length. We show that circuits built with gates that are not constrained to have fixed-length inputs and outputs, are at most quadratically more compact than circuits built from traditional gates (with fixed-length inputs and outputs). Finally, we show that the computational asymmetry function is closely related to certain distortion functions: The computational asymmetry function is polynomially equivalent to the distortion of the path length in Schreier graphs of certain Thompson groups, compared to the path length in Cayley graphs of certain Thompson monoids. We also show that the results of Razborov and others on monotone circuit complexity lead to exponential lower bounds on certain distortions.

Affiliated with

Also associated with

No associations

Rating

One-way permutations, computational asymmetry and distortion does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with One-way permutations, computational asymmetry and distortion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and One-way permutations, computational asymmetry and distortion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-147924