GSoC 2020: Introduction and IDEA PROPOSAL

[Rohin Garg]

Hi,

I am Rohin Garg, senior EECS undergraduate at IIT Kanpur and I am about to begin my MS-PhD in Computer Science.

I would like to work on mathematically intensive projects, and am particularly interested in Representation Theory, implementing Schubert and Grothendieck polynomials and/or Distance-regular graphs. I have a deep understanding of Graph Theory and Linear Algebra. I am proficient in C++ and Python, and have re-invented and implemented Randomized geometric algorithms in C++ before. I have started looking at some tickets on  https://trac.sagemath.org/ that I can begin with. I will contact the mentors soon to discuss some ideas.

IDEA PROPOSAL:

The idea isn't concrete yet and I hope to discuss this further with potential mentors.

Implementing Randomized Graph Algorithms: for spanning trees - I see that Sage has a module for spanning trees, but randomized spanning tree construction is still in the To Do list. Randomized algorithms are extremely powerful in many practical cases, and I would love to work towards an efficient computation of spanning trees (minimum, sparse) in weighted graphs.

Reference: "A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs" by S. Baswana et al. (https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20130)

Reference: "A randomized linear-time algorithm to find minimum spanning trees" by Karger et al. (https://dl.acm.org/doi/abs/10.1145/201019.201022)

Thank you for considering my proposal.

Regards,

Rohin Garg