Windows On Theory

I originally planned this summer to finish the work on my Introduction to Theoretical Computer Science book, and in particular write the two missing chapters on space complexity and interactive proof systems. Needless to say, this summer did not go as planned and I won’t be able to write these chapters. However, I still intend to go over the existing chapters, fixing typos, adding examples, exercises, and generally making it friendlier to beginning undergraduate students.

Toward this end, I would be grateful for people posting bugs, typos, and suggestions as GitHub issues (I currently have 267 closed and 14 open issues which I hope to get to soon). Of course, if you are technically inclined and there’s a simple local fix, you can also make a pull request.

Aside from these fixes, I am making two more “global” changes to the book. First, I am adding a “non mathy overview” for each chapter. While some students got a lot from reading the book prior to lectures, others were intimidated by the mathematical notation, and so I hope this more gentle introduction will be helpful. I am also adding more examples & solved exercises toward this end.

Another change is that I now follow the more traditional way of presenting deterministic finite automata before Turing machines – DFAs are still optional and can be skipped without missing anything, but some instructors find them as a good introduction to Turing Machines. Thus the order of presentation of materials in the book is roughly as follows:

1. Introduction, representing objects as strings – Representing numbers, lists, etc. Specifying computational tasks as functions mapping binary strings to binary strings, Cantor’s theorem.
2. Finite functions and Boolean circuits – Every function can be computed by some circuit, circuits as straightline programs, representing circuits as strings, universal circuit evaluator, counting lower bound.
3. Computing on unbounded inputs – DFAs (optional), Turing Machines, equivalence between Turing machines, RAM machines and programming languages, λ calculus (optional), cellular automata (optional)
4. Uncomputability – Universal Turing machine, Halting problem, reductions, Rice’s Theorem. Optional: Gödel’s incompleteness theorem, uncomputability of quantified arithmetic statements, context free grammars.
5. Efficient computation – Modeling running time, time hierarchy theorem, P and EXP
6. NP and NP completeness – Polynomial-time reductions, Cook-Levin Theorem (using circuits), definition of NP using “proof system”/”verifying algorithms” (no non-deterministic TMs), NP completeness, consequences of P=NP: search to decision, optimal machine learning, etc..
7. Randomized computation: Worst-case randomized computation, defining BPP, Sipser-Gács, does BPP=P? (a little on derandomization)
8. Cryptography: One time pad, necessity of long keys for information theoretic crypto, pseudorandom generators and stream ciphers, taste of public key and “magic” (ZKP, FHE, MPC)
9. Quantum computing: Some quantum mechanics background – double slit experiment, Bell’s inequality. Modeling quantum computation. Bird’s eye view of Shor’s algorithm and quantum Fourier transform.

Going directly from undergraduate to Ph.D can be a good idea for many students interested in research, but it’s not the only route or the best choice for everyone.

As I wrote before, for students that discovered their interest in theoretical CS late in their undergrad, or perhaps after they graduated, a research Masters, can be a great option. This is particularly the case if the program is funded (i.e., students get a stipend and don’t need to pay tuition). Such programs are not common in the U.S., but there are some excellent choices around the world.

Since (as far as I know) there is no single source listing such programs, I thought a crowdsourced Google spreadsheet might be useful and so created one here: http://tiny.cc/tcsmasters

If you know of more places, please fill out this form: https://forms.gle/qfnbEZYYYDtFCDpx9

Madhur writes:

Thanks to all who participated in STOC 2020! Since the discussions on some of the topics from the business meeting, on SafeToC, and  on the papers/workshops are still ongoing, we will keep the Slack workspace open till July 31st (instead of just one week after the conference, as announced earlier). Also, if any members of the community are interested in joining the discussions, they are welcome to email us (stoc2020@ttic.edu) and we can send them an invitation to join the workspace.

Of course the organizers may not always be able to quickly respond to help messages during the next month. However, all members are welcome to participate in discussions, create new topics or channels as needed, and use the workspace as they prefer.

