Lightnews — Scholar-powered news

Adithya Bhaskara @adithyacolorado.bsky.social · 15h

I'll end here. As always, if there are any mistakes or comments, I'm all ears!

Adithya Bhaskara @adithyacolorado.bsky.social · 15h

Interestingly, fast MM algorithms give rise to fast algorithms for closely related problems. For example, an O(n^ω) algorithm for MM implies (and vice versa!) an O(n^ω) algorithm for the computation of inverses, determinants, kernels, characteristic polynomials, and more!

1

Adithya Bhaskara @adithyacolorado.bsky.social · 15h

For example, rank((2,2,2)) ≤ 7 corresponds to Strassen's result. A bound due to Pan, [Pan78], gives rank((70,70,70)) ≤ 143640, yielding a O(n^2.79)-time algorithm!

1

Adithya Bhaskara @adithyacolorado.bsky.social · 15h

The key result connecting tensor rank and fast MM algorithms is the following: if the rank of the (q,q,q) MM tensor is at most r, then there exists an O(n^(log_q(r))-time algorithm for MM.

1

Adithya Bhaskara @adithyacolorado.bsky.social · 15h

An important concept is the notion of tensor rank. Informally, the rank of a tensor T is the minimum number of rank 1 tensors that sum up to T. A rank 1 tensor is one that is nonzero and "fully factors."

1 1

Adithya Bhaskara @adithyacolorado.bsky.social · 15h

To generalize Strassen's algorithm, we can represent matrix multiplication as a bilinear map, i.e. a tensor (of order 3). I won't get into the specifics here (because they're hard to typeset), but the results are very interesting.

1

Adithya Bhaskara @adithyacolorado.bsky.social · 15h

Strassen's breakthrough [Str69] was discovered via an exhaustive case analysis, realizing that one could reduce 8 MM operations to 7. The recurrence is then
T(n) = 7T(n/2) + O(n^2) = O(n^(log 7)) ≤ O(n^2.8).

Strassen's realization was a result of trying to prove that O(n^3) was the optimal bound!

1

Adithya Bhaskara @adithyacolorado.bsky.social · 15h

A standard divide-and-conquer approach to MM consists of dividing the original n x n matrix into (n/2) x (n/2) blocks and performing the product blockwise. This gives us a recurrence

T(n) = 8T(n/2) + O(n^2) = 0(n^(log 8)) =0(n^3)

since we do 8 multiplications and O(n^2) work to read and recombine.

1

Adithya Bhaskara @adithyacolorado.bsky.social · 15h

Given this, I thought I'd write a thread about matrix multiplication (MM) complexity, starting with Strassen's result, and going from there!

Let ω = inf{ω' > 0, for all ε > 0, there exists an O(n^(ω'+ε))-
time algorithm to solve matrix multiplication}.

We know 2 < ω ≤ 3, and many conjecture ω = 2.

Simons Institute for the Theory of Computing @simonsinstitute.bsky.social · 1d

1/2 Should have paid attention to matrices during linear algebra classes! In 2026, AI will use ~1% of global electricity, of which ~45-90% will be for matrix multiplications, said Oded Schwartz of Hebrew University of Jerusalem at the Simons Institute. simons.berkeley.edu/talks/oded-s...

1 1

Reposted by Adithya Bhaskara

Quanta Magazine @quantamagazine.bsky.social · 7d

In optimization problems, randomness thwarts complexity.

Researchers Discover the Optimal Way To Optimize | Quanta Magazine

The leading approach to the simplex method, a widely used technique for balancing complex logistical constraints, can’t get any better.

www.quantamagazine.org

7 26

Adithya Bhaskara @adithyacolorado.bsky.social · 3d

I’ve seen "Lemma" for one direction, and "Theorem" stating both directions and proving one, and invoking the lemma for the other.

1 1

Adithya Bhaskara @adithyacolorado.bsky.social · 11d

I’m excited to travel to "Social Choice: Theory and Computation: An Interdisciplinary Conference on Voting, Representation, and Districting" next week at Wellesley College!

I’m enjoying diving into computational social choice research as I’m working on my senior thesis with Bailey Flanigan!

Social Choice: Theory and Computation conference - Institute for Mathematics and Democracy

Institute for Mathematics and Democracy, in collaboration with Wellesley College Wagner Centers, is organizing

mathematics-democracy-institute.org

2

Reposted by Adithya Bhaskara

Chara Podimata @charapod.bsky.social · 26d

We have a new paper out today, and I’m so proud of it and the work that went into creating it! Link here: arxiv.org/pdf/2509.184....

The 2024 US presidential election was the first major election in the US since the popularization of LLMs. (1/6)

1 3 10

