Simons Collaborations in Mathematics and the Physical Sciences

The Simons Foundation has issued a call for proposals for their new program Simons Collaborations in Mathematics and the Physical Sciences.  The aim of the program is to “stimulate progress on fundamental scientific questions of major importance in the broad area of mathematics, theoretical physics, and theoretical computer science.”  An example is the Simons Collaboration on Algorithms and Geometry.

Grant sizes are up to $2.5m/year for 4 years (which can be extended to 7 years).  Letters of intent are due by October 31.

CATCS Presentation at STOC

Here is the CATCS Report from the STOC 2014 business meeting.  Of particular note are the following upcoming deadlines:

The NSF CRII program is new and was discussed during the NSF presentation at STOC.  This program provides graduate student support for new faculty who have not received grants before. It can help one get a research program started and enable a more competitive submission to the CAREER program in the future.  Contrary to initial announcements, the program is not restricted to US citizens, permanent residents, and nationals.  More information can be obtained form the 7/28 webinar or by contacting the program directors.




NSF Exploiting Parallelism & Scalability deadline 2/24

A reminder that the deadline for the NSF Exploiting Parallelism and Scalability (XPS) program is February 24.

Theorists who work on issues related to parallel computing are encouraged to consider applying to XPS program.  See the solicitation, the webinar by Tracy Kimbrel, and the FAQ for more information.

NSF CISE FY2014 Budget Request and Priorities

From: CISE Announcements [mailto:CISE-ANNOUNCE@LISTSERV.NSF.GOV] On Behalf Of Jahanian, Farnam
Sent: Thursday, April 11, 2013 11:20 AM
Subject: NSF CISE FY2014 Budget Request and Priorities

Dear Computer and Information Science and Engineering (CISE) Community,

Yesterday, the President delivered the Fiscal Year (FY) 2014 Budget Request to Congress. I am pleased to share with you the key figures from the President’s FY2014 budget request for the National Science Foundation and the CISE Directorate. The Administration is requesting a total of nearly $7.6 billion dollars for NSF, which is an increase of $593 million, or about 8.4 percent, over the FY 2012 NSF Enacted Level. The Request also includes an increase of $85 million, or 9.8 percent, over the FY 2012 Enacted Level for the CISE Directorate, for a total of $950 million. For more information on the NSF FY 2014 budget, see:

For more than six decades, NSF has had a profound impact on our Nation’s discovery and innovation ecosystem by funding transformative research that has pushed forward the frontiers of knowledge.  As the only Federal agency dedicated to the support of basic research and education in all fields of science and engineering, NSF enables discoveries across a broad spectrum of scientific inquiry. In its mission to promote progress in computer and information science and engineering research, education and infrastructure, CISE will continue to cast a wide net, letting the best ideas surface. We ask you — members of the CISE research, education, and infrastructure community — to send your most transformative ideas to one of CISE’s four divisions – Advanced Cyberinfrastructure (ACI), Computing and Communications Foundations (CCF), Computer and Network Systems (CNS), and Information and Intelligent Systems (IIS).

The CISE FY 2014 Request is shaped by investments in core research, education and infrastructure programs as well as investments in a cross-cutting portfolio that aligns closely with national priorities and societal challenges. In this message, I wish to emphasize four specific areas: 1) CISE foundational research; 2) cross-cutting areas of exploration; 3) advanced cyberinfrastructure; and 4) education and workforce development.

Expansions of CISE Foundational Research: I wish to take this opportunity to reaffirm CISE’s strong commitment to its core programs in all areas of computer and information science and engineering.  Specifically, I want to focus on two highly complementary foundational research programs launched last year — Core Techniques and Technologies for Advancing Big Data Science and Engineering (BIGDATA) and eXploiting Parallelism and Scalability (XPS). In partnership with all other NSF directorates, CISE is leading the BIGDATA program in its second year. The goal is to address fundamental big data challenges, whose solutions may have wide applicability across a broad range of science and engineering domains. In XPS, the goal is to support groundbreaking research leading to a new era of parallel computing. XPS seeks research re-evaluating, and possibly re-designing, the traditional computer hardware and software stack for today’s heterogeneous parallel and distributed systems and exploring new holistic approaches to parallelism and scalability.

