Windows On Theory

Shcachar Lovett has put together a new website aggregating information about virtual talks in CS theory: https://cstheorytalks.wordpress.com/

 It has a Google calendar that people can add to their own, and a form to submit a new talk that automatically gets added to the Google calendar. 

This can be a fantastic resource these days that almost no one can travel – please publicize this and also submit to it talks that you are organizing.

From Sandy Irani, FOCS 2020 PC chair:

In light of the very unusual developments in the world due to the spread of Covid-19 and the disruption it is causing to many people in our field, especially those with young children at home, the FOCS PC has decided to push back the final deadline for papers by six days. We would have liked to do more, but we still are trying to stick to our timeline for notification since that date is coordinated with other deadlines in the theory community. In addition, some members of the committee are also affected by this crisis and there is concern that we may not be able to do our job as a committee in a shorter time frame. Pre-registration (including titles and abstracts) is still required by the original deadline. Here are the new dates:

Pre-registration (including titles and abstracts): Thursday April 9, 11:59 PM (EDT)

Final Paper Submission: Wednesday April 15, 11:59 PM (EDT)

Conference url: https://focs2020.cs.duke.edu/

We hope you all stay healthy!

–Sandy Irani, for the FOCS 2020 Committee

Harvard University, as well most other places that I know of will be moving to remote lectures. I just gave the last in-person lecture in my cryptography course. I would appreciate technical suggestions on the best format for teaching remotely. At the moment I plan to use Zoom and log-in from both my laptop (for the video) and from my iPad pro (for the interactive whiteboard).

The one silver lining is that more lectures will be available online. In particular, if you’re teaching algorithms, you might find Eric Vigoda’s videos helpful. (If you know of more sources, please let us know.)

I was hoping that reducing meetings and activities will be good for research, but currently find it hard to concentrate on anything except this train-wreck of a situation. The financial times has a chart that summarizes the progress of the disease in several countries:

The number of confirmed cases grows by about 33% each day. This growth in confirmed cases is partially due to increased testing as cases increase – there is some evidence that the doubling time of the disease (time between infected people to infected) is about 6 days (rather than the 2.4 days that this figure suggest). However, a doubling time of 6 days still means that the number of cases grows 10-fold in a month, and so if there are 10K actual cases in the U.S., today, there would be 100K by mid April and 1M by mid May.

Strong quarantine regimes, contact tracing, and drastically reducing activity and increasing “social distance” can very significantly reduce the base of this exponent. Reducing the base of the exponent is more than simply “delaying the inevitable”. The mortality statistics mask the fact that this can be a very serious illness even for the people who don’t die of it – about 5% of the cases need intensive care (see this Economist article). Spreading the infections over time will enable the healthcare system to handle the increased caseload, which will completely overwhelm it otherwise.

Such steps are clearly much easier to achieve before the number of cases is too large to be manageable, but despite having “advance warning” from other countries, this lesson does not seem at the moment to have sunk in, at least here in the U.S. At the moment no such initiatives are taken at the federal level, the states are doing more but still not enough, and it’s up to private companies and institutions to come up with their own policies. As faculty and citizens there is not much we can do about it except support such decisions even when they are unpopular, and just try to make the remote experience as good as possible for us, our colleagues, and our students.

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)

This semester I taught another iteration of my “Introduction to Theoretical Computer Science” course, based on my textbook in process. The book was also used in University of Virgnia CS 3102 by David Evans and Nathan Brunelle.

The main differences I made in the text and course since its original version were to make it less “idiosyncratic”: while I still think using programming language terminology is the conceptually “right” way to teach this material, there is a lot to be said for sticking with well-established models. So, I used Boolean circuits as the standard model for finite-input non-uniform computation, and Turing Machines, as the standard model for unbounded-input uniform computation. (I do talk about the equivalent programming languages view of both models, which can be a more useful perspective for some results, and is also easier to work with in code.)

