Recent searches

No recent searches

Search options

Only available when logged in.
sigmoid.social is one of the many independent Mastodon servers you can use to participate in the fediverse.
A social space for people researching, working with, or just interested in AI!

Administered by:

Server stats:

596
active users

sigmoid.social: AboutProfiles directoryPrivacy policy

Mastodon: AboutGet the appKeyboard shortcutsView source codev4.4.2

#tcs

0 posts0 participants0 posts today
Sebastian Forster

I'll be at #ICALP in Aarhus next week, and more precisely will give a talk at TAAP25, a satellite workshop, on Monday. TAAP stands for Theory and Applications of Algorithms with Predictions. #tcs

I'll travel through all of Germany by train on Sunday. Wish me luck! 🙃

Continued thread
*
Joshua Grochow

This is an example of amortized complexity and Strassen's "asymptotic spectra" (nice monograph by Zuiddam & Wigderson: math.ias.edu/~avi/PUBLICATIONS)

Strassen developed this to understand the #complexity of matrix multiplication and #tensors, but it turns out to also show up in a bunch of places:
- #Entropy
- #Quantum information
- Shannon capacity of graphs
- Communication complexity en.wikipedia.org/wiki/Communic
- Circuit complexity (Robere & Zuiddam eccc.weizmann.ac.il/report/202)

#math#probability#ComputationalComplexity
*
Joshua Grochow

Real coin flips are ~49-51 not 50-50 scientificamerican.com/article

But you can guarantee equal probability with a simple trick! Flip 2x in a row starting with the same side up.

HT->call it H
TH->call it T
HH,TT->try again

(due to von Neumann en.wikipedia.org/wiki/Randomne)

This leads to randomness extractors: from a given random process, what's the biggest uniform distribution you can get efficiently?

Randomness extractors give another interpretation of #entropy:

avg # bits needed to *describe* the outcome
=
# uniformly random bits you can *extract* from the outcome

Scientific American · Scientists Destroy Illusion That Coin Toss Flips Are 50–50By Shi En Kim
#math#probability#ComputationalComplexity
Akshar Varma

BB(5) = 47,176,870

Possibly the last busy beaver number we'll ever know definitively:
discuss.bbchallenge.org/t/july

The quanta article linked at the end provides a very nice overview of the history of the humans and computers involved in the story: quantamagazine.org/amateur-mat

Scott Aaronson's blog post provides some technical details and a variety of other reference links: scottaaronson.blog/?p=8088

Apart from the crazy technical aspects, what I find most exciting and interesting is how some (many?) of those involved are "amateur mathematicians", in it because they love mathematics and found this problem challenging.

The Busy Beaver Challenge · [July 2nd 2024] We have proved "BB(5) = 47,176,870"BB(5) = 47,176,870 We are extremely happy to announce that, after two years of intense collaboration, the goal of the Busy Beaver Challenge has been reached: the conjecture “BB(5) = 47,176,870” is proved. Exceeding our expectations, the proof has been formally written in Coq by collaborator mxdys whose work improves on and/or uses the contributions of more than 10 other bbchallenge contributors (see credits). The formal theorem’s statement was reviewed by independent Coq experts (see credits) ...
#math#TCS#BusyBeaver
TrendingLive feeds
About