Cross-cutting Investments led by CISE: CISE leads a number of cross-cutting programs, which catalyze foundational research and, in many cases, cross over multiple NSF directorates.  Secure and Trustworthy Cyberspace (SaTC) is a partnership with the Directorates for Education and Human Resources (EHR), Engineering (ENG), Mathematical and Physical Sciences (MPS), and Social, Behavioral, and Economic Sciences (SBE); it seeks to protect the Nation’s critical infrastructure, including the Internet, from a wide range of threats that challenge its security and reliability. The Cyber-Physical Systems (CPS) program (with ENG) aims to deeply integrate computation, communication, and control into physical systems and to engineer complex “smart” cyberphysical systems. All NSF directorates are participating in Cyber-enabled Sustainability Science and Engineering  (CyberSEES), which is a partnership with the Semiconductor Research Corporation (SRC); it aims to advance interdisciplinary research in which the science and engineering of sustainability are enabled by new advances in computing, and where computational innovation is grounded in the context of sustainability problems. Through programs such as the Innovation Corps (I-Corps), CISE will continue to foster public-private partnerships to accelerate transfer of knowledge from lab to practice to benefit society.

CISE is also actively engaging in several cross-agency initiatives and programs. For example, the National Robotics Initiative (NRI) is a partnership with three other agencies — NASA, NIH, and USDA – as well as three other NSF directorates — ENG, EHR, and SBE. The goal is to develop the next generation of collaborative robots that promise to enhance personal safety, health, and productivity. Smart and Connected Health is a newly formed partnership between NSF (including CISE, ENG, and SBE) and six institutes at the National Institutes of Health (NIH); it aims to accelerate the development and use of innovative approaches that would support the much-needed transformation of healthcare from reactive and hospital-centered to preventive, proactive, evidence-based, person-centered and focused on well-being rather than disease.

Advanced Cyberinfrastructure: Cyberinfrastructure has increasingly become a critical component of the R&D ecosystem.  Realizing the enormous potential of cyberinfrastructure requires a long-term, bold, sustainable, and comprehensive approach.  In FY 2014, CISE, in partnership with all NSF research directorates, will increase its investments in the Cyberinfrastructure Framework for 21st Century Science and Engineering (CIF21) programs. The goal is to develop and deploy comprehensive, integrated, sustainable, and secure cyberinfrastructure (CI), accelerating a new era in scientific discovery and engineering innovation, thereby transforming our ability to effectively address and solve the many complex problems facing science and society. NSF-wide investments include Data Infrastructure Building Blocks (DIBBs), BIGDATA,  Software Infrastructure for Sustained Innovation (SI2), and Computational and Data-Intensive Science and Engineering (CDS&E). 

With the launch of Stampede and Blue Waters, NSF continues to make significant investments in advanced cyberinfrastructure as well as in research and education networks, including the Campus Cyberinfrastructure – Network Infrastructure and Engineering (CC-NIE) Program and Global Environment for Network Innovations (GENI), a virtual laboratory for exploring future internets at scale.

Education and Workforce Development: In FY 2014, it is estimated that CISE will support approximately 20,800 people across the spectrum from undergraduate and graduate students to postdoctoral fellows and senior researchers. CISE reaffirms its commitment to education and workforce programs, including CAREER and Graduate Research Fellowships, which support early-career researchers and contribute to the development of future generations of scientists and engineers.  In collaboration with several other Directorates, including EHR and SBE, CISE will grow its investments on research in cyberlearning and online education, promising to integrate advances in technology with advances in what is known about how people learn. This is an important area of inter-disciplinary exploration with enormous potential to transform formal and informal education.

CISE continues its focus on STEM-C Partnerships (formerly, the Computing Education for the 21st Century (CE21) program) in order to increase the pool of students and teachers who develop and practice computational and data competencies in a variety of contexts and to prepare more students to pursue degrees in computing, computation, and data-intensive fields of study. 

As a field of inquiry, computer and information science and engineering has a rich intellectual agenda.  Foundational research seeds new programs that keep our community at the frontiers of knowledge and discovery. I invite you to work with us to ensure that our Nation remains at the forefront of advances in science and engineering research, education, and infrastructure.

Best regards,