In any course on intro to theoretical CS, there are always beautiful topics that are left on the “cutting room floor”. To partially compensate for that, we had an entirely optional “advanced section” where guest speakers talked about topics such as error correcting codes, circuit lower bounds, communication complexity, interactive proofs, and more. The TA in charge of this section – amazing sophomore named Noah Singer – wrote very detailed lecture notes for this section.

This semester, students in CS 121 could also do an optional project. Many chose to do a video about topics related to the course, here are some examples:

• Helen Huang and Phil Labrum: “Is your brain Turing complete?”
• Dylan Zhou: Candy Crush is NP complete and Mario Kart tour is PSPACE hard.
• Carolyn Ge, Kavya Kopparapu, and Eric Lin: a 4-part series on theory of machine learning including an interview with Les Valiant: What is learnability? Cryptographic limitations, Cryptography and Machine Learning, and future possibilities.
• And finally, Christine Cai, April Chen, Zev Nicolai-Scanio, and Grace Tian produced a rap song “Proof Göds” inspired by the course.

There is much work to still do on both the text and the course. Though the text has improved a lot (we do have 267 closed issues after all) some students still justifiably complained about typos, which can throw off people that are just getting introduced to the topic. I also want to add significantly more solved exercises and examples, since students do find them extremely useful. I need to significantly beef up the NP completeness chapter with more examples of reductions, though I do have Python implementation of several reductions and the Cook Levin theorem.

This type of course is often known as a “great ideas” in computer science, and so in the book I also added a “Big Idea” environment to highlight those. Of course some of those ideas are bigger than others, but I think the list below reflects well the contents of the course:

• If we can represent objects of type T as strings, then we can represent tuples of objects of type T as strings as well.
• A function is not the same as a program. A program computes a function.
• Two models are equivalent in power if they can be used to compute the same set of functions.
• Every finite function can be computed by a large enough Boolean  circuit.
• A program is a piece of text, and so it can be fed as input to other  programs.
• Some functions    cannot be computed by a Boolean circuit using fewer than exponential (in ) number of gates.
• We can precisely define what it means for a function to be computable by any possible algorithm.
• Using equivalence results such as those between Turing and RAM machines, we can “have our cake and eat it too”: We can use a simpler model such as Turing machines when we want to prove something can’t be done, and use a feature-rich model such as RAM machines when we want to prove something can be done.
• There is a  “universal” algorithm that can evaluate arbitrary algorithms on arbitrary inputs.
• There are some functions that can not be computed by any algorithm.
• If a function  is uncomputable we can show that another function is uncomputable by giving a way to reduce the task of computing to computing .
• We can use restricted computational models to bypass limitations such as uncomputability of the Halting problem and Rice’s Theorem. Such models can compute only a restricted subclass of functions, but allow to answer at least some semantic questions on programs.
• A proof is just a string of text whose meaning is given by a verification algorithm.
• The running time of an algorithm is not a number, it is a function of the length of the input.
• For a function and , we can formally define what it means for to be computable in time at most where is the size of the input.
• All “reasonable” computational models are equivalent if we only care about the distinction between  polynomial and exponential. (The book immediately notes quantum computers as a possible exception for this.)
• If we have more time, we can compute more functions.
• By “unrolling the loop” we can transform an algorithm that takes steps to compute into a circuit that uses gates to compute the restriction of to .
• A reduction shows that is “no harder than ” or equivalently that is “no easier than “.
• If a single -complete has a polynomial-time algorithm, then there is such an algorithm for every decision problem that corresponds to the existence of an efficiently-verifiable solution.
• If , we can efficiently solve a fantastic number of decision, search, optimization, counting, and sampling problems from all areas of human endeavors.
• A randomized algorithm outputs the correct value with good probability on every possible input.
• We can amplify the success of randomized algorithms to a value that is arbitrarily close to .
• There is no secrecy without randomness.
• Computational hardness is necessary and sufficient for almost all cryptographic applications.
• Just as we did with classical computation, we can define mathematical models for quantum computation, and represent quantum algorithms as binary strings.
• Quantum computers are not a panacea and are unlikely to solve complete problems, but they can provide exponential speedups to certain structured problems.

