Cuckoo Cycle verification checks that k nonces form a cycle on k hash values;
I'd say that's comparably simple (with no need for modular arithmetic).

Interesting idea...

But your analysis seems wrong.

With O(sqrt(d)) hashes you can form O(d) different 2-SUMs, and expect a solution,
just like with the birthday paradox.

For 3-SUM, O(d^{1/3}) hashes using O(d^{2/3}) memory should suffice.

Dont you think it will be better distributed if its done simething similar to POW. It might cost everyone a little bit of mining but it wont be like people with huge money can hoard all the coins.

You mean the potential for underground websites like stakesignfavors.com popping up,
where signers can try to make a little extra money on the side?

No, ASICs have nothing to do with botnet formation.

However, botnets are less likely to target a coin whose PoW has ASICs since
ASICs will only be developed when they significantly outperform CPUs&GPUs,
which limits profitability compared to ASIC-less PoWs/coins.

But as we saw recently (http://www.zdnet.com/nas-device-botnet-mined-600000-in-dogecoin-over-two-months-7000030662/), botnet operators can be either dumb or lazy
and still go after BTC/LTC/DOGE.

slowly rising reward, taking a few months to peak, preventing instamine

then slowly decaying, but to some constant greater than zero (i.e. no hardcap)
no need to rely on fees
will still have a soft-cap due to some percentage of coins inevitably getting lost every year.

airdrop a fraction of that soft-cap to bitcoin owners, according to a snapshot of the bitcoin blockchain at some fixed date (see https://bitcointalk.org/index.php?topic=563925.0)
  expands user base
  preserves some of the digital scarcity

use a PoW that's memory-bound rather than compute-bound
  computation being dominated by random access to global memory makes it low-power
  require hundreds a MB to find proof (either on CPU or GPU)
  require no memory and negligable time to verify (same as bitcoin)

transactions require smaller sized PoW (e.g. provable in 10s)
   to prioritize inclusion (in absence of fees)
   avoid tx DOS attack

rely on high memory usage and low (initial) reward to make it unattractive for botnets

In fact the memory requirements should exceed what you can cost-effectively
put on an ASIC. Then whatever ASIC is made for the PoW won't be self-contained
but reliant on additional, and much more expensive, memory modules, limiting
its speed&cost advantage over all-commodity solutions.

A coin with high memory requirements and low initial rewards
(ideally, max reward should not appear until several weeks or even months of mining)
makes for an unattractive botnet-target.

Botnet owners don't mind slowing computers down somewhat (people are used to that),
but the last thing they want to do is force people to take action once their computer
starts swapping excessively and becomes totally unusable.

Both Monero and Vertcoin are short-term solutions that do no scale since they are symmetric:
verifying a proof is as slow as looking for one.

The PoW I have in mind is not only memory bound but aims at vastly higher
memory requirements while remaining instantly verifiable.

Only if a handful or fewer super computers dominate everyone else and their owners
are susceptible to collusion.

Otherwise, they're part of the solution.

Focussing on power consumption suggests that you are focussing on compute-bound PoWs.
However, some memory-bound PoWs spend only 1/3 of time doing computations, and
2/3 waiting on random-access memory-latency, which makes power-consumption less of an issue.

That so reminds me of a Seinfeld episode...

https://www.youtube.com/watch?v=iq8gfaFqFpI

Compute-bound PoWs are ASIC-friendly by nature.

Memory-bound PoWs that need more memory than fits on a single chip
would lead to ASICs that need to connect to memory modules;
whose throughput is limited by the memory interface and latency.
Such a setup would have limited performance & power advantage over
commodity hardware.

You could use this prime-sieve program as a logo:

Not to be confused with batcoin, badcoin, and bedcoin...

That may be true for compute-bound PoWs but not for memory-bound PoWs
that need random access to more memory than can be fit on an ASIC.

Thus an ASIC for such a PoW needs to be equipped with (more expensive) memory modules,
and only needs to be optimized to saturate the memory latency, which also limits power-use.

Such an ASIC would also not have much of a performance advantage over a multi-core cpu
running the PoW, since both are limited by memory latency.

A compute bound PoW (or one using limited memory like scrypt) results in
a self-contained ASIC allowing for many generations of improvements and refinements.

With a memory-latency bound PoW requiring the use of separate DRAM memory modules,
an ASIC only needs to be able to saturate memory bandwidth, meaning fewer generations and less obsolescence.

At a given level of investment, this will also make mining much less power-hungry,
with costs shifting from power/cooling costs to investment in DRAM, which is even
more general-purpose and obsolescence proof than GPUs.

Because of (random access) memory latency.
See http://en.wikipedia.org/wiki/Random-access_memory#Memory_wall

Requiring lots of memory is good for CPU friendliness and ASIC resistance.
But using lots of memory takes lots of time, and you want PoW verification to be super fast.

So scrypt is a bad idea.

You want an assymetric PoW where only finding the proof requires a lot of memory,
while verification takes none.

Gigabytes of memory cannot (yet) be put on a self-contained ASIC. At best it will lead to an ASIC that you have to connect to much more expensive memory modules.
Then the already heavily commoditized DRAM market dictates mining costs, preventing centralization
based on access to fabrication technology and cheap power...

Can you download the source code from https://github.com/tromp/cuckoo and measure the power-usage while running e.g.
?