Windows On Theory

In 2011, as a graduate student Jelani Nelson founded the AddisCoder course on algorithms and coding for high schoolers in Addis Ababa Ethiopia. Since then the course has been offered twice more, and this summer it will occur again for the fourth time. Over 330 students have completed the course, and some of its alumni are now students in top institutions in the U.S., Ethiopia, and all over the world. I was a lecturer in this course in 2016 and will be again this summer (together with Jelani, Timnit Gebru, and Daniel Kang).

The students in AddisCoder come from all over Ethiopia, and many have never considered computer science as a potential field of study or even touched a computer. Once when meeting an alum, I asked whether he enjoyed the course. He told me that he didn’t just enjoy it, it was a lifechanging experience for him, and I believe the same holds for many other graduates.

The reason for this post is that AddisCoder is now a tax-exempt non profit organization, which you can donate to through our website. It is a fairly lean operation, but funds are needed for travel of teaching staff (with TA’s that come from all over the world). Please consider supporting AddisCoder yourself (any amount helps!), and forward this information to any friends or colleagues. If you work for a company that might be interested in supporting AddisCoder, you can contact Jelani at the email minilek+addiscoder@gmail.com .

In December I participated in the wonderful “PCP Fest” workshop in Tel Aviv. The videos from these workshops are now online on their youtube channel.

The channel contains not just videos of talks but also two wide ranging interviews of Alon Rosen with Avi Wigderson and Christos Papadimitriou, as well as a discussion between them. I think many people, especially students, might find these interviews inspiring. They cover Avi’s and Christos’ personal and intellectual journeys, that are similar in some ways and quite different in others.

(As you’re working on your FOCS papers, an announcement about STOC 2019 from Eric Allender –Boaz)

STOC registration is now open acm-stoc.org/stoc2019/. The deadline to apply for travel grants is April 22 . Apply on
acm-stoc.org/stoc2019/travel-support.html

There is also travel support available via TCS Women (deadline April 25), see sigact.org/tcswomen/

The website for the FOCS 2019 conference is
http://focs2019.cs.jhu.edu/ , and the submission server is
https://focs19.cs.utexas.edu/

The deadline is 3:00pm PDT, April 5, 2019.

The reason I am posting this is that there is a fake FOCS website that ranks first or second on searches for “FOCS 2019”. The website is under the domain “aconf dot org” (I don’t want to increase ranking and traffic to it even further by linking to it). This website contains fake pages for many other conferences, and in fact sometimes is ranked highly enough in searchers that conference organizers mistakenly link to it in their own web page. Apparently it is owned by a company called Chaytey who also has a similar webpage for journals under the address xjournal dot net. (Thanks to Sara Cohen ,colleague of FOCS general chair Yuval Rabani for finding this out.)

In the Fall, Boaz and I co-taught a grad seminar on physics and computation (see here for some of the original press coverage). We were lucky to attract an intrepid group of students from multiple fields, with representatives from computer science, physics, math and biology. As part of the course, we asked our students to give presentations and write expository blog posts on a number of topics at the intersection of computation and physics, including algorithms from statistical physics, quantum area laws, and the firewall paradox. The students worked hard to produce posts that make the physics concepts accessible to a computer science audience, and the result is a nice collection of posts that create a “bridge” from CS to physics.

Here, the aim is to give a (long overdue) table of contents for their posts. Followers of the blog may have noticed a landslide of physics & computation posts around December and January; if you weren’t able to keep up with them all at the time, then here they are, rounded up and organized by topic.

Statistical Physics

Background and intro to phase transitions:

• Statistical Physics: an introduction in two parts (by Tselil Schramm)

Algorithms from statistical physics: belief propagation and approximate message passing:

• Belief Propagation and the Stochastic Block Model (by Thomas Orton)
• Introduction to AMP and the Replica Trick (by Preetum Nakkiran and Yueqi Sheng)

Informational and computational phase transitions:

• Algorithmic and Information Theoretic Decoding Thresholds for Low density Parity-Check Code (by Jeremy Dohmann, Vanessa Wong, and Venkat Arun)

Proving the existence of phase transitions:

• Ising Perceptron under Gaussian Disorder, and k-NAE-SAT (based on a guest lecture by Nike Sun, as scribed by Patrick Guo, Vinh-Kha Le, Shyam Narayanan, and David Stoner)

 Using convex relaxations to approximate partition functions:

• Approximating Partition Functions (based on a guest lecture by Andrej Risteski as scribed by Alex Kelser, Alex Lin, Amil Merchant, and Suproteem Sarkar)

