Wikipedia just told me there's a galactic algorithm for integer multiplication in O(n log n) based on FFT so I'm guessing those two proofs are related.
It fascinates me that there's something like this in something as solid and rigid like matrix multiplication. What causes something so rigid to break apart and "leak" at very large scale? Why does the "optimization" appear to be very, very small? Why does galactic algorithm exists? I can't imagine long division suddenly breaking apart after a billion digit, the structure seems very stable? I have heard before that matrix multiplication is apparently optimize-able at very, very large scale.
Does anyone have an intuition to what causes it? What happens at these large scale (or very small)?
One way to think about it is that the classical algorithms are the ones that are fast for small numbers. Galactic algorithms often work for small inputs, it's just that to be faster you need big inputs. A common case of this is a requirement that log(n)<<klog(log(n)). If k=100 then this algorithm will take huge sizes to win
Then 'n' means kind of different things for sorting vs. multiplication though. For example for sorting we assume constant time comparison, which doesn't make sense inputs of O(n) bits
If you sort n k-bit items for a total time of O(nk logn), that scales more poorly in n than multiplying n-word integers. Of course if k is constant you can do radix sort, but I genuinely don't know under what conditions radix sort is more/less galactic than this multiplication algorithm.
this alg is way more galactic than radix sort. radix sort often wins in the hundreds of elements. the nlogn multiplication requires numbers with more digits than atoms in the universe (although that could probably be brought down a lot)
Ah thanks for pointing this out, for some reason I had always equated radix sort and bucket sort (with 2^k buckets) in my head. But I learned today that this isn't true!
even though the constant is tiny, this breaks the long held assumption that nlogn is the minimal possible bound, so further research seemed unfruitful. this discovery will now trigger more research in this area, and probably more optimal algorithms will be discovered.
Like matrix multiplication, the common assumption was that it cannot be improved past n^3. Then Strassen broke the barrier (with a more significant constant) which caused intensive research - and now we are around n^2.3..2.4.
Any strong enough model with weak enough safeguards can cause an AI Chernobyl event that will make people and governments against AI development and deployment, just like Chernobyl did for nuclear energy.
Removing AI watermarks is still easier than doing a school assignment.
The only way to prevent AI cheating is to make the assignments in class in pen and paper. To be honest, I don't understand why schools moved away from that in the first place.
Yes, and back in my school days we all did our tests on paper, except the two kids who had a slip of paper that allowed them to take a digital test instead. Helping people with disabilities doesn't require having everyone make their tests on a computer.
And taking away writing from people with bad handwriting (if not related to disability) is just about the worst thing to do if you want them to ever get better at it.
Idk, I’ve had bad handwriting my entire childhood and I still have bad handwriting now as an adult. I’ve (somewhat jokingly) announced that I am “illegible”. It isn’t a detriment to my day to day activities at all, because I can type sufficiently well
And now instead of teaching disabled students how to improve their handwriting to improve their lives regardless of their circumstances, we lowered the bar and made all students have bad handwriting.
I am talking about disabilities which affect things like motor control which means that they cannot improve their handwriting very much.
How does good handwriting improve people's live significantly? I know some people who prefer handwritten notes and I think there is research that says they can be more effective when learning, but most adults very rarely write more than a few lines by hand.
You could say the same of PE, maths, literature, or almost anything learned in school. Few adults need them in their lives, but they provide good habits and virtue to students. People who don't read and write anything outside social media are a loss to themselves and to society.
Disabilities don't disappear after school, and children who struggle with motor control in school will continue struggling with it on adulthood. Half the point of school is finding out your weaknesses and learning to overcome them in a safe and controlled environment.
Studying maths and literature should develop your mind in many ways and gives you a chance to enrich your life. I do not see how handwriting will do that.
Pushing someone with a disability to improve their handwriting will not cure their disability. How does making people struggle more help them? its like suggesting kids in wheelchairs should be made to try to walk.
> . Half the point of school is finding out your weaknesses and learning to overcome them
Learning to use a computer as a means to overcome a disability that makes handwriting painful or difficult or illegible sounds like it'd qualify as exactly that.
I have been successfully using the Consent-O-Matic extension [1] to auto-decline all cookie and GDPR banners. As much as I'm not comfortable giving potential access to every website to some extension developers, this improved my internet experience almost as much as AdBlock.
Seeing that the series aired on Apple TV+, it seems like Apple knows exactly what its employees are doing. Maybe they just turned what their employees want into a drama? hehe
I wouldn't be surprised if the EU and ISPs are funding fibre to remote locations _because_ of Starlink competition.
Taxis and minicabs all over the world were unreliable, expensive, and unsafe before Uber came along with some healthy competition. The same dynamic is happening here between Starlink and rural fibre.
The killer feature of Organic Maps and OSM is the POI markers for small things. If you are cycling, knowing where the nearest bike rack is to your location is crucial.
Google Maps is very good at showing car parking spaces, which is the requirement if you live in a suburb in California like its developers.
What's the status of banking apps, Google / Microsoft authenticator, and Google Wallet? Those were the things preventing me from abandoning stock Android.
Authenticators should work normally, as far as I know (unless Google Authenticator does anything special). Can’t say anything about Google Wallet. There might be more lists/forums where people share which setups are (not) working well for them.
In general, I had these concerns as well until a few months ago. But I am much more optimistic these days that things will just work well out of the box (have read many positive sentiments in blog posts and here on Hacker News).
Nobody in the chain of command thought this was a real emergency situation.
The point of turning Bluetooth off or having to turn around the aircraft was to follow the airline's rules on terrorism, which likely tell them to abort a flight route if there's any symbol that could be interpreted as a bomb.
The captains were risking their jobs if they didn't follow this stupid request. This is a good case for getting common-sense exceptions to checklist-style rules.
> Example: Point at a date in an email to instantly set up a meeting, find good spots to meet up, or draft a reply.
This is actually a good use case for AI. My university sends a lot of newsletters with several events in free text format; all I want is to be able to select one of them, have an LLM parse the title, date, location, and category, and put it in my calendar.
Still, I'm sceptical this will work. Samsung phones supposedly have this same feature, and it works 1/10 of the times. Pasting it to ChatGPT and tell it to add the events to my calendar works fine, but the bottleneck is always the project managers in charge of the UI. Of course, having a small local model and being able to choose my own right-click items like I could in 1995 would be an actual solution.
LMAO, I don't think I ever saw such a small number in a CS result.
reply