Hacker News Reader

napping_penguinon The Mathematics of Speed Dating

A friend recently went to a speed dating event. The organizers seated ten people at each table: five men and five women. Everyone gave a one-minute introduction; then the men moved as a group clockwise to the next table.

With this design, there were too many repeat introductions, particularly, people who moved together. It turns out there is better way to conduct this. Here's a short writeup of it.

napping_penguinon Prompt Privacy from LLMs

I recently came across a really interesting piece of privacy technology. Suppose you have a model M and a prompt P. The technique allows you to create an obfuscated prompt Q such that:

- M(Q) is nearly the same as M(P)

- P is hard to reverse engineer from Q

As a applied crypto researcher, this feels like an "ML-based homomorphic encryption". Works with any model (that supports prompt_embeds) without changing anything on the model side. Very cool indeed.

Credit note: This method was invented by Protopia Labs and I don't have any affiliation there.

napping_penguinon Can LLMs identify 16 cards in 45 bit-queries?

Ah, sloppy language on my part. It should be 5 of fewer questions. I'll fix it, thank you!

napping_penguinon Can LLMs identify 16 cards in 45 bit-queries?

You are right, your argument establishes the lower bound: D(4) >= 5 (you will need at least 5 questions in the worst case).

The interesting bit is to come up with a strategy to make 5 adaptive queries that will guarantee you know all the 4 cards no matter what the response you got to the queries.

As a simple example: Suppose I do the following (static) set of 5 questions:

- Is the first card Red?

- Is the first card King?

- Is the second card Red?

- Is the second card King?

- Is the third card Red?

You can see that there might be a situation where these 5 questions are not enough to uniquely determine the arrangement (for instance, in case you got answers Yes, Yes, Yes, No, No respectively).

More succinctly, 5 is the information theoretic lower bound but that does not mean it is achievable and that is precisely what the post is about. Is the information theoretic lower bound achievable?

napping_penguinon Can LLMs identify 16 cards in 45 bit-queries?

Thank you for the feedback, I will address this in the post.

napping_penguinon Can LLMs identify 16 cards in 45 bit-queries?

Good catch but it's intentional. The engine behind the first simulator for 4-cards is adversarial and hence appears a bit deterministic.

- Adversarial engine: Will always respond with an answer to your query such that it maximizes the number of remaining permutations (used in the first simulator)

- Honest engine: This one will actually have one random hidden permutation that will be uncovered by your queries (this is used in the second simulator)

The reason why the adversarial engine is used up there is because if the user does not play optimally, they will be forced into 6 queries or more (and hence will appreciate the difficulty of the problem better). If you do self-play on the lower simulator (which has the 4,8,16 card variants) you will have the experience you expect.