Reposted by Adithya Bhaskara

Jed Brown @jedbrown.org · Aug 18

It is not "attribution and sourcing" to generate post-hoc citations that have not been read and did not inform the student's writing. Those should be regarded as fraudulent: artifacts testifying to human actions and thought that did not occur.
www.theverge.com/news/760508/...

For help with attribution and sourcing, Grammarly is releasing a citation finder agent that automatically generates correctly formatted citations backing up claims in a piece of writing, and an expert review agent that provides personalized, topic-specific feedback.

Screenshot from Grammarly's demo of inserting a post-hoc citation.
https://www.grammarly.com/ai-agents/citation-finder

6 75 230

Reposted by Adithya Bhaskara

Terence Tao @teorth.bsky.social · Aug 18

I wrote an op-ed on the world-class STEM research ecosystem in the United States, and how this ecosystem is now under attack on multiple fronts by the current administration: newsletter.ofthebrave.org/p/im-an-awar...

I’m an award-winning mathematician. Trump just cut my funding.

The “Mozart of Math” tried to stay out of politics. Then it came for his research.

newsletter.ofthebrave.org

17 310 750

Adithya Bhaskara @adithyacolorado.bsky.social · Aug 13

These experiences wouldn’t have been possible without the unending support of Raf Frongillo, @huckbennett.bsky.social, Sriram Sankaranarayanan, Joan Gabriele, and The Boettcher Foundation. I am very grateful!

Adithya Bhaskara @adithyacolorado.bsky.social · Aug 13

I decided to take time to reflect on my summer travel to STOC, EC, and CMMRS, and I wrote a blog post about my experiences!

I hope to make the funding opportunities that made my travel possible known to other undergrads. Most are Colorado/CU Boulder specific, but similar sources exist elsewhere!

my reflections on summer 2025 | Adithya Bhaskara my reflections on summer 2025 | Adithya Bhaskara

what i've been up to this summer!

officialadithya.github.io

1 2

Adithya Bhaskara @adithyacolorado.bsky.social · Aug 4

CMMRS’25 at the Max Planck Institutes in Saarbrücken was an amazing experience filled with great lectures and opportunities to meet several faculty and students from around the world!

Thank you to the organizers, especially Lorenzo Alvisi (Cornell) and Peter Druschel (MPI-SWS)!

cmmrs.mpi-sws.org

1

Adithya Bhaskara @adithyacolorado.bsky.social · Jul 11

Had an amazing time at #ACMEC25 this year! I met a lot of cool people and simultaneously learned a lot!

I especially enjoyed the social choice workshop.

Thank you to all the conference and workshop organizers!

4

Reposted by Adithya Bhaskara

ACM SIGecom @acmsigecom.bsky.social · Jul 2

See everyone at #ACMEC25 on Monday, July 7!

And while you're there, join us July 8, 8-10pm in Stanford Econ Landau 139 for a Wikipedia edit-a-thon!

Feel free to contribute to the crowdsourced list of topics that need attention: docs.google.com/spreadsheets...

Edit-a-thon

Let's get together and create or edit Wikipedia pages for EconCS entries. Both new and experienced Wiki editors are welcome!

sites.google.com

2 6

Adithya Bhaskara @adithyacolorado.bsky.social · Jun 23

First day of first STOC was amazing! Great talks all around, and meeting so many cool people!

1

Adithya Bhaskara @adithyacolorado.bsky.social · Jun 22

I’m excited to attend my first STOC this year on a grant funded by the Boettcher Foundation.

I’m relatively new to the broader theoretical CS community as a fourth-year undergrad, so I’m looking forward to meeting people here, especially fellow students!

I’d love to meet people in the same boat!

Adithya Bhaskara @adithyacolorado.bsky.social · Jun 1

Update: After writing this, I just realized @huckbennett.bsky.social also has a great thread about Kimbrel's algorithm! I'd recommend a read!

1

Adithya Bhaskara @adithyacolorado.bsky.social · Jun 1

Congratulations again to Tracy Kimbrel! Hopefully this summary of his matrix multiplication verification algorithm was enjoyable to read. I apologize in advance for any poor exposition and errors; it's my first time doing an overview in this format. Please let me know if you have any corrections!

1 1

Adithya Bhaskara @adithyacolorado.bsky.social · Jun 1

Kimbrel and Sinha's algorithm runs in O(n^2) time, like Freivalds', but, it uses only log_2(n)+O(1) random bits!

When AB-C is promised to have low Hamming weight, @huckbennett.bsky.social, Karthik Gajulapalli, Alexander Golovnev, and Evelyn Warton give an O(n^2) algorithm using fewer random bits.

arxiv.org

1 1