Farnam Jahanian
Assistant Director for CISE
National Science Foundation


Propose workshops for STOC 2013

As in previous STOC/FOCS conferences, STOC 2013 will have a workshop and tutorial day. Moses Charikar and I are in charge of the program for this day, and are soliciting proposals for it. The deadline to propose is tomorrow, November 17th, but if you need a bit extra time, please email us and let us know.

FOCS 2012 workshops

On Saturday, October 20th, from 9am till 6pm, there will be three workshops as part of the FOCS 2012 conference:

See this page for more details.


FOCS 2012 workshops

STOC 2012 started a new experiment of a workshop and tutorial day in the beginning of the conference. The program looks fascinating and I hope many people attend.

FOCS 2012 will have also have such an event on Saturday, October 20. We (Boaz Barak and Avrim Blum) are looking for proposals for workshops to run on that day. So, if you want to organize a workshop that day, please do visit the link above and send us a proposal by June 20, 2012.

Hope everyone enjoys the STOC workshops and please do start thinking of ideas for great FOCS workshops!

New NSF solicitation on Big Data

A new NSF solicitation on Big Data was announced yesterday.  This program “aims to advance the core scientific and technological means of managing,  analyzing, visualizing, and extracting useful information from large, diverse, distributed and heterogeneous data sets.” Within TCS, some natural connections include efficient algorithms, machine learning, streaming and online algorithms, and privacy.

Deadlines: June 13 for “mid-scale” projects, July 11 for “small” projects (see solicitation for specifics).

Here is the announcement yesterday by Farnam Jahanian, head of CISE:

This afternoon at a White House event, the Administration unveiled a Big Data Research and Development Initiative, which creates enormous opportunities for extracting knowledge and insights from large and complex collections of digital data. The CISE community is well poised to become an active participant in this new initiative.

NSF Director, Dr. Subra Suresh, joined other federal science agency leaders to discuss cross-agency plans and announce new research efforts to address big data. NSF will direct its current efforts to develop new methods to derive knowledge from data; construct new infrastructure to manage, curate and serve data to communities; and forge new approaches for associated education and training.

The cornerstone of the announcements includes a joint NSF-NIH solicitation on foundational research for big data. The “Core Techniques and Technologies for Advancing Big Data Science & Engineering,” or “Big Data” ( aims to advance the core scientific and technological means of managing, analyzing, visualizing and extracting information from large, diverse, distributed, and heterogeneous data sets in order to accelerate progress in science and engineering research.  Specifically, it will fund research to develop and evaluate new algorithms, technologies, and tools for improved data management, data analytics, and e-science collaboration environments.

Welcome to the CATCS blog

This is the blog for the SIGACT Committee for the Advancement of Theoretical Computer Science (CATCS).  The aims of this blog and site are to:

  1. Inform the TCS community about funding opportunities that arise, as well as discuss tips, suggestions, and experiences related to funding and funding agencies.
  2. Provide information (nuggets, slides, descriptions, surveys) that members of the TCS community can use to help in explaining the excitement of TCS to the broader public.
  3. Enlist the help of the TCS community for matters vital to the community as a whole, for instance in identifying candidates for NSF program directors, etc.

This site is based on the theorymatters wiki initially created by Sanjeev Arora, Boaz Barak, and Luca Trevisan in 2005, and subsequently transferred to the oversight of the CATCS and maintained substantially by Salil Vadhan.  The porting of the wiki to a blog was done by Boaz Barak, Moses Charikar, and Luca Trevisan (many thanks to Boaz, Moses, and Luca for doing this!).

We hope you find this blog and site useful.  Feel free to contact committee members directly with questions or suggestions.

-Avrim Blum (CATCS chair)

Visioning Workshop

On May 17, 2008 (the day before STOC 2008 in Victoria, BC), there was a “visioning” workshop at the University of Washington in Seattle. The workshop was funded by the Computing Community Consortium, and supported by the SIGACT Committee for the Advancement of Theoretical Computer Science. The goals of the visioning workshop were to:

  • Identify broad research themes within theoretical computer science (TCS) that have potential for a major impact in the future, &
  • Distill these research directions into compelling “nuggets” that can quickly convey their importance to a layperson.

Get every new post delivered to your Inbox.

Join 36 other followers