Windows On Theory

When I was in grad school a common advice for beginning grad students was to leaf through the (paper) STOC or FOCS proceedings to see papers that you are interested in. This is still a decent advice (and requires less physical strength these days 🙂 ) but papers are not always the best source for people starting out. More often than we’d like to, the author of the 10th paper on a topic writes it to the audience of people that read (in fact probably wrote) the previous 9 papers.

Talks often do a better job of giving an overview of the field, and one great resource is the videos from the Simons Institute. If you want to get more in-depth information about a particular topic, it’s hard to beat the extended surveys in Foundations and Trends in TCS, as well as the related areas such as Machine Learning and Information Theory.

But if you are not yet sure what topic you’re interested in, or perhaps not even sure if you want to go to grad school, but you just know that you are interested in theory, there is now a new great resource. As I learned from Twitter, Ryan O’Donnell has just finished his TCS Toolkit course. All 99(!) lectures are on YouTube.

The topics are the following (these links are to the handwritten notes, for the lecture videos see YouTube channel):

1.   Course Overview, and How to TCS

2.   Basic Asymptotics

3.   Factorials and Binomial Coefficients

4.   Central Limit Theorem

5.   Chernoff Bounds

6.   Computational Models

7.   Fast Multiplication with the DFT

8.   Analysis of Boolean Functions

9.   Quantum Computation

10.   Fields and Polynomials

11.   Error-Correcting Codes

12.   Derandomization

13.   Spectral Graph Theory I

14.   Spectral Graph Theory II

15.   Spectral Graph Theory III

15.1.   Cheeger’s Inequality (Spectral Graph Theory bonus)

16.   Expander Graphs

17.   Linear Programming I

18.   Linear Programming II

19.   The Ellipsoid Algorithm

20.   CSPs and Approximation

21.   LP Hierarchies and Proof Systems

22.   Treewidth

23.   Communication Complexity

24.   Information Theory

25.   Cryptography

26.   Hardness Assumptions

27.   The PCP Theorem

p.s. For giving a high level taste of theory to beginning undergraduates, a great resource is Aaronson’s Quantum Computing since Democritus or Wigderson’s Math and Computation if they’re more math inclined.

[Guest post by Valerie King. TL;DR SOSA 21 will take place jointly with SODA 21. To submit register by August 12, paper deadline August 19.]

Call for Papers: Registration deadline August 12, 2020

3rd SIAM Symposium on Simplicity in Algorithms  (SOSA)
January 11-12, 2021
Alexandria, Virginia, U.S.
(Held jointly with SODA 2021)

Symposium on Simplicity in Algorithms (SOSA) is a conference in theoretical computer science dedicated to advancing algorithms research by promoting simplicity and elegance in the design and analysis of algorithms. The benefits of simplicity are manifold: simpler algorithms manifest a better understanding of the problem at hand; they are more likely to be implemented and trusted by practitioners; they can serve as benchmarks, as an initialization step, or as the basis for a “state of the art” algorithm;  they are more easily taught and are more likely to be included in algorithms textbooks; and they attract a broader set of researchers to difficult algorithmic problems.

Papers in all areas of algorithms research are sought.  An ideal submission will advance our understanding of an algorithmic problem by, for example, introducing a simpler algorithm, presenting a simpler analysis of an existing algorithm, or offering insights that generally simplify our understanding of important algorithms or computational problems.

We are especially interested in papers that make material more accessible to a wider audience, such as undergraduates, or for more specialized topics, general algorithms researchers.

Submissions should contain novel ideas or attractive insights, but they are not expected to prove novel theorems. That is, the results themselves can be known, but their presentation must be new. Conference website is https://www.siam.org/conferences/cm/conference/sosa21

