New theory jobs website

The CATCS setup a new website to post information on positions such as postdoc, faculty, teaching fellows for theoretical computer scientists, the website is (this replaces the old webpage at the center for Computational Intractability that was hacked over the summer). It is rather rudimentary, but hopefully it still gets the job done, and it is connected to the Theory of Computing Blog Aggregator.

I encourage people to use this to post information about availability for academic positions. I think this should be particularly useful for postdoc positions. I think oftentimes graduating students are not aware of which universities have postdoc positions, especially since in most institutions availability tends to change from year to year. So, if you are looking for postdocs in theoretical CS, please do post that information on the website. Posts should be short but describe the duration of the position and the deadline to apply, together with a link that points out to additional information.

Salil, Moses and Boaz

STOC grant-writing panel recap

Moses Charikar and I organized a grant writing panel at STOC 2013. The panel was well attended and I think (or at least hope) provided useful information to the audience, thanks to our great panelists: Joan FeigenbaumPiotr IndykBala Kalyanasundaram, and Salil Vadhan.

Panelists had many insights on aspects of achieving funding, some highlights that stuck in my memory:

1) There are many funding opportunities out there apart from the “obvious” sources (i.e., NSF theoretical foundations) – check those out.  Don’t be afraid to contact people with lots of funding experience for advice or even to ask (if appropriate) to join future large projects.

2) That said, you should always make sure that you actually want to do the proposed research, and shouldn’t join a project you don’t care about just for the funding. This is particularly true for large projects or funding from “mission oriented” (as opposed to “basic science oriented”) agencies, where the funding often comes with plenty of strings attached.

3) If you work in theoretical CS in the U.S., you should definitely consider applying  for grants from the Computing and Communication Foundations division (and in particular the Algorithmic Foundations program). Grants have gotten bigger and competition smaller than people may remember from past years, and it’s definitely worth the trouble.

4) NSF program officers are your friends, they are more than happy to talk to you, and can often help you find the right program for your proposal.

5) Especially (but not only) in NSF CCF grants, people understand that theory research is unpredictable. If you’ve done good research in the area, nobody will blame you for not solving the particular problems you set out in your proposal. That said, the proposal should have a mix of problems of various difficulty and “speculativeness”.  If the proposal just lists some important open problem without suggesting that you have any new approach to solve them, it’s unlikely to get funded.

6) Collaborative projects are much easier to manage when it’s 2-3 PI’s (primary investigators) who are close collaborators than project involving a large number (say 7 or more) PI’s.

7) Writing a proposal involves making choices – how big the team, one area or interdisciplinary, contain everything you want to work on or leave topics for future proposals, apply to NSF or to more  “mission oriented” sources of funding. All those choices are non-trivial and have pros and cons, which you’d do well to consider carefully and consult with people who’s had experience.

8) Proposals (especially but not only large multidisciplinary ones) often don’t get funded in the first attempt. People said they found that the proposal became better and the team more cohesive in future iterations.

While some of the advice is universal, we did not have a panelist with specific expertise in funding outside the U.S. We hope to have some guest posts on this blog about this topic in the future, though in the meantime we would welcome tips about resources on grant writing in the comments.

One such resource that could be very useful was collected by Moses Charikar and Piotr Indyk – this is a collection of  successful NSF CAREER proposals  along  with retrospective comments by the authors. We are truly grateful to these researchers for making available this valuable resource to anyone that is considering submitting a grant proposal. Salil Vadhan also made available his multi-disciplinary grant proposal.

People might also find useful  Joan Feigenbaum’s presentation from the event.

Advice from Sanjeev Arora on writing grant proposals

In advance of the grant writing panel to be held this Saturday 8pm at STOC, Sanjeev Arora put together some very useful tips for people writing grant proposals. These tips as well as others will be discussed on Saturday by our panelists: Joan Feigenbaum, Piotr IndykBala Kalyanasundaram, and Salil Vadhan.

The panel will be moderated by Moses Charikar and me.

Advice on writing a research grant proposal.

Sanjeev Arora

Professor of Computer Science,
Princeton University

