## Swiss TCS winter school (guest post by David Steurer)

*[Guest post by David Steurer – seems like a great opportunity! –Boaz]*

The Swiss Winter School on Lower Bounds and Communication Complexity (10-14 February 2020, https://theory.epfl.ch/WinterSchool2020/ ) is the first in a series of annual winter schools in Theoretical Computer Science jointly organized by EPFL and ETH Zurich. The goal of the school is to educate top international theory PhD students about exciting recent developments in the field. The winter school will be held in Zinal, a mountain village in the Swiss Alps that has a long tradition of hosting academic workshops and that allows for nice excursions and stimulating discussions in a relaxed atmosphere.

This year’s installment features an exciting trinity of speakers: Kasper Green Larsen (Data Structure Lower Bounds), Raghu Meka (Communication Complexity) and Amir Shpilka (Algebraic complexity).

The application deadline is November 15th 2019, and acceptance notifications will be sent by December 1st 2019. The application form is available at https://theory.epfl.ch/WinterSchool2020/. Attendance of the winter school is free of charge and includes room and board (shared rooms).

Organizers: Michael Kapralov (EPFL), David Steurer (ETH) , Ola Svennson (EPFL)

## Make equations blue in powerpoint

Microsoft Powerpoint has a surprisingly powerful equation editor, which also allows to use latex macros such as `\alpha `

to get .

I’ve blogged about the equation editor before but one pet peeve of mine was that I like to have my math in a different color, but never found a way to do this automatically. I finally decided to invest the time and find out how to do it. After a mere several years of investigation, I am happy to report that it is in fact possible to do so using Visual Basic for Applications (VBA).

You can view the developer tab by following these instructions, and then click on “macros”, type a name such as `All_eqs`

and click on “create” at which point you can add the following code:

Sub All_eqs() Dim oSld As Slide Dim oShp As Shape Dim oShapes As Shapes For Each oSld In ActivePresentation.Slides Set oShapes = oSld.Shapes For Each oShp In oShapes If oShp.HasTextFrame Then If oShp.TextFrame.HasText Then With oShp.TextFrame.TextRange For x = 1 To .Characters.Count If .Characters(x).Font.Name = "Cambria Math" Then .Characters(x).Font.Color.RGB = RGB(0, 112, 192) End If Next x End With End If End If Next oShp Next oSld End Sub

## Update on the Safe ToC initiative (guest post by Sandy Irani)

*[Guest post by Sandy Irani; see also the new website http://safetoc.org for more information on this initiative. –Boaz ]*

Update and follow-up on the Safe ToC initiative:

Last year, a group of us served on an ad hoc committee to combat harassment and discrimination in the Theory of Computing community. In our report, we suggested a number of measures that the various theory conferences could adopt to help in this effort. At a minimum, we wanted conferences to adopt a code of conduct and to appoint volunteers to serve as ToC Advocates whose role will be to provide support to any individual who has experienced harassment at a conference. Our full final report is now available here:

https://www.ics.uci.edu/~irani/ToC_SH_report.pdf

A small subset of the original committee along with Yuval Rabani in his capacity as IEEE TCMF chair are working on implementing some of the recommendations in the recent report. We have now launched a web site for the SafeToC Initiative: safetoc.org

So far, the support from the broader community has been strong. Quite a few conferences have passed resolutions to adopt the recommended practices in our report. The new web site lists all the participating conferences as well as the names of volunteers who have signed on to be ToC Advocates. The web site also provides information for ToC Advocates, conference organizers, and members of the ToC community.

Participating conferences all have codes of conduct and are ensuring that participants agree to abide by the code as part of their registration process. In addition, some of these conferences are adopting new mechanisms for author-declared conflicts of interests. This is especially important if an author feels that he or she may receive an unfair review due to a previous harassment-related incident.

Of course, the work is not done, and this important effort needs to continue. What can everyone do from here?

- First, we are in need of trained ToC Advocates, to spread this important service around! An advocate would be a designated conference attendee who would be available to provide support and information to anyone who has observed or experienced harassment at the conference The work is not difficult. Right now the training consists of an hour-long webinar sponsored by the ACM. We are envisioning one or two group Skype meetings per year to share experiences and best practices. If you are interested in serving as a ToC Advocate for a conference, you can contact someone on the steering committee for that conference.

- Second, even if you are not serving as an Advocate, please familiarize yourself with the various codes of conduct, and perhaps even listen to a training video! A larger community of invested bystanders who are aware of these issues and prepared to support and/or intervene as needed is critical. This does not have to mean formal reporting – even helping to diffuse a problematic situation or checking in on a colleague to be sure they are ok after a difficult conversation can make a big difference to someone involved in an incident.

We will continue to update the web page as participation in this effort grows. Thank you to everyone for helping to make our community a safe and welcoming place for everyone.

Erin Chambers

Martin Farach-Colton

Sandy Irani

Yuval Rabani

List of Resources:

- ACM training webinar (https://webinars.on24.com/acm/harassment)
*No Means No: Respond to Harassment in the Moment,*Webinar sponsored by the Association for Women in Science. (https://vimeo.com/163581972/6b1f96fb72)*Spot and Stop It: How To End Harassment at Professional Meetings,*Webinar sponsored by the Association for Women in Science. (https://vimeo.com/166410162/8dc250e79a)- Sexual Harassment Resources from the CRA-W (https://cra.org/cra-w/sexual-harassment)

## Sensitivity conjecture proved!

In a recent breakthrough, Hao Huang gave a 6 page paper proving the longstanding sensitivity conjecture. (Hat tip, Scott Aaronson and Gil Kalai. See this stackexchange post and this paper of Avishai for some links to the literature on this.)

The proof is beautiful and simple. I will write a few words here, but it is probably easier for you to just read the paper. The sensitivity conjecture was known to follow from the following statement: let be the *Boolean Cube* which is the degree graph on vertices identified with such that for every , if their Hamming distance is one. Then, the maximum degree of every subgraph of of size is at least .

Hao proves the above statement by showing that there is a *signing* of the adjacency matrix of that turns it into a matrix with eigenvalues equaling and eigenvalues equaling . That is, he shows (using a simple but clever inductive argument, see the 5 line proof of his Lemma 2.2) that there is an matrix with entries in whose nonzero entries correspond to the edges of the Boolean cube, and such that all the eigenvalues of are and they sum up to zero. (Note that this makes sense since should have the same *Frobenius norm* as the adjacency matrix of . The Frobenius norm squared is both the sum of squares of entries, which is for which is a degree graph, and also equal to the sum of squares of the eigenvalues, which is if all eigenvalues are .)

Once you have such a signing, the result follows from Cauchy’s Interlace Theorem that says that for every matrix and any matrix that is a principle sub-matrix of ,

where are the eigenvalues of and is the maximum eigenvalue of . A corollary of this (which is the only fact we need) is that if has its top eigenvalue with multiplicity (i.e., ), then every principle sub-matrix of order larger than will satisfy . (In fact, we only need .)

Indeed, suppose that is a subgraph of the Boolean cube of size . Then the principle submatrix of corresponding to the vertices of satisfies (since and the first eigenvalues of are ). But it’s easy to show that for every matrix the maximum eigenvalue of is upper bounded by the maximum norm of its rows, which in our case is the maximum degree of the graph .

## TCS Women at STOC (guest post by Virginia Williams)

*[Guest post by Virgi Vassilevska Williams on the TCS women program at STOC. In particular the TCS Women Spotlight workshop has a great program and is open to all. –Boaz]*

## Intro-TCS rebooted

This Spring and Summer I am doing some major editing to my text on introduction to theoretical computer science. I am adding figures (176 so far and counting..), examples, exercises, simplifying explanations, reducing footnotes, and mainly trying to make it more “user friendly” and less “idiosyncratic”. I am now adding in all chapters figures such as the following that outline the main results and how they are connected to one another.

Specifically, in the previous version of the book I used *programming languages *as the main computational models. While I still think this is the right way if we were to “start from scratch”, these idiosyncratic models made it harder for students to use other resources such as textbooks and lecture notes. They also make it more difficult for instructors to use individual chapters in their courses without committing to using the full book.

Hence in the new revision the standard models of **Turing Machines** and **Boolean Circuits** are front and center. We do talk about the programming-language equivalents as well, since I think they are important for the connection to practice and some concepts such as the duality of code and data are better explained in these terms. I also use the programming-language variants to demonstrate concepts to students in code including compilers from circuits to straightline programs, various “syntactic sugar” transformations, and the Cook-Levin Theorem and NP reductions.

One thing did not change – we still start with *Boolean Circuits *rather than automata as the initial computational model. Boolean circuits are closer to actual implementations of computing, are a finite (and hence simpler) model, but one that is non-trivial enough to allow showing some important theorems early in the course including existence of a circuit for computing every finite function, the existence of a circuit to evaluate other circuits, and the counting lower bound as well as the counting lower bound.

Circuits are also crucial for later material in the course since they make the proof of the Cook-Levin Theorem much simpler and cleaner, allow talking about results such as and Sipser-Gacs, and are crucial to be even able to state results in advanced topics such as derandomization, cryptography, and quantum computing.

We do cover automata as well, including the equivalence of regular expressions and deterministic finite automata. We also cover context-free grammars (though not pushdown automata) and the λ calculus, including its equivalence with Turing Machines and the Y combinator (see also this notebook)

I have also done some work on the technical side of producing the book. The book is written in markdown. Markdown has many advantages but it wasn’t designed for 600-page technical books full of equations and cross-references so I did need to use some extensions to it. I am using pandoc (and my own filter) to produce both the HTML and LaTeX/PDF versions of the book.

There is still more work to do. I plan to add a chapter on space complexity and on proofs and computation (including both interactive and zero knowledge proofs, as well as the “propositions as types” correspondence between proofs and programs). I need to add more examples and exercises. There are also still several chapters where the text is “rough around the edges”.

As usual, the latest version of the book is available on https://introtcs.org . If you see any typo, problem, etc.., please post an issue on the GitHub repository (you can also make a pull request for small typo fixes if you prefer)

We invite you to submit your papers to the 11th Innovations in

Theoretical Computer Science (ITCS). The conference will be held at

the University of Washington in Seattle, Washington from January 12-14,

2020.

ITCS seeks to promote research that carries a strong conceptual message

(e.g., introducing a new concept, model or understanding, opening a new

line of inquiry within traditional or interdisciplinary areas,

introducing new mathematical techniques and methodologies, or new

applications of known techniques). ITCS welcomes both conceptual and

technical contributions whose contents will advance and inspire the

greater theory community.

Submission deadline: September 9, 2019 (05:59pm PDT)

Notification to authors: October 31, 2019

Conference dates: January 12-14, 2020

See the website at http://itcs-conf.org/itcs20/itcs20-cfp.html for

detailed information regarding submissions.

Program committee

Nikhil Bansal, CWI + TU Eindhoven

Nir Bitansky, Tel-Aviv University

Clement Canonne, Stanford

Timothy Chan, University of Ilinois at Urbana-Champaign

Edith Cohen, Google and Tel-Aviv University

Shaddin Dughmi, University of Southern California

Sumegha Garg, Princeton

Ankit Garg, Microsoft research

Ran Gelles, Bar-Ilan University

Elena Grigorescu, Purdue

Tom Gur, University of Warwick

Sandy Irani, UC Irvine

Dakshita Khurana, University of Illinois at Urbana-Champaign

Antonina Kolokolova, Memorial University of Newfoundland.

Pravesh Kothari, Carnegie Mellon University

Rasmus Kyng, Harvard

Katrina Ligett, Hebrew University

Nutan Limaye, IIT Bombay

Pasin Manurangsi, UC Berkeley

Tamara Mchedlidze, Karlsruhe Institute of Technology

Dana Moshkovitz, UT Austin

Jelani Nelson, UC Berkeley

Merav Parter, Weizmann Institute

Krzysztof Pietrzak, IST Austria

Elaine Shi, Cornell

Piyush Srivastava, Tata Institute of Fundamental Research, Mumbai

Li-Yang Tan, Stanford

Madhur Tulsiani, TTIC

Gregory Valiant, Stanford

Thomas Vidick, California Institute of Technology (chair)

Virginia Vassilevska Williams, MIT

Ronald de Wolf, CWI and University of Amsterdam

David Woodruff, Carnegie Mellon University