Program Committee
Aaron Bernstein, Rutgers University, U.S.
Allan Borodin, University of Toronto, Canada
Timothy Chan, University of Illinois at Urbana-Champaign, U.S.
Edith Cohen, Google Research, U.S. and Tel Aviv University, Israel
Vincent Cohen-Addad, Google Research, Zürich, Switzerland
Sanjoy Dasgupta, University of California, San Diego, U.S.
Michael Elkin, Ben-Gurion University of the Negev, Israel
Funda Ergun, NSF and University of Indiana, Bloomington, U.S.
Mike Fellows, University of Bergen, Norway
Arnold Filtser, Columbia University, U.S.
Kasper Green Larsen,  Aarhus University, Denmark
Andrew Goldberg, Amazon, U.S.
John Iacono, Université libre de Bruxelles, Belgium
Russell Impagliazzo, University of California, San Diego, U.S.
Giuseppe Italiano,   LUISS Guido Carli, Rome, Italy
Michael Kapralov,  École Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Anna Karlin, University of Washington, Seattle, U.S.
Valerie King, University of Victoria, Canada (Co-chair)
Hung Le, University of Victoria, Canada and  University of Massachusetts at Amherst, U.S. (Co-chair)
Daniel Lokshtanov, University of California, Santa Barbara, U.S.
S. Cenk Sahinalp, NIH and University of Indiana, Bloomington, U.S.
Jared Saia, University of New Mexico, U.S.
Shay Solomon, Tel Aviv University, Israel
Mario Szegedy, Alibaba and Rutgers University, U.S.
Robert Tarjan, Princeton University, U.S.
Seeun William Umboh, University of Sydney, Australia
Qin Zhang, University of Indiana, Bloomington, U.S.
Uri Zwick, Tel Aviv University, Israel

Steering Committee
Michael A. Bender, Stony Brook University, U.S.
David Karger,  Massachusetts Institute of Technology, U.S.
Tsvi Kopelowitz, Bar-Ilan University, Israel
Seth Pettie,  University of Michigan, U.S.
Robert Tarjan, Princeton University, U.S.
Mikkel Thorup, University of Copenhagen, Denmark

Submissions and Deadlines:
A link to the submission site is available https://easychair.org/my/conference?conf=sosa21.
Short Abstract Submission and Paper Registration Deadline: August 12, 2020, 4:59 PM Eastern Time
Full Paper Submission Deadline: August 19, 2020, 4:59 PM Eastern Time
Acceptance Notification: early October 2020
Proceedings (posted online):  early January 2021


How to Participate
Authors must submit their papers electronically, in PDF format.
Submissions should begin with a title page containing the paper title, each author’s name, affiliation, and email address, and an abstract summarizing the contributions of the paper. There is no page limit. The paper should begin with a clear description of the algorithmic problem to be solved, a survey of prior work on the problem—including a candid assessment of prior work in terms of simplicity and elegance—and a discussion of the contributions of the paper. The body of the paper should be written for a general theoretical computer science audience, and substantiate the main claims of the paper with full proofs. The submission should be typeset using 11 point font, in a single-column format with ample spacing throughout and ample margins all around.  The submissions ought to be visually easy to read.
Brevity is a hallmark of simplicity. Authors are specifically encouraged to submit short and simple papers. Final papers may not exceed fifteen (15) pages in double column format.

The program committee may designate one or more papers as SOSA Best Papers. All submissions will be considered.

(Does it still make sense to blog such announcements or is these days Twitter the only way to go about this? Asking for a friend 🙂 )

Prasad Raghavendra and Avishay Tal have organized a sequence of 6 lectures on some of the exciting recent advances in analysis of Boolean functions.

Lecture Series: Advances in Boolean Function Analysis

The Simons Institute is organizing a series of lectures on Advances in Boolean Function Analysis, that will highlight a few major developments in the area. The series will feature weekly two-hour lectures from July 15th to Aug 18th.  The lectures aim to address both the broad context of the results and their technical details. Though closely related in theme, each lecture will be self-contained.  The schedule is attached below (more info at link).

Talks take place on Wednesdays at 10am Pacific time (1pm Eastern). If you can’t catch them live, they will be redcorded.

Zoom Link: https://berkeley.zoom.us/j/93086371156

Talk Schedule:

July 15, Wednesday  10:00am PDT (1pm EDT) Dor Minzer (Institute of Advanced Study)On the Fourier-Entropy Influence Conjecture

July 22, Wednesday, 10:00am PDT (1pm EDT) Hao Huang (Emory University) & Avishay Tal (UC Berkeley)Sensitivity Conjecture and Its Applications

August 3rd, Monday, 10:00am PDT (1pm EDT) Shachar Lovett (UC San Diego)Improved Bounds for the Sunflower Lemma

August 5, Wednesday, 10:00am PDT (1pm EDT) Ronen Eldan (Weizmann Institute)Concentration on the Boolean Hypercube via Pathwise Stochastic Analysis

August 12, Wednesday, 10:00am Esty Kelman (Tel Aviv University) KKL via Random Restrictions

August 18, Tuesday, 10:00am Pooya Hatami (Ohio State University)Pseudorandom Generators from Polarizing Random Walks

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.