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.
On Saturday, October 20th, from 9am till 6pm, there will be three workshops as part of the FOCS 2012 conference:
- Bayesian Mechanism Design. (Organizers: Constantinos Daskalakis and Jason Hartline)
- Randomized Numerical Linear Algebra: Theory and Practice. (Organizers: Christos Boutsidis, Petros Drineas, and Haim Avron)
- Data Structures (in memory of Mihai Patrascu) (Organizers: Alexandr Andoni, Erik Demaine, Piotr Indyk, and Mikkel Thorup)
See this page for more details.
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!
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.
The SIGACT committee has been holding biweekly conference calls. The following are the main problems it sees with TCS funding.
- 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).
- 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.
- 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.
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”).