STOC 2020 slack channel open (from Madhur Tulsiani)

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)

STOC 2020 information (guest post by Madhur Tulsiani)

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)

TCS visioning workshop

[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.

ITC 2020 program is out

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

Theory of Machine Learning summer seminar

[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:

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

Liberation from grades

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 🙂 )

Resources for the upcoming job market crunch

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.

Lessons from COVID-19: What works online and what doesn’t

(I am now on Twitter , so you can follow this blog there too if you prefer it. –Boaz)

Between Zoom meetings and deadlines, I thought I’d jot down a few of my impressions so far on what lessons we can draw from this period on how well research and education can work online. I’ve had a few surprises in both directions – things that worked better than I would have expected, and aspects that were more problematic than I realized. These are personal impressions – please do comment on your own experiences.

As a rule of thumb, the interactions that most successfully replicate online are those that are relatively short and focused (an hour or so – e.g., a focused research meeting, seminar talk, or a lecture in a course). Other interactions (e.g., faculty meetings) are also fairly easily to port online, perhaps because the original wasn’t that great to begin with.

The things that are harder to replicate are sustained interactions over longer periods. These include more extended and less directed research collaborations, informal workshops, as well as support for students outside lectures in education.

Works well: Research seminars

I’ve been pleasantly surprised by how effective research seminars such as our machine learning theory seminar are over Zoom. In particular these were no less interactive than physical seminars – in fact people are offten more comfortable asking questions on chat than they would during in-person seminars. I hope such seminars become common practice even after this period ends- flying a speaker across the country or the world to give an hour talk doesn’t makes much sense given that there is a perfectly satisfactory alternative.

Works well: Lectures

This term I am teaching cryptography, and online lectures on Zoom have gone surprisingly well (after working out some technical issues). Students participate on chat and ask questions, and seem to be following the lecture quite well. The important caveat is that lectures only work well for the students that attend and can follow them. For students who need extra support, it’s become much harder to access it. It’s also much easier for students to (literally) “fall off the screen” and fall behind in a course, which brings me to the next point.

Works less well: Support outside lectures

Lectures are just one component of a course. Most of students’ learning occurs outside the classroom, where students meet together and work on problem sets, or discuss course material. These interactions between students (both related and unrelated to course) are where much of their intellectual growth happens.

All these interactions are greatly diminished online, and I did not yet see a good alternative. I’ve seen reduced attendance in office hours and sections, and reports are that students find it much harder to have the sort of chance discussions and opportunities to find study partners that they value so much. If anything, this experience had made me less positive about the possibility of online education replacing physical colleges (though there are interesting hybrid models, where the students are co-located but lecturers are online).

Works less well: unstructured research collaborations

A focused meeting reporting on results or deciding on work allocation works pretty well over Zoom. So far it seems that extended brainstorming meetings, such as talking to someone over several hours in a coffeeshop, are much harder to replicate. In particular, a good part of such meetings is often spent with people staring in silence into their notebooks. As I wrote, mutual silence seems to be very hard to do over Zoom.

Generally, informal week-long workshops, where much time is devoted to unstructured discussions, are ones that are most important to hold in person, and are hard (or maybe impossible) to replicate online. I have still not attended an online conference, but I suspect that these aspects of the conference would also be the ones hardest to replicate.

Works well: faculty meetings

I’ve always found it hard to bring a laptop to a faculty meeting and get work done, while listening with one ear to what’s going on. This is so much easier over Zoom 🙂

Summer School on Statistical Physics and Machine Learning

Gerard Ben Arous, Surya Ganguli, Florent Krzakala and Lenka Zdeborova are organizing a summer school on statistical physics of machine learning on August 2-28, 2020 in Les Houches, France. If you don’t know Les Houches, it apparently looks like this:

They are looking for applications from students, postdocs, and young researchers in physics & math, as well computer scientists. While I am biased (I will be lecturing there too) I think the combination of lecturers, speakers, and audience members will yield a very unique opportunity for interaction across communities, and strongly encourage theoretical computer scientists to apply (which you can from the website). Let me also use this opportunity to remind people again of Tselil Schramm’s blog post where she collected some of the lecture notes from the seminar we ran on physics & computation.

More information about the summer school:

The “Les Houches school of physics”, situated close to Chamonix and the Mont Blanc in the French Alps, has a long history of forming generations of young researchers on the frontiers of their fields. Our school is aimed primarily at the growing audience of theoretical physicists and applied mathematicians interested in machine learning and high-dimensional data analysis, as well as to colleagues from other fields interested in this interface. [my emphasis –Boaz] We will cover basics and frontiers of high-dimensional statistics, machine learning, the theory of computing and learning, and probability theory. We will focus in particular on methods of statistical physics and their results in the context of current questions and theories related to machine learning and neural networks. The school will also cover examples of applications of machine learning methods in physics research, as well as other emerging applications of wide interest. Open questions and directions will be presented as well.

Students, postdocs and young researchers interested to participate in the event are invited to apply on the website http://leshouches2020.krzakala.org/ before March 15, 2020. The capacity of the school is limited, and due to this constraint participants will be selected from the applicants and participants will be required to attend the whole event.

Lecturers:

  • Boaz Barak (Harvard): Computational hardness perspectives
  • Giulio Biroli (ENS, Paris): High-dimensional dynamics
  • Michael Jordan (UC Berkeley): Optimization, diffusion & economics
  • Marc Mézard (ENS, Paris): Message-Passing algorithms
  • Yann LeCun (Facebook AI, NYU). Challenges and directions in machine learning
  • Remi Monasson (ENS, Paris): Statistical physics or learning in neural networks
  • Andrea Montanari (Stanford): High-dimensional statistics & neural networks
  • Maria Schuld (Univ. KwaZulu Natal & Xanadu): Quantum machine learning
  • Haim Sompolinsky (Harvard & Hebrew Univ.): Statistical mechanics of deep neural networks
  • Nathan Srebro (TTI-Chicago): Optimization and implicit regularisation
  • Miles Stoudenmire (Flatiron, NYC): Tensor network methods
  • Pierre Vandergheynst (EPFL, Lausanne): Graph signal processing & neural networks

Invited Speakers (to be completed):

  • Christian Borgs (UC Berkeley)
  • Jennifer Chayes (UC Berkeley)
  • Shirley Ho (Flatiron NYC)
  • Levent Sagun (Facebook AI)