c0deb0t

PTHash and other minimum perfect hash functions return an arbitrary value if the query key did not exist when building the MPHF, so they can be a lot smaller. B-field can identify query keys that don't exist in the set (with high probability?).

What I'm wondering is why the Kraken2 probabilistic hash table doesn't work. It uses 32 bits per element in an open addressing hash table. For 1 billion k-mers and 19 bits for the value, 32 - 19 = 13 bits of the key hash can be stored alongside the value, helping disambiguate hash collisions. If the load factor is 1.25x, then that's 4 * 10^9 * 1.25 = 5GB total, better than ~7GB. Also, this is only one cache miss (+ linear probing that can be SIMD accelerated) per lookup.

Adversarial attacks is a super interesting field, but unfortunately I feel that a lot of papers are just incremental attack or defense improvements like a cat-and-mouse game. I originally did some research on 3D point cloud attacks, but later stopped because making super successful attacks (eg., attacks with higher success rates than all the previous techniques for some very specific task) don't really help us understand that much more about neural nets, its just optimizing a metric for publishing papers. This kind of research is quite common, even at top conferences.

Despite this, recently, we made a 1 minute explainer video introducing adversarial attacks on neural nets as a submission for the Veritasium contest: https://youtu.be/hNuhdf-fL_g Give it a watch!

Yes, this will uwuify your text at high speeds. It reached 2.3 GB/s on my 8-core macbook pro, while uwu-ing the first 1 GB of english Wikipedia. This Rust command-line tool takes advantage of SSE4.1 SIMD vectorization and multithreading (exploit all your CPU cores for this!) to be almost as fast as simply copying a file. Installing it is simply cargo install uwuify, assuming you already have Rust installed. It is on crate.io too: https://crates.io/crates/uwuify

In case you don't know what uwu'd text looks like, here's an example:

hey... i think i w-weawwy wuv you. (⑅˘꒳˘) d-do you want a headpat?

Yes, this will uwuify your text at high speeds. It reached 2.3 GB/s on my 8-core macbook pro, while uwu-ing the first 1 GB of english Wikipedia. This Rust command-line tool takes advantage of SSE4.1 SIMD vectorization and multithreading to be almost as fast as simply copying a file. Installing it is simply cargo install uwuify, assuming you already have Rust installed. It is on crate.io: https://crates.io/crates/uwuify

For binary trees, indexing can be done by saving the subtree size of each node and doing a sort of binary search. Not sure if this is fast for B-trees that have more than 2 children nodes, though.

I'm a high school student that is quite new to Rust, and I am liking it so far. I learned a lot from this project and I hope that it can be a good learning resource for others.

In addition to this, I am also working on a SIMD edit distance library in Rust.

Since I am storing the entire DP matrix as diagonal vectors that are flattened, I don't think there will be many cache misses. Each diagonal only depends on its previous two diagonals, and each diagonal is stored contiguously in memory.

The problem with handling diagonals is that indexing cells and comparing characters on the diagonal becomes complex. Dealing with this without many branches (less branch mispredictions) is the hard part.

I took a look at the code, and read the paper. It seems that they directly calculate the entire 2D DP array, but use SIMD to allow each cell to contain multiple values, one for each query string. My approach uses anti-diagonals instead, but it is fast for one vs one comparisons, instead of handling multiple query strings.

Regardless, my goal was to learn some SIMD and Rust (first time for both), so I did not read many background papers.

Though I probably won't implement the different weighting schemes, I currently have alignment traceback and searching (allow "free shifts" for the pattern string) features.

High school is out so I am learning SIMD instruction sets, like AVX2 and SSE, and using these to speed up Hamming/Levenshtein distance calculations in Rust. Preliminary testing shows a 20x speedup using vectorized SIMD operations! The end goal is a full Rust library for edit distance routines.

Sneak peek of the code: https://twitter.com/daniel_c0deb0t/status/124224838155819008...