These are all ideas that I believe are important for Computer Science undergraduates to be exposed to, but covering all of these does make for a every challenging course, which gets literally mixed reviews from the students, with some loving it and some hating it. (I post all reviews on the course home page.) Running a 200-student class is definitely something that I’m still learning how to do.

In an exciting manuscript just posted on the arxiv, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen prove that there is a 2-prover quantum protocol (with shared entanglement) for the halting problem. As a consequence they resolve negatively a host of open problems in quantum information theory and operator algebra, including refuting the longstanding Connes embedding conjecture. See also Scott’s post and this blog post of Thomas Vidick discussing his personal history with these questions, that started with his Masters project under Julia Kempe’s supervision 14 years ago.

I am not an expert in this area, and still have to look the paper beyond the first few pages, but find the result astounding. In particular, the common intuition is that since all physical quantities are “nice” function (continuous, differentiable, etc..), we could never distinguish between the case that the universe is infinite or discretized at a fine enough grid. The new work (as far as I understand) provides a finite experiment that can potentially succeed with probability 1 if the two provers use an infinite amount of shared entangled state, but would succeed with probability at most 1/2 if they use only a finite amount. A priori you would expect that if there is a strategy that succeeds with probability 1 with an infinite entanglement, then you could succeed with probability at least with a finite entangled state whose dimension depends only on .

The result was preceded by Ito and Vidick’s 2012 result that and Natarajan and Wright’s result last year that (non deterministic double exponential time) is contained in . This brings to mind Edmonds’ classic quote that:

“For practical purposes the difference between algebraic and exponential order is often more crucial than the difference between finite and non-finite”

sometimes, the difference between double-exponential and infinite turns out to be non-existent..

I am in Tel Aviv Theory Fest this week – a fantastic collection of talks and workshops organized by Yuval Filmus , Gil Kalai, Ronen Eldan, and Muli Safra.

It was a good chance to catch up with many friends and colleagues. In particular I met Elchanan Mossel and Subhash Khot, who asked me to serve as a “witness” for their bet on the unique games conjecture. I am recording it here so we can remember it a decade from noe.

Specifically, Elchanan bets that the Unique Games conjecture will be proven in the next decade – sometime between January 1, 2020 and December 31, 2029 there will be a paper uploaded to the arxiv with a correct proof of the conjecture. Subhash bets that this won’t happen. They were not sure what to bet on, but eventually agreed to take my offer that the loser will have to collaborate on a problem chosen by the winner, so I think science will win in either case. (For what it’s worth, I think there is a good chance that Subhash will lose the bet because he himself will prove the UGC in this decade, though it’s always possible Subhash can both win the bet and prove the UGC if he manages to do it by tomorrow 🙂 )

The conference itself is, as I mentioned, wonderful with an amazing collection of speakers. Let me mention just a couple of talks from this morning. Shafi Goldwasser talked about “Law and Algorithms”. There is a recent area of research studying how to regulate algorithms, but Shafi’s talk focused mostly on the other direction: how algorithms and cryptography can help achieve legal objectives such as the “right to be forgotten” or the ability to monitor secret proceedings such as wiretap requests.

Christos Papadimitriou talked about “Language, Brain, and Computation”. Christos is obviously excited about understanding the language mechanisms in the brain. He said that studying the brain gives him the same feeling that you get when you sit in a coffee shop in Cambridge and hear intellectual discussions all around you: you don’t understand why everyone is not dropping everything they are doing and come here. (Well, his actual words were “sunsets over the Berkeley hills” but I think the Cambridge coffee shops are a better metaphor 🙂 )