TheoryFest organization team (stoc2020@ttic.edu)

Dear fellow theorists,

As you already know, STOC 2020 this year will be a virtual conference. If you are interested in attending the conference, but haven’t registered yet, please do so soon (students: $25, regular: $50). This will help us ensure we have capacity for various online events. 

Upon registration, you should receive a confirmation email from CVENT, also containing access information for various conference events. Also, if you are a student looking to register for STOC but the cost is a burden, please email us at stoc2020@ttic.edu.

How will the conference work?

• Videos: The videos for all conference talks are now available on YouTube, and can be accessed through the links in the conference program. Registration is not required to view the talks on Youtube.

• Slack: The conference has a Slack workspace, with one channel for every paper and workshop, and additional channels for information, announcements, social events, help, etc. The invitations for the Slack workspace will be sent to registered participants. Authors are also encouraged to monitor the channels for their papers. All access information for the conference will also be available here. The workspace is currently active, and will remain active for at least one week after the conference.

• Zoom sessions: The conference will feature Zoom sessions with short presentations by the speakers. The total time for each paper is 10 minutes. Given that participants have access to the full talks by the speakers on Youtube, these can be thought of as being analogues of poster sessions. The workshops will also be held as separate sessions. The links for the Zoom sessions are available via information in the registration confirmation email.

• Social events: The conference will include junior/senior “lunches”, breakout tables for impromptu and scheduled hangouts, and a group event using gather.town. The timings for the events can be found in the conference program. Sign-up links for various events will be sent to all registered participants – please do sign-up soon!

See you all at (virtual) STOC 2020. Please do let us know if you have any questions or suggestions.

TheoryFest organization team

(stoc2020@ttic.edu)

[From Jelani Nelson and David Woodruff. This workshop can be very important to ensure TCS is represented in what is likely to be a difficult funding environment in coming years. –Boaz ]

The CATCS will be hosting a virtual “Visioning Workshop” the week of July 20 in order to identify broad research themes within theoretical computer science (TCS) that have potential for a major impact in the future. The goals are similar to the workshop of the same name in 2008: to package these themes in a way that can be consumed by the general public, which we would deliver primarily to the Computing Community Consortium and others (e.g. funding agencies) to help them advocate for TCS.

While participation in the workshop is primarily through invitation, we have a few slots available for the broader community. If you are interested in participating, please see details of the application process below. The workshop will be organized according to area-wise breakout groups. Each breakout group will have 1-2 leads. Breakout groups will meet for 4-5 hours spread across several days and will be tasked with brainstorming ideas and preparing materials related to their topic. Leads are further expected to participate in plenary sessions held on Monday July 20 and Friday July 24 (4-5 hrs of additional time) where these materials will be discussed.

