New book on Probability

A new book announcement from Mor Harchol-Balter:

Dear Theory Friends, I am excited to announce that I just completed writing a new textbook, titled Introduction to Probability for Computing, published by Cambridge University Press, 2024.  This book is based on my “Probability and Computing” class at CMU.   It should be useful for teaching undergraduates and masters students.  This link includes a pdf for every chapter. 

The book is written in the usual student-friendly Question/Answer format that many of you have come to know from my earlier textbook: Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Thanks for taking a look!

          Mor

Wikipedia edit-a-thon at FOCS

FOCS’23 is hosting a Wikipedia edit-a-thon on Monday, Nov 6, 2023.

Let’s get together and create or edit Wikipedia pages for CS Theory entries. Both new and experienced Wiki editors are welcome to participate! 

Read more and sign up at https://sites.google.com/view/tcs-edit-a-thon.

– Divyarthi Mohan, Aviad Rubinstein, Ewin Tang, and Shuchi Chawla (organizers)

TCS Job Market profiles

Are you or your institution looking to hire a theoretician? Check out these job market profiles of TCS candidates. Feel free to share widely within your network. This information can also be found under the “TCS Job Market” tab in the menu above.

Candidates on the TCS job market: fill out this form to get your profile added to the list. We will review responses and add them to the list every 2-3 weeks.

ACM survey on math requirements for the CS major

The ACM/IEEE-CS/AAAI CS2023 Curricular Task Force is working on updating the undergraduate CS curriculum guidelines for the next decade. They have distributed a survey about the role of math in that curriculum, which is of direct interest to the TCS community. Please consider taking the survey so your opinion is heard!

From the Task Force:

———–

Dear educator,

What math should undergraduate Computer Science students know?

The CS2023 Task Force is collecting (and will share!) input from the community on this very important topic both as a useful “sense of the community” for everyone and, pertinent to our immediate goal, to shape our decennial curricular recommendations.

We invite you to fill out a survey: https://tinyurl.com/7zjbu7pr

As you fill out this survey, we ask you to reflect on:

• Discrete mathematics: student preparedness, topics covered, what’s missing?
• What should come beyond discrete mathematics, if anything?
• What do the new high-growth areas (AI, ML, quantum computing, data science) need by way of mathematical preparation?
• Do most CS jobs need much mathematics, and do current mathematical requirements pose a barrier to some populations of students?

Thank you in advance for taking the time to fill out the survey!

If you believe that other colleagues in your department can contribute, please forward the survey link to them.

Amruth Kumar and Rajendra Raj

On behalf of the of the ACM/IEEE-CS/AAAI CS2023 Curricular Task Force

NOTE: By participating, you agree that we may use your responses for this study; and that this data may be presented in aggregate form (with no personally identifying information) in articles or websites.

——–

Call for TCS Job Market profiles

CATCS is resuming the effort to collect and disseminate profiles of theory researchers who are going on the job market during the 2022-23 academic year, complementing the job postings collected under the Jobs tab.  The goals are to provide:

• a platform to job-seekers to advertise their credentials and
• an interface for institutions/individuals with open positions to find prospective candidates.

Candidates can fill out this form, which asks for basic information, graduation date (past or future), cv, bio, research summary, etc.

The responses will be reviewed and, if approved, edited and posted on Theory Matters starting on Oct 15, 2022. There is no deadline, but for responses received after Oct 15, please allow two weeks for review before your profile appears on the website. Responses received by Oct 15 will have summaries published in the following issue of SIGACT News (Dec’22 issue).

Women in TCS Profiles

Are you trying to form a committee or panel or invite speakers for a TCS event, but cannot find enough women? Look no further. This spreadsheet contains the profiles of 100+ women TCS researchers spanning many subareas of TCS; countries; universities and research institutions; and career stages.

The spreadsheet is password protected. The password is a case-sensitive five letter phrase that captures the most iconic (but as yet unsolved) problem in TCS.

The spreadsheet was made possible through the efforts of Yusu Wang and Kira Goldner. We have full permission of the participants to have their information shared publicly.

Would you like your information added to or corrected on the spreadsheet? If so, fill out this Google form. Any edits will be verified and posted to the spreadsheet within 3-4 weeks.