I am a high school student, and this is a published paper that I wrote. If you want to read a shorter blog version of my work, please take a look at my blog: https://blog.liudaniel.com/n-grams-BK-trees. I enjoy working on bringing computer science algorithms to other fields like biology. I have also worked on algorithms for machine learning security.

The general problem that this paper addressed is grouping similar DNA/RNA sequences based on something known as a Unique Molecular Identifier, and then collapsing those groups into consensus sequences. This helps estimate the number of unique sequences while efficiently accounting for substitution errors in sequencing or PCR amplification.

If you have any questions, feel free to ask me!

I am a high school student, and this is a published paper that I wrote. If you want to read a shorter blog version of my work, please take a look at my blog: https://blog.liudaniel.com/n-grams-BK-trees. I enjoy working on bringing computer science to other fields like biology. I have also worked on algorithms for machine learning security.

The general problem that this paper addressed is grouping similar DNA/RNA sequences based on something known as a Unique Molecular Identifier, and then collapsing those groups into consensus sequences. This helps estimate the number of unique sequences while efficiently accounting for substitution errors in sequencing or PCR amplification.

If you have any questions, feel free to ask me!

I am a high school student, and this is a published paper that I wrote. If you want to read a shorter blog version of my work, please take a look at my blog: https://blog.liudaniel.com/n-grams-BK-trees. I enjoy working on bringing computer science to other fields like biology. I have also worked on algorithms for machine learning security.

The general problem that this paper addressed is grouping similar DNA/RNA sequences based on something known as a Unique Molecular Identifier, and then collapsing those groups into consensus sequences. This helps estimate the number of unique sequences while efficiently accounting for substitution errors in sequencing or PCR amplification.

If you have any questions, feel free to ask me!

I implemented many deep learning algorithms in this library, mainly as a way to learn about deep learning. Beware, it is very slow since it is written in Java and there is no GPU acceleration. Maybe this will be of use to people who are learning new deep learning concepts.

If you have any questions, feel free to ask me!

I am a high school student, and this is a published paper that I wrote. If you want to read a shorter blog version of my work, go here: https://blog.liudaniel.com/n-grams-BK-trees.

The general problem is grouping similar DNA/RNA sequences based on something known as a Unique Molecular Identifier, and then collapsing those groups into consensus sequences. This helps estimate the number of unique sequences while efficiently accounting for errors in sequencing or PCR amplification.

If you have any questions, feel free to ask me!

I am a high school student and this blog post is a summary of a research project I did. The full published paper can be viewed here: https://peerj.com/articles/8275/.

This is not really explained in the blog post, but the "naive" method is O(N^2) brute force search, and the "combos" method is recursively going through all combinations of UMIs within a certain edit distance. There are also some other variants that are evaluated.

If you have any questions, feel free to ask me!

If you want research experiences, then try to email professors directly. Summarize your experiences and how it aligns with the professors' interests.

Otherwise, try reimplementing algorithms and blogging about them. Do fun projects like deploying a model online or to phones. If you are a fan of competitions, then you can try some Kaggle competitions. With some projects (if you say you have experience then you probably already done some) it should not be hard to get research experiences because you have something to show off. Remember to post your projects on Reddit and HackerNews to get internet points and encouragement! It is quite motivating.

Well, I used to play a lot of competitive FPS games because I found it fun. I have also done competitive programming problems for fun/accolades. But after doing more practical research, I realized it felt better to do impactful stuff (especially getting recognized). Also, research is nice because I perform terrible at short events (games, contests) under pressure. I think that if I tried something else before research that met the same criteria I probably wouldn't have done research.

There is one thing I forgot in my advice: you need to have a good foundation first. For example, when I cold emailed, I had many programming projects and I wrote about them in the email. But after you have stuff done, I think aggressively (but politely) "marketing" your work is important to get those opportunities.

I don't really think its fair to say that the "field is in a sad state". Plenty of insightful and well-written papers are put out everyday by hardworking and intelligent people. I still have a long way to go.

I do research because I like solving hard problems that people have never considered. I like to ensure that what I have learned will be put into practical use.

