SCS Recruiting Seminar: Josh Alman

Event Details
  • Date/Time:
    • Tuesday February 5, 2019 - Wednesday February 6, 2019
      11:00 am - 11:59 am
  • Location: KACB 1116W
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:

Tess Malone, Communications Officer


Summary Sentence: Title: Algebraic Tools in Algorithms and Complexity

Full Summary: No summary paragraph submitted.

  • Josh Alman Josh Alman

TITLE: Algebraic Tools in Algorithms and Complexity


In this talk, I will speak about how algebraic tools can be used to solve problems throughout computer science. I will focus on two such tools: algorithms for quickly multiplying matrices and mathematical techniques for approximating functions by low-degree polynomials. I will survey how these two tools, when combined, yield a wide variety of new results, including:

- the fastest known algorithm for batch nearest neighbor search, where one is given many data points and wants to find the “most similar” pairs of points according to various metrics,
- state-of-the-art limitation results for threshold circuits, a loose model of neural networks,
- a new, efficient representation of the Walsh-Hadamard transform from signal processing, and
- limitations on all known approaches to designing fast matrix multiplication algorithms.


Josh Alman is a Ph.D. candidate in computer science at MIT, where he is advised by Ryan Williams and Virginia Vassilevska Williams. He received his master’s in computer science from Stanford in 2016 and his bachelor’s in mathematics from MIT in 2014.

Additional Information

In Campus Calendar

College of Computing, School of Computer Science

Invited Audience
Faculty/Staff, Postdoc, Public, Graduate students, Undergraduate students
No keywords were submitted.
  • Created By: Tess Malone
  • Workflow Status: Published
  • Created On: Jan 28, 2019 - 3:57pm
  • Last Updated: Jan 28, 2019 - 4:49pm