TheoryFest 2022: Registration now open and travel grant applications due soon!

Call for Participation 

54th ACM Symposium on Theory of Computing (STOC 2022) – Theory Fest 

June 20-24, 2022 

Rome, Italy 

The 54th ACM Symposium on Theory of Computing (STOC 2022) is sponsored by the ACM Special Interest Group on Algorithms and Computation Theory and will be held in Rome, Italy, Monday June 20 – Friday, June 24, 2022.

STOC 2022 – Theory Fest will feature technical talk sessions, 6 workshops with introductory tutorials, poster sessions, social events, and a special joint session with “Accademia Nazionale dei Lincei”, the oldest and most prestigious Italian academic institution, followed by a reception and a concert at the Academy historic site. 

Registration

STOC 2022 registration is available here.

Early registration deadline: April 30th. 

Student Travel Grants 

Information for student travel grant applications is available here. 

Application deadline: April 20th.

STOC 2022 is sponsored by Algorand, Amazon, Apple, Google, IOHK, Microsoft, Sapienza University of Rome. 

Call for Nominations: STOC Test of Time Award (Deadline: Apr 30)

The 2022 STOC Test of Time Award recognizes papers published in the Proceedings of the Annual ACM Symposium on Theory of Computing. This is the second year of this annual award. There are three awards, targeting the STOC conferences 10, 20, and 30 years prior to the year in which the award is given. While there is a preference for papers in the target years (and nominations from those years are encouraged), in each of these award categories it is also possible to nominate STOC conference papers published up to four conferences earlier than the targeted conference. Thus, the 2022 STOC Test of Time Awards will be for papers presented at the STOC conferences in 2008-2012, 1998-2002, and 1988-1992. The awards, which will be presented at STOC 2022, include a prize of US $500 per author as well as complimentary registration for all authors who attend the conference at which the award is given.

Nomination Procedure

Nominations should be sent to stoc22.tot.award@gmail.com with a subject line of “STOC Test of Time Award” no later than April 30, 2022. Nominations should contain an explanation of the impact of the nominated paper(s), including references to follow-on work. A nomination may be accompanied by up to three additional endorsement letters, which may be sent by the endorsers directly to the same email address with the same subject line. Self-nominations are disallowed. 

Selection

The winners will be selected by a committee appointed by the SIGACT Executive Committee. For 2022 the selection committee consists of Toniann Pitassi (Columbia), Satish Rao (Berkeley), Salil Vadhan (Harvard, chair), Avi Wigderson (Institute for Advanced Study). 

In selecting the Test of Time Award winners, the Committee will pay particular attention to long-term impact. This impact can come in many forms, including but not limited to:

1. Opening up a new area of research
2. Introducing new techniques
3. Solving a problem of lasting importance
4. Stimulating advances in other areas of computer science or in other disciplines.

The committee expects to select exactly one paper for each award. However, when circumstances justify it, up to three may be selected. The committee may consider papers that were not explicitly nominated and gather additional input from experts, but formal nominations are extremely helpful in the committee’s deliberations and strongly encouraged.

Call for nominations: Knuth Prize

Deadline: March 31, 2022.

The Donald E. Knuth Prize for outstanding contributions to the foundations of computer science is awarded for major research accomplishments and contributions to the foundations of computer science over an extended period of time. The Prize is awarded annually by the ACMSpecial Interest Group on Algorithms and Computation Theory (SIGACT) and the IEEETechnical Committee on the Mathematical Foundations of Computing (TCMF).

Nomination Procedure. Anyone in the Theoretical Computer Science community may nominate a candidate. To do so, please send nominations to knuth.prize.2022@gmail.com by March 31, 2022. The nomination should state the nominee’s name, summarize their contributions in one or two pages, provide a CV for the nominee or a pointer to the nominee’s web page, and give telephone and email contact information for the nominator. Any supporting letters from other members of the community (up to a limit of 5) should be included in the package that the nominator submits. Supporting letters should contain substantial information not in the nomination. Others may endorse the nomination simply by adding their names to the nomination letter. If you have nominated a candidate in past years, you can re-nominate the candidate by sending a message to that effect to the above email address. (You may revise the nominating materials if you so desire.)

