rob-p · HackerTrans

позавчераdiscuss

The giant yellow warning, unfortunately, says nothing about "complexity safety". As I note, even though I think the first failure (failure to help port an open source C++ codebase to Rust, simply because the tool itself deals with genomic data) is possibly explicable given their warnings, the refusal to engage with trying to resolve the complexity class of an abstract graph problem really has no reasonable explanation in light of all of the documentation and warnings that Anthropic has written about Fable's "guard rails".

rob-p

позавчераdiscuss

The abstract problem absolutely has legitimate interpretations outside of phylogenetics, and there are other ways to formulate the problem that directly relate to linear algebra over GF(2). Reformulating the problem in those contexts also failed. It is a legitimate, pure CS theory question, that itself relates quite closely so several other known results including in computational geometry

https://arxiv.org/abs/2003.02801

https://doi.org/10.1016/j.comgeo.2024.102102

https://arxiv.org/abs/2107.10339

https://dl.acm.org/doi/10.1145/1998196.1998218 — DOI: 10.1145/1998196.1998218

The problem in the post is right at the edge of variants that are known to be in P and variants that have been proven NP-complete. So, in this case, it is simply Fable refusing to engage with a theory question.

Also, as I note in the post:

This may not be true for everyone, but for anyone working in Bioinformatics, Genomics, Computational Biology, Biology, Cybersecurity, and, seemingly Computer Science, this seems to be the case.

Of course it can go on a tear for various coding challenges. However, the more that I learn the more that I also suspect that it rejects not just prompts that may relate tenuously to biology or cybersecurity, but also otherwise completely innocuous prompts that are issued by people who work in areas adjacent to biology and cybersecurity. If true, I think that is certainly a bridge too far, and a hard policy to defend.

rob-p

3 дня назадdiscuss

But none of which suggest that it is not useful for math or theoretical CS tasks. The biology classifier is so miscalibrated so as to render the model useless for biology; and yes, they hint at that on the label (but not the extent of it). However, there is no description or suggestion that it is so miscalibrated that it offers up refusals in completely innocuous theoretical tasks. If it is simply a state-of-the-art model for coding, and frontend design, so be it, but at least they should be honest about that.

rob-p

9 месяцев назадdiscuss

Your statement conveys a lack of knowledge of the main purpose of minimal perfect hash functions, as compared to generic/general hash tables (which are a more general, but therefore, in some cases, less efficient data structure). The main point of the MPHF is not to be order preserving, or to provide a prescribed function from the keys to [1...n]. Rather, it is to provide a collision free mapping between the set of keys and [1..n].

The fact that minimal perfect hashes do not reject alien keys is not an "academic" limitation, it is implicit in the definition of the problem being solved. In fact, the relevant space bounds cannot be satisfied if you either (1) must reject elements not in the key set at the time of construction or (2) require a prescribed order be assigned to the specific keys.

However, even given your misapprehensions about the purpose of minimal perfect hash functions, your statement about how they are not useful in practice is also simply false. You are describing uses for classical hash tables that store their key set explicitly and in their entirety. These serve an entirely different purpose in application to minimal perfect hash functions.

Minimal perfect hash functions are particularly useful when you know the key set ahead of time and are certain that only valid keys will be queried. In this case, the values can be stored in a flat array (in the order prescribed by the MPHF) and the cost of the hash itself is only ~2 bits/key. So the total storage is the minimal storage for the values + a small overhead to allow constant-time access to the value for a given key. If you need to reject alien keys, then you can of course store those as well. In that case, the MPHF costs the storage cost for the key set + value set + ~2 bits/key; still smaller than most existing dynamic hash tables.

In many cases, you don't need an ordering table. If you are allowed to permute the keys and all you require is O(1) access to the corresponding index for a key, then the additional ordering table is unnecessary overhead. On the other hand, if you need, for some reason, to remap the keys to be in a specific order, then this is easy simply by iterating over the keys and observing what indices they yield.

Many times, people wish to use MPHFs for non-static purposes (i.e. where the key set is not known at compile time). Consider e.g. in network mapping (https://dl.acm.org/doi/abs/10.1109/tnet.2018.2820067), or in taxonomic classification (https://academic.oup.com/bioinformatics/article/34/1/171/393...) or in k-mer indexing (https://academic.oup.com/bioinformatics/article/34/13/i169/5... or https://academic.oup.com/bioinformatics/article/38/Supplemen...). Moreover, MPHFs form the basis for near-optimal static filters, by storing fingerprints of the keys in the indexed spots (https://www.sciencedirect.com/science/article/pii/S0166218X1...).

Simply because a particular MPHF construction doesn't suit the problem you have in mind doesn't mean it's not useful or that it's "academic". MPHFs have plenty of uses, some without the need for a key routing or key-reordeing table. Other times, one needs the keys in a particular order and even then MPHFs are very useful because if the key set is static, the MPHF + the rerouting table is often still smaller than alternative dynamic hash table approaches while being similarly fast for query. They can be built in an parallel, external memory, and cache efficient manner.

The argument that MPHFs are "academic" and not useful because they don't adhere to constraints to which they are not intended to adhere is like arguing that a hammer is not useful because you cannot use it to tighten philips head screws.

rob-p

9 месяцев назадdiscuss

Uhh, there is nothing at all "academic" about pthash, (or phast, or ptrhash), apart from the fact that they also described their ideas in papers. All of those tools work on massive sets of data, support massively parallel construction, and support external memory construction. They are all well-engineered libraries and not "academic" in any derogatory sense.

comments