Thanks for your comments and encouragements!

The success rates of the attacks are not really emphasized---we only show that they work. They provide other benefits like robustness against point removal defenses.

The attacks are optimized for different criterion. The sticks attack is supposed to be easy to construct, at the cost of perceptibility. The distributional attack is more geared towards imperceptibility. Indeed, we do bound the perceptibility of the sticks and sinks attacks, just with different metrics. You can even argue that the number of sticks we generate is a measure of perceptibility. Compared to other papers in terms of visual perceptibility, our attacks are not that crazy. Of course, human perception is the true metric, and I think more work must be done on quantifying perceptibility in 3D. This paper is the first step, and I mainly wanted to show that there are factors other than perceptibility that we care about.

Feeding examples generated by an attack back into the network is a very classical defense mechanism. This works ok, but it is not attack-agnostic, and removing adversarial points works better in 3D. There are also works (mostly in 2D) on detecting adversarial examples with neural networks.

I am not sure about statistical identification, but we show that it is difficult to identify and remove adversarial points by looking for statistical outliers points.

I am not sure about truly robust 3D-specific defenses---if anyone has some idea, I am open to collaboration. I would imagine some sort of provably robust method built specifically to handle the varying density and distribution of points.

Yes, there are similar ideas to removing points, like masks and other transformations. Removing points is merely a 3D equivalent of the idea of destroying potentially adversarial information. I guess you can "remove" a pixel by setting it to a certain color, so my statement is not entirely accurate. However, point-removal methods are able to take into consideration the distribution of points, which is unique to 3D point sets. Furthermore, there are a lot of redundant points on the surface of an object, which means that removing a few points will not destroy the shape information.

This paper does suggest that we can circumvent certain domain-specific knowledge when attacking. This does not mean that we won't discover methods to utilize domain-specific knowledge in the future. I would imagine extending current provably robust methods to 3D would require domain-specific knowledge to deal with the distribution of points.

Yep, and it is college application season!

Sorry, I'm not too knowledgeable of the math part of the distribution. Usually, we would want some set of points from the surface of the object that maximizes the distance between each point and its nearest neighbors. Then, the points would be distributed with uniform density across the surface.

In my previous paper, I've shown that moving the points around on the surface of an object does lead to imperceptible but effective adversarial attacks, as you've observed.

Yep, Ronald is extremely nice and helpful!

Cold email plus a bit of luck, and then an informal interview in person. My best advice for anyone wanting to get connected is to not be shy. To get opportunities and connections, you have to put yourself out there. This comes with the risk of criticism.

Many previous algorithms (adversarial training, distillation, most attacks, etc.) can be used in 3D in a fairly straightforward manner as they are architecture-agnostic. However, they do not make use of specific properties that are present in 3D point sets and the 3D neural networks. For example, removing points as an attack or a defense is specific to point sets; you cannot really remove pixels in an image. The distribution of points in a point cloud also gives us information that can be used in defenses, but the attacker can also tamper with it (this is partially the focus of this work).

Similarly, adversarial attacks/defenses are still being proposed for graphs, audio, and other domains because we can leverage domain-specific knowledge.

If you have any questions, I (the first author of the paper) will be more than happy to answer them. This is my second work in a series on adversarial attacks/defenses in 3D space (first paper [1]).

A high-level overview of the research:

Basically neural networks are weak against adversarial attacks that change the input by a little bit to cause the prediction to be wrong. We look at these adversarial attacks in 3D space, specifically on 3D point clouds (think LiDAR and RGB-D data). In the paper, four attacks in two different categories (distributional and shape attacks) are proposed. The main benefit of distributional attacks is their imperceptibility. On the other hand, shape attacks are more easily crafted in real-life (though more perceptible) and also robust against point removal defenses that were proposed in previous work. If you want a more comprehensive (but less dense than the paper) overview, take a look at my blog post [2].

[1] https://arxiv.org/abs/1901.03006

[2] https://blog.liudaniel.com/birth-of-a-new-sub-sub-field