Quantum Computation

Background on Quantum Hamiltonians and tensor network representations:

• What is Quantum Hamiltonian Complexity? (by Ben Edelman)
• Tensor Networks, Matrix Product States and Density Matrix Renormalization Group (by Fred Zhang)

Area laws:

• A 1D Area Law for Gapped Local Hamiltonians (by Boriana Gjura and Prayaag Venkat)

Quantum algorithms:

• Introduction to Quantum Walks (by Beatrice Nash)
• Efficient preparation of thermal states of quantum systems: natural or artificial (based on a guest lecture by Aram Harrow as scribed by Sinho Chewi, William S. Moses, Tasha Schoenstein, Ary Swaminathan)
• Quantum Approximate Optimization Algorithm and Applications (by
  Amir Karamlou)

Quantum games and quantum PCPs:

• Towards Quantum PCP: A Proof of the NLETS Theorem (by Abhijit Mudigonda, Richard Wang, and Lisa Yang)
• Quantum Games (by Nilin Abrahamsen, Daniel Alabi, Mitali Bafna, Emil Khabiboulline, and Juspreet Sandhu)

Quantum supremacy:

• Quantum circuits and their role in demonstrating quantum supremacy (by Hikari Sorensen)

Quantum error correction:

• Peter Shor on Quantum Error Correction (based on a guest lecture by Peter Shor as scribed by Annie Wei)

Black Holes and the Firewall Paradox

(See also Boaz’s introductory post)

Background on black holes and the Firewall Paradox:

• Why physicists care about the Firewall Paradox (by Noah Miller)
• Black hole paradoxes: A conservative yet radical journey (by Abhishek Anand and Noah Miller)

Firewall Paradox meets Computational Complexity:

• Black Holes, a complexity theory perspective (by Chi-Ning Chou and Parth Mehta)

[Guest post by Aleksander Mądry]

To me, one of the best things about working in theoretical computer
science has always the exciting rate of progress we make as a community. 
On (what appears to be) a regular basis, we produce breakthroughs on 
problems that are absolutely fundamental to our field. Problems that 
often look impossible to tackle, right up until someone actually tackles 
them.

However, as inspiring as all these developments were to me, I also 
always felt that we, as a community, could do more to properly recognize 
and highlight them, both internally and to the outside world. This kind 
of outreach would make it easier for us to capitalize on the 
breakthroughs as well as to accelerate the impact of the underlying 
ideas on the other areas of computer science, and beyond.

Fortunately, this is about to change!

One of the first decisions of our newly (re-)elected SIGACT committee was to create a committee (as committees are wont to do 🙂 whose mission will be to help promote top computer science theory research. This SIGACT Research Highlights Committee – consisting of Boaz Barak, Omer Reingold, Mary Wootters and myself – will, in particular, work to identify results to be recommended for consideration for the CACM Research Highlights section as well as other general-audience research outlets in computer science and other fields.

Of course, to do a proper job here we require your help! To this end, 
the committee solicits two types of nominations:

1) Conference nominations. Each year, the committee will ask the PC 
chairs of a broad set of theoretical computer science conferences to 
send a selection of up to three top papers from these conferences 
(selected based on both their technical merit and the potential 
significant interest to non-theory audiences) and forwarding them to the 
committee for consideration.

2) Community nominations. The committee will accept nominations from the members of the community. Each such nomination should summarize the contribution of the nominated (and recently published) paper and also
argue why this paper particularly merits a broader outreach. The 
nomination should be no more than a page in length and can be submitted 
at any time by emailing it to sigact.cacm.nominations@gmail.com. 
Self-nominations are discouraged.

To be considered in the upcoming round of our deliberations, we need to 
receive your nomination by April 30.

Looking forward to learning about all the new exciting research that you 
all are doing!

If, like others following the pace of modern life, you’re the kind of person that needs to get just on time updates on the state of theoretical computer science, consider signing up for the newsletter of CATCS. You can get information about funding opportunities, advocacy efforts, and more. Sure, at the hectic rate of two messages per year, it might flood your inbox, but it is worth it.

Dear Theoretical Computer Scientist,

The Committee for the Advancement of Theoretical Computer Science (CATCS) was established by SIGACT to deal with funding, outreach, and advocacy issues for our community. If you would like to receive our newsletter (no more than twice annually) we encourage you to sign up for the Google group below:
https://groups.google.com/forum/#!forum/catcs-news
(Navigate to the page above and click “Join group.” You can unsubscribe at any time from the same page.)
Best wishes, CATCS