Criteria for Selection. The winner is selected by a Prize Committee consisting of six people appointed by the SIGACT and TCMF Chairs, see below for the composition of the committee.

Previous nominations made or updated in the last 5 years will be considered. Older nominations must be updated for consideration. Note that the Knuth Prize is awarded to a single individual each year. Nominations of groups of researchers will not be considered.

In selecting the Knuth Prize winner, the Committee pays particular attention to a sustained record of high-impact, seminal contributions to the foundations of computer science. The selection may also be based partly on educational accomplishments and contributions such as fundamental textbooks and high-quality students. The award is not given for service to the theoretical computer science community, but service may be included in the citation for a winner if appropriate.

The 2022 prize committee consists of Harold Gabow (U. Colorado), Monika Henzinger (U. Vienna), Kurt Mehlhorn (Max Planck Institute), Dana Randall (Chair, Georgia Tech), Madhu Sudan (Harvard U.), and Andy Yao (Tsinghua U.).

Call for nominations: Godel Prize

Deadline for nominations extended to March 31st 2022.

https://www.sigact.org/prizes/g%C3%B6del.html

The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the European Association for Theoretical Computer Science (EATCS) and the Special Interest Group on Algorithms and Computation Theory of the Association for Computing Machinery (ACM SIGACT). This award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and the ACM Symposium on Theory of Computing (STOC). The thirtieth Gödel Prize will be awarded at the forty-ninth International Colloquium on Automata, Languages and Programming (ICALP), which will be hybrid, happening both physically and virtually. The physical meeting will take place in Paris, France, July 4–8 2022.

The Prize is named in honor of Kurt Gödel in recognition of his major contributions to mathematical logic and of his interest, discovered in a letter he wrote to John von Neumann shortly before von Neumann’s death, in what has become the famous “P versus NP” question. The Prize includes an award of USD 5,000.

Award Committee

The 2022 Award Committee consists of Samson Abramsky (Chair, University College London), Nikhil Bansal (University of Michigan), Irit Dinur (Weizmann Institute), Anca Muscholl (University of Bordeaux), Ronitt Rubinfeld (Massachusetts Institute of Technology), and David Zuckerman (University of Texas at Austin).

Eligibility

The 2022 Prize rules are given below and they supersede any different interpretation of the generic rule to be found on websites of both SIGACT and EATCS. Any research paper or series of papers by a single author or by a team of authors is deemed eligible if:

• The main results were not published (in either preliminary or final form) in a journal or conference proceedings before January 1, 2009.

• The paper was published in a recognized refereed journal no later than December 31, 2021.
The research work nominated for the award should be in the area of theoretical computer science. Nominations are encouraged from the broadest spectrum of the theoretical computer science community so as to ensure that potential award winning papers are not overlooked. The Award Committee shall have the ultimate authority to decide whether a particular paper is eligible for the Prize.

Nominations

Nominations for the award should be submitted by email to the Award Committee Chair: s.abramsky@ucl.ac.uk. Please make sure that the Subject line of all nominations and related messages begin with “Goedel Prize 2022”. To be considered, nominations for the 2022 Prize must be received by March 31, 2022.

A nomination package should include:

• A printable copy (or copies) of the journal paper(s) being nominated, together with a complete citation (or citations) thereof.

• A statement of the date(s) and venue(s) of the first conference or workshop publication(s) of the nominated work(s) or a statement that no such publication has occurred.

• A brief summary of the technical content of the paper(s) and a brief explanation of its significance.

• A support letter or letters signed by at least two members of the scientific community.
Additional support letters may also be received and are generally useful. The nominated paper(s) may be in any language. However, if a nominated publication is not in English, the nomination package must include an extended summary written in English.

Those intending to submit a nomination should contact the Award Committee Chair by email well in advance. The Chair will answer questions about eligibility, encourage coordination among different nominators for the same paper(s), and also accept informal proposals of potential nominees or tentative offers to prepare formal nominations. The committee maintains a database of past nominations for eligible papers, but fresh nominations for the same papers (especially if they highlight new evidence of impact) are always welcome.