Most general order-preserving function

[Dragonfall]

Is there an easy description for all the real to real functions that are order-preserving? I can only think of linear functions

 

[Mark44]

Is there an easy description for all the real to real functions that are order-preserving? I can only think of linear functions

What do you mean by "order-preserving?" Is it the idea that if a < b, then f(a) < f(b)? If so any function that is strictly increasing satisfies the latter inequality. If you mean something different, you need to clarify your question.

 

[Dragonfall]

What I need is a class of functions that is strictly increasing, very efficient to compute, and when one is selected uniformly and applied to x < y, the pair (f(x), f(y)) is uniformly distributed.

 

[mfb]

For every x,y? Then your class of functions has to be uncountable. What do you mean with "selected uniformly"? There is no clear definition of this on an arbitrary uncountable set.
Also, uniform distributions over the full real line do not exist.

f(x)=mx+c with suitable distributions of m and c can give a uniform distribution of (f(x),f(y)) in some finite range, or give nice non-uniform distributions as well.

 

[Dragonfall]

OK the domain is integers [1, ..., n], forget about what the range is for now, we can decide that after. I have a pair of numbers (a, b). I want to apply a function at random from this class so that (f(a), f(b)) is uniformly random and f(a) < f(b).

f has to be efficiently computable. It also has to be "decomposable" into two parts f_1, f_2 such that f(x) = f_2 ( f_1 (x) ). Knowing ONLY ONE of f_1 or f_2, and given f(x), it should be infeasible to compute x.

I'm thinking Ax + B for A > 0 and random B. Knowing Ax+B, and only one of A or B doesn't tell you anything about x.

 

[mfb]

Uniformly random where?

Every f is "decomposable" that way, simply set f_1(x)=f(x), f_2(x)=x (or vice versa).
Knowing only one of an arbitrary and unknown "decomposition" makes the task impossible - see my example, one of the functions could be just the identify function.

I think it would really help if you give more context. What do you actually want to do?

 

[Dragonfall]

Uniformly random where?

Every f is "decomposable" that way, simply set f_1(x)=f(x), f_2(x)=x (or vice versa).
Knowing only one of an arbitrary and unknown "decomposition" makes the task impossible - see my example, one of the functions could be just the identify function.

I think it would really help if you give more context. What do you actually want to do?

No. If f_1 = f then knowing f_1 and knowing f(x) gives you x, assuming it's not one-way and is one to one.

You know that zero-knowledge proof of graph isomorphism? You have two permutations. Composition gives you the permutation. Knowing just one gives you nothing. I'm trying to come up with something similar for two ordered committed numbers.

 

[mfb]

I'm trying to come up with something similar for two ordered committed numbers.

So who is supposed to know what? What is the protocol you want to use, and what is the result?

 

[Dragonfall]

You're not supposed to know that. I'm supposed to come up with it. And I have! Thanks for the inputs.

 

[mfb]

A new protocol for Yao's Millionaires' Problem?