Theoretical computer scientists have successfully applied for the following in the past.
Full Proposal Deadline Date: October 21, 2015
Program Guidelines: NSF 14-582
The purpose of the Mathematical Sciences Postdoctoral Research Fellowships (MSPRF) is to support future leaders in mathematics and statistics by facilitating their participation in postdoctoral research environments that will have maximal impact on their future scientific development. There are two options for awardees: Research Fellowship and Research Instructorship. Awards will support research in areas of mathematics and statistics, including applications to other disciplines.
More at http://www.nsf.gov/funding/pgm_summ.jsp?pims_id=5301&WT.mc_id=USNSF_39&WT.mc_ev=click
Theory Matters 