If you are interested in participating in the workshop, please fill out this Google form by Monday June 15 ( https://forms.gle/cdCTsLfUs56CDhKS9 ). On this form, applicants are asked to contribute one or two major results in the last 10 years whose significance can be explained in layperson terms, and one or two major challenges for theory whose significance can be explained in layperson terms. [The results need not and generally will not be your own. They just should be easy-to-explain major results in your research area–Boaz] These descriptions can be very brief. We will just use them to select participants and create breakout groups.

Guest post by Benny Applebaum

The ITC 2020 program is out, and this newborn looks healthy and strong! The program contains exciting new works in the area of Information-Theoretic Cryptography, confirming the importance of this new venue.

The PC, chaired by Daniel Wichs, also chose an amazing sequence of invited talks by Dachman-Soled, Natarajan, Jafar, Kol, Raz, and Vaikuntanathan, so this can also be a good opportunity to hear about the big recent developments in the area.

The conference will be virtual this year. Participation is free but requires registration. We hope to see many of you there

[Note: While I and many others are fortunate to be able to go on with our work, deadlines, and (as mentioned in this post) seminars, this is not the case for many in the U.S. following yet another demonstration that black lives don’t matter as much as they should in this country. I would like to relay Rediet Abebe’s call to support local organizations. As Rediet says “These problems have been and will be here for a very long time. We’re not solving racism this month.”. –Boaz]

For the last year, I have been co organizing a theory of machine learning seminar at Harvard. Following the format of our prior Harvard/MSR/MIT theory reading group, these have been extended blackboard talks with plenty of audience interaction.

Following COVID-19, the last three talks in the semester (by Moritz Hardt, Zico Kolter, and Anima Anandkumar) were given virtually. Frankly, I was at first unsure whether these seminars can work in the virtual format but was pleasantly surprised. Talks have been very interactive, with plenty of audience participation in the chat channel. In fact, the virtual format has some advantages over physical talks. Sometimes a question will be asked and answered by a co-author over chat, without the speaker needing to interrupt the talk.

Since the seminars were so successful, we decided to continue holding them over the summer. We have an exciting line up of confirmed speakers, and more will come soon. See our webpage for more details, which also contains a google calendar and a mailing list you can sign up for to get the Zoom link.

Confirmed speakers so far include:

• Jascha Sohl-Dickstein – June 11
• Behnam Neyshabur – June 18
• Alex Dimakis – July 9
• Nadav Cohen – August 6
• Maithra Raghu – date tbd
• Hanie Sedghi – date tbd

More should be confirmed soon – join our mailing list to get updates.

This semester, like many other universities, Harvard switched to a pass/fail grade model. (In typical Harvard style, we give them different names – “Emergency Satisfactory” and “Emergency Unsatisfactory” – but that doesn’t matter much).

One unexpected but happy consequence of this policy is that even though I already submitted the grades for my crypto course, I can now take the time and send students detailed feedback on their final projects. Typically, both students and faculty tend to be focused on the “bottom line” of exams or papers – what is the final grade. The comments are viewed as of marginal importance and only serve to justify why points have been deducted.

Now that there is no grade, I am actually giving many more comments on the write ups, trying to focus on giving students feedback on writing and presentation that will be useful for them later on. I benefited immensely from the extensive comments on my writing that I received from my advisor Oded Goldreich. While I will never match Oded’s thoroughness and dedication, I try to at least provide some of this to my students (though unlike Oded, I use blue and not red ink, and also do not intersperse the comments with Hebrew curses for emphasis 🙂 )

[Hat tip: Aaron Roth]

The inaugural conference on the foundations of responsible computing will take place in less than two weeks (June 1-2). Registration is FREE but you need to register by May 28.

The program looks fantastic, and includes keynotes by Adrian Weller, Rakesh Vohra, Patricia Williams, and Jon Kleinberg, as well as a set of (very interesting, judging by the titles) contributed talks.

Aside from its devastating death toll, the COVID-19 pandemic has had severe economic implications. The impact on universities is particularly substantial, including disruptions to our physical campuses and student residences, as well as to the sources of income for private and public universities such as endowments and state budgets.

All this means that the academic job market is likely going to be tough in the near future, and computer science will not be immune. During the last recession, the CCC started a computing innovation fellows program which was very successful, and I hope that something similar will occur this time as well. But it won’t be enough.

If you are aware of any postdoc positions (or better yet, can create one) please do make sure to post it on the CS theory job board. If you know of any teaching position that could potentially be applicable for theorists, please post it there too. This crisis can also be an opportunity to get fantastic people for such positions. If you have any ideas on how we as the theoretical CS community can support graduating students and postdocs, please do share these in the comments or on Twitter.

If anything, this crisis has taught us that the world needs more science, not less. Moreover, computer science has been and will continue to be a crucial component in fighting this epidemic, including not just modeling but also tracing applications using crypto, load balancing that ensures the Internet doesn’t crush, and more. I am thus hopeful that within a couple of years, the academic job market for theoretical computer scientists will recover. However we should try to do all we can to help our junior colleagues get through this period.