Postdoc positions

A quick roundup of postdoc and faculty positions currently advertised at http://intractability.princeton.edu/jobs/ whose deadlines have not yet passed:

• Postdoc at KTH Royal Institute of Technology (deadline Jan 31)
• Postdoc at Cornell at the interface of networks, computing, and economics (deadline Jan 30)
• Simons postdoc at Carnegie Mellon (deadline Jan 31)
• Postdoc at LIAFA (Paris) (deadline Feb 1)
• Theory Postdoc at EPFL and Faculty positions at EPFL (no deadline stated)
• Postdoc in Theory/Practice of Differential Privacy at UPenn (no deadline stated)
• Postdoc in Cryptography at Tel-Aviv University (no deadline stated)
• Faculty positions at Northeastern University, Boston. (no deadline stated)
• Tenure-track Faculty Position at Purdue (Krannert School of Management) (no deadline stated)

Check http://intractability.princeton.edu/jobs/ for further updates.

Two announcements of potential interest to TCS students

1. Simons Graduate Fellowships in TCS: intended for students who have already produced significant results in TCS, this fellowship provides support for two years plus includes travel funds.  At most one application per university, so coordinate with your department chair. The Simons foundation anticipates making roughly 5 awards.  Deadline is May 1, 2012.  More information.

2. IAS summer school in Computation and Biology, July 9-20, 2012, will explore topics at the interface of theoretical computer science, statistical physics and quantitative biology.  Organizers are Bernard Chazelle, David Huse, and Stanislas Leibler. Information about application procedures and a program schedule can be found on the website: www.ias.edu/pitp.  The program is intended for both PhD students and postdocs.  Application deadline: March 1, 2012. Here is a publicity poster.

DARPA Young Faculty Award program

DARPA’s 2012 Young Faculty Award program  provides grants of $150,000/year for up to 2 years for junior faculty.  The announcement explicitly mentions a number of topic areas, of which the most relevant to TCS look to be:

• Quantum Science and Technology
• Mathematics (listing algorithms, geometric and topological methods, combinatorics, and graph theory and network analysis, among others)
• Computational and Quantitative Social, Decision, and Behavioral Sciences.

Submission deadline is 4pm ET January 19, 2012.

See http://www.darpa.mil/Opportunities/Universities/Young_Faculty.aspx and the grants.gov site for more information.

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)

NSF Program Director

NSF is looking for names for program directors in TCS (Algorithmic Foundations). If you have suggestions or are interested, send email to Avrim Blum who is helping to compile a list. For more information, See Bob Sloan’s essay The Joys of Being an NSF Program Director.

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.

2005 CATCS Report

The SIGACT committee has been holding biweekly conference calls. The following are the main problems it sees with TCS funding.

1. Low grant sizes in TCS, and too few of them. Grant sizes are now $70K/year.  A more viable grant size (paying for say summer salary+one student + computer/travel) will truly raise the effectiveness of researchers, allow grad training to continue, and lower various overheads for both researchers and NSF/CISE.  Researchers would write fewer proposals.
   In recent years there has also been a severe problem with very low numbers of funded proposals. In 2005 this was  ameliorated a bit since CISE made a special effort to raise the funding rate in TCS this year (both by increasing the TCS program budget and by reducing grant sizes). But the underlying fact is that the total budget of the TCS program is essentially unchanged since 1989 (which means it has greatly decreased in real dollars).
2. TCS’s position in the CISE hierarchy is too low which causes CISE leadership to miss its importance. CISE’s view of TCS (a sibling of numerical and symbolic computation, information theory, geometric computation, etc. in the TF cluster) seems out of accord with the view in most research  departments (viz., TCS as a major subdiscipline of CS on a par with AI, systems, software systems, etc.). Note that both AI and Networking and Systems are two levels higher than TCS in the CISE hierarchy.One recent statistic to support this: this spring six of the top 10 CS depts —Stanford, CMU, Cornell, UW, U. Wisc (Madison), UIUC– made offers to six different junior TCS people (five of which were accepted). This may greatly exceed the tally for any other leaf of the CISE tree, or the combined tally for the rest of the Theoretical Foundations Cluster.
3. Apart from the dedicated TCS program, few NSF programs support long-term, basic research. There is a pressing need for new NSF initiatives that support long-term, basic research  and which welcome TCS proposals. The TCS community also needs to be proactive too. Whenever NSF proposes new crosscutting initiatives –e.g., the new networking initiative– the TCS community needs to help delineate ways in which it can contribute.

2004 Proposal to increase TCS funding for Theoretical Computer Science

INTRODUCTION AND SUMMARY

As computer science enters an era of new challenges and multidisciplinary opportunities, there is a pressing need for new approaches, new conceptual models, and unconventional ideas. Theoretical computer science (TCS) has a proven track record in providing all of these.  TCS innovations such as analysis of algorithms, NP-completeness, complexity-based cryptography, use of probabilistic choices in algorithms, etc., are mainstays of CS research and education and one result is the growing popularity of quantitative reasoning and formal models in all of CS. In the past decade, TCS has invented new sub-disciplines (quantum computing), contributed new paradigms for emerging areas (web-search, internet content distribution, data-mining, computational biology etc.), and made important breakthroughs in a continuing study of intrinsic complexity, NP-completeness, randomness, efficient algorithms, networks, etc. Its long-term focus is at the root of its high impact –scientific, conceptual— and this has benefited the strategic national interest. Finally, TCS has also had considerable commercial impact: several IT and Biotech companies –Google, Amazon, Celera Genomics, Akamai, Verity, Digital Fountain, etc.—rely crucially on good algorithms originating from TCS. In many cases their chief scientists were also TCS researchers (at Amazon, the title is “Chief Algorithms Officer”).