April 2013

  1. Approach it with a positive attitude: it is a necessary part of your job along with writing papers, giving good talks, following the research in your field, PhD advising etc. Remember: the better you get at it, the less frequently you need to do it.What I like about the current peer review system (at least in computer science) is that it allows young researchers with good, imaginative proposals to get funded, leaving more senior researchers in the dust.  I’ve seen it happen a lot.

    Another positive aspect for me is that this system forces me to evaluate myself every couple of years, and figure out what I should do next.

  2. Don’t forget the basics: a grant proposal has to identify a problem or set of problems; outline what is lacking in current approaches; and sketch how you will address these deficiencies and solve the problem. Along the way it should argue that you are the right person to do this work. Usually it’s best to weave your past track record subtly into the entire narrative instead of relegating it to a separate section at the end. Keep in mind that reviewers are asked to judge the proposal based upon the research that is being proposed, and not merely upon the past track record of the PI. (Of course, in practice reviewers rely a lot upon the past track record.)Also, it is useful —for proposer as well as the reviewer— if the proposal states concrete “project goals” sprinkled throughout the writeup. (Create a separate latex environment for this.) Instead of saying something wishy washy like “We plan to further explore area x”  say: “Project Goal 4: Use technique blah to design a polynomial time algorithm for problem foo.” Ideally this concrete goal should come after a paragraph or two where you have sketched the prior art, and explained the importance of this goal.

    Avoid the temptation to cut and paste text verbatim from your recent papers (or even worse, actual theorems riddled with messy parameters). A research proposal is more like an expository article geared to a broad audience —at least the couple of opening sections.

  3. In addition to getting the basics right, you should pay attention to the other stuff and do your groundwork. Carefully read the program solicitation, and if possible, talk to NSF program officers.  They attend conferences, answer emails, take phone calls, etc.  Obviously, they will be most candid in face to face conversations. (Keep your conversation short and to the point, though.) They can give you a sense of funding trends and current buzzwords at NSF, saying things like: “There are three buzzwords in the program solicitation but the last one is more important to us than the first two.” Or “Your work seems relevant to area X and there is a program in area X that is looking to fund foundational work.”  Colleagues can also be useful in this process.Such groundwork is especially useful for a new funding program that is in the pipeline. If you know about it in advance, you could have a proposal idea ready —or collaborators lined up—when the solicitation comes out. In general it is much easier to get funded in the first year or two of a new program, before it gets overwhelmed by “proposal pressure.”
  4. While writing your proposal, be sure to address the buzzwords you have discovered as part of (3). I don’t mean to make all this sound shallow or dishonest. Obviously, if your work has no implication for national security, you shouldn’t claim any. But if there happen to be some, do point them out. (Don’t exaggerate; reviewers are smart.) Another example: if you enjoy working with high school students and have an excellent track record in it, consider making that a component of your proposal. There are no fixed rules, and anything that helps you stand out from the crowd is fine and good.Put yourself in the reviewers’ shoes as you  write. They have limited time and have usually received highly specific instructions from NSF (usually including the buzzwords from the solicitation).  Make it easy for them to evaluate your proposal. Use short sections with descriptive titles, especially “Broader Impact”, “Postdoc mentoring plan” etc. that NSF wants them to specifically comment on. Use short, declarative sentences that are easy to parse.
  5. Conversely, if you are ever asked to serve on a selection panel, take careful notes on what worked in the proposals you reviewed and what didn’t. What aspects did the panel dislike? Of course, the quality of research is the most important aspect. But panels can be harsh on good researchers who clearly didn’t put in the time in crafting a good proposal, or who had obviously not read the solicitation carefully.
  6. Ask colleagues for advice as well as examples of their successful proposals. (Do it indirectly so you don’t put them on the spot. Most people are happy to help.) Ask colleagues who are not in your subarea as well. I find it very stimulating to read a well-crafted proposal not in my research area.
  7. Work out a writing schedule that works for you. I like to do a 1-page sketch to collect my thoughts and then modify it as I ponder it for several weeks. But then I do the actual writing fairly close to the deadline when I am more focused and efficient. If you plan to seek feedback on your draft, allow time for that.


Crosscutting solicitations are often judged by panels composed of people from different specialities. So write appropriately. Suppose you wish to work on theory problems arising in computer systems. Be sure to read some successful systems proposals and learn what aspects are important to systems reviewers. Talk to systems colleagues and learn a bit of their lingo. A day or two of such legwork will really pay off, and also improve your research.

Most panelists will not know your past record, and it has to come through clearly in the proposal.

The “groundwork” aspect described earlier (talking to program officers, etc.) is  very important for crosscutting program. Some program officers will even go to the trouble of listening to your proposal idea and give you valuable feedback. Sometimes they will give you feedback on a rejected proposal and suggest changes that could allow it to succeed in future.

Things like broader impact, training of underrepresented groups, etc. can be very important.  Pay attention to the solicitation’s “buzzwords.” All of this advice is is especially relevant for larger projects. Again, I don’t mean to advocate any dishonesty; just keep those aspects in your mind.

Often crosscutting proposals involve collaboration. The proposal usually should contain contributions from all team members, but one individual should take charge to make the proposal read well. Panels look for the following: Does this collaborative team make sense? How likely is it that these people will actually work together? Have they collaborated before? If your team involves people in different geographical locations, you need to sketch out a plan for how this collaboration will happen: regular meetings, joint postdocs, whatever. (It is wise to give such a plan even if all people are in one place. Sometimes solicitations will require such plans.) Also give a rationale for the team’s composition. (“Doing such a project calls for a mix of skills x, y, z. On our team we have skills x, y, z.”) Ideally do this mental exercise sufficiently ahead of the deadline so you can seek additional collaborators if you realize your team needs to be fleshed out.

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!

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


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 ideasTheoretical 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-miningcomputational 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”).

[Read more…]