(CLOSED) Randomized Algorithms for Combinatorial Scientific Computing (DE-FOA-0002722)

Sponsor Name: 
DOE Office of Science
Description of the Award: 

The DOE SC program in Advanced Scientific Computing Research (ASCR) hereby announces its interest in basic research in the design, development, analysis, and scalability of randomized algorithms for the challenging discrete and combinatorial problems that arise in the Department’s energy, environmental, and national security mission areas.

Randomized algorithms are enabling advances in scientific machine learning and artificial intelligence (AI) for a wide range of “AI for Science” uses. Scientific discovery in priority areas such as climate science, astrophysics, fusion, materials design, combustion, and the Energy Earthshots initiative will make use of increased understanding in randomized algorithms for surmounting the challenges of computational complexity, robustness, and scalability. Randomized algorithms also represent a major thrust for applied mathematics and computer science basic research, and such thrusts are essential for future progress in advanced scientific computing.

Randomized algorithms employ some form of randomness in internal algorithmic decisions to accelerate time to solution, increase scalability, or improve reliability. Examples include matrix sketching for solving large-scale least-squares problems and stochastic gradient descent for training scientific machine learning models. Rather than using heuristic or ad-hoc methods, thedesired objective is the development of efficient randomized algorithms that have certificates of correctness and probabilistic guarantees of optimality or near-optimality.

ASCR held a four-day virtual workshop on “Randomized Algorithms for Scientific Computing (RASC)” on December 2-3, 2020 and January 6-7, 2021. The subsequent workshop report articulates how randomized algorithms research is motivated by application needs and drivers such as: Massive data from experiments, observations, and simulations; Forward problems; Inverse problems; Applications with discrete structure; Experimental designs; Software and libraries for scientific computing; Emerging hardware; and Scientific machine learning. For data collection, advances in imaging technologies – such as X-ray ptychography, electron microscopy, or electron energy loss spectroscopy – collect hyperspectral imaging and scattering data in terabytes and at high speeds enabled by state-of-the art detectors. The data collection is exceptionally fast relative to its analysis. Similarly, advances in high-performance computing and exascale systems have changed the nature of scientific computing research. An increasing trend is that faster hardware makes data easier to generate, but more challenging to rapidly analyze. For problems with discrete structure – such as the Internet, power grids and biological networks – faster and better ways are needed to analyze, sample, manage, and sort discrete events, graphs, and data streams.

Research Area
The overarching goal of randomized algorithms research, under this Funding Opportunity Announcement (FOA), is to find scalable ways to sample, organize, search, or analyze very large data streams, discrete structures, and combinatorial problems relevant to DOE mission areas. The five research topics of interest focus on algorithms for discrete and combinatorial problems as highlighted in the RASC workshop report:

  1. Randomized algorithms for discrete problems that cannot be modeled as networks
  2. Randomized algorithms for solving well-defined problems on networks
  3. Universal sketching and sampling on discrete data
  4. Randomized algorithms for combinatorial and discrete optimization
  5. Randomized algorithms for machine learning on networks
Limit (Number of applicants permitted per institution): 
Sponsor LOI Deadline: 
May 19, 2022
Sponsor Final Deadline: 
Jun 30, 2022
OSVPR Application or NOI Instructions: 

If you intend to submit complete the notification form to provide your contact information and the title and brief description of your project.

To be considered as a Penn State institutional nominee, please submit a notice of intent by the date provided directly below.
Penn State OSVPR NOI Deadline: 
Monday, April 25, 2022 - 4:00pm
This limited submission is in downselect: 
Penn State may only submit a specific number of proposals to this funding opportunity. The number of NOIs received require that an internal competition take place, thus, a downselect process has commenced. No Penn State researchers may apply to this opportunity outside of this downselect process. To apply for this limited submission, please use this link:
For help or questions: 

Questions concerning the limited submissions process may be submitted to limitedsubs@psu.edu.

Kamesh Madduri (CoE); PSU is eligible to submit one additional pre-application to DOE, contact limitedsubs@psu.edu if interested.