Adithya Bhaskara

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

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/...

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.

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...

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!

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!

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

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!

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...

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

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!

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

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!

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.

For correctness, note that if AB - C = 0, then ABx - Cx = 0 with probability 1. Note dim(ker(AB - C)) ≤ n - 1. So, if AB - C ≠ 0 but ABx - Cx = 0, x is a linear combination of at most n - 1 vectors out of a possible 2n options. So, Pr[AB - C≠0] ≤ 1/2, as desired.

Yes! Let's look at Kimbrel and Sinha's algorithm [KS93].

1. compute a prime p in {2n,...,4n}
2. sample α ~ {1,...,2n} uniformly at random
3. let x = {α^0 mod p,...,α^(n-1) mod p)^T
4. return true iff ABx - Cx = 0

We can drive the probability down by running Freivalds' algorithm repeatedly, and since Freivalds' procedure uses three matrix-vector multiplications, Freivalds' algorithm is an O(n^2) time algorithm that solves MMV with high probability. It uses n random bits.

Can we do better than n random bits?

The last ≤ is due to:

1. write ⟨k,x⟩ = k_ix_i + r where k_i ≠ 0 is a component of k and r = sum(j ≠ i) k_jx_j.

2a. if r = 0, then ⟨k,x⟩ = 0 iff x_i = 0, true with probability 1/2.

2b. if r ≠ 0, then ⟨k,x⟩ = 0 iff x_i = 1 and k_i = -r, true with probability ≤ 1/2.

Freivalds' algorithm [Fre79] is as follows:

1. sample x ~ {0,1}^n uniformly at random
2. return true iff ABx - Cx = 0

Observe that (AB - C)x = 0 iff ABx = Cx. If AB - C = 0, then ABx - Cx = 0 with probability 1.

Else, AB - C must have a nonzero row k. So, Pr_x[ABx - Cx=0] ≤ Pr_x[⟨k,x⟩=0] ≤ 1/2.

So, what is matrix multiplication verification? Say Alice has two n × n matrices A and B she'd like to multiply, and Bob has a powerful computer. Alice sends the matrices to Bob, who sends back the purported product C. How can Alice decide whether C = AB without computing the product herself?

Kimbrel's receipt of this honor is well-deserved! To celebrate, I'll discuss the matrix multiplication verification problem and his improvement with R.K. Sinha [KS93] to Freivalds' algorithm [Fre79].

More improvements are ongoing work, joint with @huckbennett.bsky.social and @noahsd.bsky.social!