07:50 UTC

< October 2017 > Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

- Console
- #amber
- #apicula
- #arm-graphics
- #arm-netbook
- #bitcoin-wizards
- #buildbot
- #bundler
- #cinch
- #coiniumserv
- #coiniumserv-dev
- #crystal-lang
- #cubieboard
- #datamapper
- #discferret
- #elliottcable
- #forth
- #glasgow
- #gridcoin
- #gridcoin-dev
- #homecmos
- #huawei-g300
- #imx6-dev
- #imx6-dongle
- #ipfs
- #jruby
- #libreelec
- #libreoffice-ru
- #lima
- #linux-amlogic
- #linux-exynos
- #linux-rockchip
- #linux-sunxi
- #lisp
- #litex
- #logarion
- #lowempire
- #maemo-leste
- #maglev-ruby
- #microrb
- #milkymist
- #mirage
- ##moved_to_libera
- #mutant
- #nanoc
- #neo900
- #nextbsd
- #nmigen
- #ocaml
- #opal
- ##openfpga
- #openwrt-devel
- #panfrost
- ##panfrost-offtopic
- #Paws
- #Paws.Nucleus
- #picolisp
- #ponylang
- #prjmistral
- #pypy
- #qaul.net
- #qi-hardware
- #racket
- #radxa
- #reasonml
- #river
- #rom-rb
- #rubinius
- #ruby
- #ruby-core
- #rubygems
- #rubygems-aws
- #rubygems-trust
- #ruby-lang
- #ruby-rdf
- #sandstorm
- #scopehal
- #skywater-pdk
- #slime
- #soletta
- #stellar
- #stellar-dev
- ##stm32-rs
- #symbiflow
- #systemtap
- #teamhacksung
- #teamhacksung-support
- #tinyqma
- #videocore
- #wallaroo
- #xiki
- #xtompp
- ##yamahasynths
- #yosys
- #zig

sipa changed the topic of #bitcoin-wizards to: This channel is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja

<maaku>
I have a CS theory question for this group. A Huffman code is optimal if the probabilities are known and fixed. However is there a method for constructing trees that try to minimize the path for accessing multiple elements?

<maaku>
Obviously the frequency of each A,B pairing (for accessing 2 items) or A,B,C (3, etc.) would be given.

<kanzure>
if you allow for stepwise increase in path length cost, your method could be just put the frequently-accessed stuff at the top of the tree, then for double cost the less popular stuff at the next level, and so on.

<kanzure>
H(root) -> (H(tree(H(tree(...)), H(C)), H(B)), H(A)) so H(A) is cheapest to lookup, B is more expensive, C is even more expensive.

<gmaxwell>
maaku: huffman tress also require that the probablities are all 1/2^n for optimality. (though not your question) ... I know how to construct ones that have a depth limit, which seems relevant to your interests.

<gmaxwell>
I think this shared prefix property might also just be obeyed by huffman codes, if you assume that the probablities are independant.

<gmaxwell>
absolutely, but nothing that maps into a binary decision tree, which is what I assume you want. (because I assume you're using this for hashtree layouts)

<maaku>
gmaxwell: yes, and yes. with those restrictions I think Huffman is optimal, but would like to be corrected if wrong

<maaku>
kanzure: that's what I'm trying to do. my question is more, "for given probability distributions, what's the optimal tree shape?"

<maaku>
gmaxwell: constructing with a depth limit would be interesting. not what I'm working on right now, but I'd be good to know how to do that

<kanzure>
uhrm for the tree sizes you are considering, is it practical to just run some quick iterative emperical method to figure that out? and then you cna look at the results to answer your question (or if it's fast enough, just include that in your implementation anyway).

<maaku>
Specifically I'm trying to find tree shapes that I should be benchmarking serialization choices against. "Maximally-unbalanced (a list) at the top, then a fully-balanced tree at the bottom" is a good intuition for what this ***should*** look like, based on real world use cases

<maaku>
But I'm looking for a theoretical justification for that -- constructing a justifiable probability model, then making an optimal tree.

<gmaxwell>
https://en.wikipedia.org/wiki/Package-merge_algorithm is how you solve the capacited depth version; this https://arxiv.org/pdf/cs/0701012 also looks relevant

<maaku>
Oh, and here's a practical justification: key tree threshold signatures where 'individual' signers use their own internal thresholds. for example, a 4-way script has an 'everybody signs' top-level conditional that must actually be the combinatorial possibilities of each individual signer

<maaku>
and in many cases each actor would specify their own probability distribution for their sub-key combinations. e.g. if it is 2-of-3 there is 84% confidence one set of 2 keys will be used, 15% confidence the other set, and 1% for the worst-case paper key recovery

<maaku>
that could easily chop up high level reasoning about what the tree structure "should" be, and at some point it becomes better to add probability semantics to the key-tree-like signing condition language and have it auto-generate tree structures via a standard method

<maaku>
sipa: Interesting tidbit that probably has a theoretical explanation : if you enumerate the number of possible proofs (tree structure plus has inclusion bit) for k-of-n, for all n between 1 and max is equal to 2^(max+1) - 1

<maaku>
so all k-of-n for 0<=k<=n and 0<=n<=7 hass 255 possible resulting trees / proof bits if you simply enumerate them

<maaku>
damnit that was too good of a result to be true. why do I always find an error right after announcing something?