Windows On Theory

Fall is coming, and with it the annual holiday of FOCS. FOCS 2017 will be held at Berkeley from Oct 15-17, with a day of workshops/tutorials on Oct 14th. Registrations are now open at http://focs17.simons.berkeley.edu/registration.html

Early registration deadline for the conference is Sept 25th, 2017.

Speaking of workshops, there is one way to guarantee that FOCS has a workshop in an area you care about, and it is to organize such a workshop yourself!

Speaking from experience, organizing a workshop is non-zero but not unmanageable amount of work. It is a great way to connect with colleagues in your area, as well as expose some other people in the TCS community to it. The call for workshops is now up at http://focs17.simons.berkeley.edu/workshopAndTutorial.html

A proposal for a workshop can be quite minimal – the main thing you need is the names of the organizers and speakers. To submit a proposal, send an email to Aleskander Mądry and James Lee by September 3, 2017.

One of the mysteries of computation is that, as far as we can tell, the time complexity of many natural computational problems is either (with a small exponent, such as or ) or at least (with a not too small coefficient in the exponent). This is perhaps the main reason why we are excited when people discover an (or even ) time algorithm for an important problem X: we view this as evidence that X is of the EASY type, and the exponent is likely to be improved over time (as indeed most often happens).
Similarly, this is why we care about hardness reductions, even when they hide huge constants or exponents: we view them as evidence that a problem is of the HARD type, and expect (as is also often the case) the efficiency of the reduction to be eventually improved.
This is also why our asymptotic theory of efficiency in informative in a finite world, and we don’t spend too much time worrying about the fact that for every input length that could possibly fit in the world’s storage capacity.

Of course there are results such as the time hierarchy theorem and Ladner’s theorem that tell us that “intermediate complexity” do exist, but the hope is that this doesn’t happen for “natural” problems.
(In particular, we can artificially create problems of complexity or by padding exponentially hard problems. This is one of the reasons why Impagliazzo Paturi and Zane argued that for NP problems, the parameter should be thought of the solution size and not the input size.)

One family of natural problems are constraint satisfaction problems (CSPs). For some finite alphabet and constant , a CSP is characterized by a set of predicates from .
The input for is a collection of functions , each of which applies some predicate in to a -subset of its coordinates.
The basic task in CSPs is exact satisfiability, where the goal is to tell whether there is some assignment for the inputs that such that .
The celebrated CSP dichotomy conjecture (which perhaps should now be called a theorem) implies (in its modern, algebraic form) that for every , either there is a polynomial-time (in fact I believe that at most time) algorithm for the exact satisfiability of or there is a constant-factor blowup reduction from 3SAT to , implying that (under the exponential-time hypothesis or ETH) its complexity is .

The approximation problem for is parameterized by two numbers (known as the soundness and completeness paramters) and asks to distinguish, given an input of , between the case that there is some assignment such that , and the case that for every . There is one sense in which understanding the complexity of the approximation problem is easier, since in the context of approximation, the pesky difference between 3SAT and 3XOR (bane of many failed NP vs P proofs, and the main reason the dichotomy conjecture is so hard to prove) disappears. On the other hand, in this context a problem such as BIPARTITNESS (or ), which was in the EASY column of exactly solving, become the NP-hard problem of Max-Cut.

One of the most fascinating consequences of the Unique Games Conjecture is that, if it is true, then there are in fact CSPs for which their approximation is neither EASY nor HARD. That is, the Unique Games Conjecture (plus the ETH) implies the following conjecture:

Intermediate Complexity Conjecture: For every , there exist some , and such that vs approximation of can be done in time but (the potentially easier) vs  approximation cannot be done in time .

This is a consequence of the subexponential time algorithm for unique games, which in particular implies that for, say, , there is some that tends to zero with such that the vs problem for the unique games CSP can be solved in time .
On the other hand, the Unique Games Conjecture implies that for every , no matter how close is to zero, or is to , the vs problem for unique games is NP hard and hence (under the ETH) cannot be solved in time .

I find this conjecture very fascinating. A priori, we might expect a zero one law for CSP’s complexity, where, depending on the approximation quality, one could either solve the problem in time or require at least time. Indeed, we have good reasons to believe that predicates such as 3XOR and 3SAT satisfy such a zero/one law. But, if the intermediate complexity conjecture is true then for some predicates (such as unique games itself, and probably even max cut, which can hardly be called “unnatural”) we would get a non-trivial curve of the running time vs approximation quality, that looks something like this:

Figure 1: Conjectured time complexity of vs approximation of unique games as a function of assuming the unique games conjecture. The UGC characterizes the threshold when the time complexity becomes for some , while there is also a (not yet fully determined) threshold when there is a linear blowup reduction from 3SAT and hence (under the ETH) the complexity is .

(One other setting where people were not sure if the complexity of some finitely specified object must be either exponential or polynomial is group theory, where one can define the complexity of a finitely generated group as the number of distinct elements that can be generated by a word of length $n$. There it turned out there are groups of “intermediate complexity”.)

What is also quite interesting is that we might be able to prove the intermediate complexity conjecture without resolving the UGC. In an exciting recent work, Dinur, Khot, Kindler, Minzer and Safra gave a combinatorial hypothesis that, if true, would imply the NP hardness of vs approximation for unique games where , and can be arbitrarily close to . Thus, if their hypothesis is true then, combined with the subexponential time algorithm mentioned above, it would imply the intermediate complexity conjecture. (If the construction is improved to obtain completeness that is close to then of course it would prove the unique games conjecture as well.)

Through discussions with Pravesh Kothari and David Steurer, we showed that the DKKMS combinatorial hypothesis is equivalent to a fairly simple to state statement. Informally, it can be stated as follows: let be the graph on binary matrices, such that two matrices have an edge if has rank one over GF(2). (UGC/PCP experts might recognize this graph as the degree two short code graph.) This graph is not a small set expander in the sense that, if you think about it for few minutes, you see that there are sets matrices of measure such that if we pick a random and a random neighbor of , then with constant probability will also be in . The DKKMS hypothesis is equivalent to the conjecture that these sets that you think about after few minutes encompass all such examples.

Let me state this more formally: Lets say that a subset is a basic set if or where are column vectors. Note that each such set has measure among all matrices and that a random neighbor of an element in will be in with probability . For every constant , you can clearly construct a set where a random neighbor stays inside with probability by intersecting basic sets. You can also keep this probability constant even if you just subsampled a constant fraction of this intersection (and you can add a few random vertices as well). The DKKMS hypothesis is equivalent to the statement that this is all you can do. That is, it is equivalent to the following statement:

Inverse short code conjecture: For every there exists some and such that if is large enough and is the graph above with vertex set and if , then for every , if satisfies then there are basic sets such that satisfies .

I call this an “inverse conjecture” since it is aimed at characterizing the sets that have unusually small expansion in the short-code graphs in terms of their correlation with basic sets.
I find it a natural question, though have to admit that, despite thinking about it some time (and also talking about it, not just with David and Pravesh but also Irit Dinur, Shachar Lovett and Kaave Hoesseini) I still don’t have a strong intuition whether it’s false or true.
Given that the short code graph is a Cayley graph over the Boolean cube, this seems like a question that could be amenable to tools from Fourier analysis and additive combinatorics.
Some partial progress has been made by the DKKMS folks in their new manuscript.
In fact, the same observations show that their original hypothesis is also equivalent not just to the “inverse short code conjecture” but also to Hypothesis 1.7 in this report, which is an analogous “inverse conjecture” for the Grassmanian graph where, for , the vertices are dimension subspaces of , and two subspaces are neighbors if their intersection has dimension .

Nevertheless, at the moment this question is still wide open, and I hope this writeup encourages more people to work on it. Other than resolving this question, there are some other interesting research directions, including:

1. The DKKMS reduction combined with the Grigoriev 3XOR instance yields a concrete candidate sum-of-squares integrality gap for, say, vs unique games. By construction, the SOS value of this instance is , but is analyzing the soundness of this instance easier than the general case?

2. The underlying building block for DKKMS is a problem known as a smooth label cover. This is not precisely a CSP, but can we show that it has intermediate complexity? i.e., give a subexponential time algorithm for it? If the DKKMS hypothesis is correct then we know that such an algorithm should be an SDP hierarchy.

3. Suppose the combinatorial hypothesis is true, is there an inherent reason why its proof should not be a low degree SOS proof? After all, related isoperimetric results on the short code graph have been shown by low degree SOS proofs. Also, is the proof of the current best bounds coming from the DKKMS manuscript SOS-izable?

4. The quantiative bounds for the DKKMS reduction are terrible. I haven’t worked out all the details but it seems that the reduction from 3XOR to vs approximation of unique games would map an variable instance to an instance of at least (or maybe even ) size. Is this inherent?

5. Is there a general conjecture that would predict for (say even if is a single predicate) and what should be the time complexity of vs approximation for it? We have some approaches of trying to predict when the complexity should be by considering pairwise independent distributions. I feel like a conjecture trying to characterize what can be done in time would have something to do with defining a suitable notion of “$(1+\epsilon)$-wise independent distributions” perhaps via concepts of mutual information. For example, perhaps we can argue that a smooth label cover is a -wise independent CSP to a certain extent.

TL;DR: New notes on introduction to theoretical computer science are available at http://www.introtcs.org.

This fall I will be teaching CS 121 at Harvard: Introduction to Theoretical Computer Science.
This type of “intro theory” course is taught at many universities, sometimes under the name “introduction to the theory of computation” or “computability and automata”, typically using Sipser’s excellent book.
Sipser’s book is incredibly well-written and liked by students, but there have been many developments in theoretical computer science and CS at large since it was written, both in terms of new results, techniques, and applications, as well as new emphases and points of view on this area.

So what should an “intro TCS” course contain these days?
My sense is that this course is first and foremost about studying computation in its own right, as opposed to being a tool to solve other problems.
This is not just about computability and complexity, but also about looking at different ways to measure the “goodness” of algorithms, especially given the drastic change in the way algorithms interact with the world these days.
So, for example, students in such a course should get at least some awareness of questions such as privacy or incentive-compatibility, even if doing these topics justice requires dedicated courses.

Another point that should be “hammered in” more is of hardness as a resource.
This of course arises in derandomization and cryptography, where recently cryptocurrencies have been quite explicit about equating computational difficulty with “mining” precious metals.
The interaction of computation with the physical world need to also be covered, and these days an “intro TCS” course cannot skip talking about quantum computing, which is our current best approach for modelling physically feasible computation.

But more than anything, considering computation as an object in its own right forces students to change their way of thinking, and truly come to terms with questions such as how do we model computation, how code is also data, and all the self-referential “paradoxes” and complications this entails.
This has always been present in “intro TOC” courses, but students can sometimes lose the big perspective while working on the n-th proof of non-regularity using the pumping lemma, or the m-th NP hardness reduction.

I am of course not alone in thinking of the need for a “more modern” intro TCS course.
See for example, Scott Aaronson’s MIT course. Also CMU’s renowned (or is it infamous? 🙂 ) Great Ideas in TCS has been following such an approach for quite a while, and the folks at CMU have been very kind with advice and suggestions.

There are also books such as Aaronson’s Quantum Computing Since Democritus and Moore and Mertens’ The nature of computation that take a similar perspective, though neither is quite appropriate as an introductory undergraduate textbook.

Thus, I am working on writing a new set of lecture notes, which are available on http://www.introtcs.org.
These notes are very much a work in progress, and I welcome comments and suggestions.
In particular, the source for these notes is posted on a github repository and people are very much invited to use the issues and pull requests features there to post suggestions, comments, and point out (or even fix!) typos and bugs.

Some of the differences between these notes and the typical treatment include the following:

• Very little automata: We will not start with automata. I find regular and context free languages to be important topics, but believe that they should be introduced as an example of a restricted model after one learns about general models and undecidability. For example, once you’ve seen the impossiblity of the halting problem, you will understand why operating systems typically allow you to search for files using regular expressions and not by specifying an arbitrary function, as you would not want the shell to enter into an infinite loop.
  Generally, automata play a very small role in this version of this course.
• Start with straightline programs: Rather than talk about Turing machines, the first computational model is an extremely simple programming language that has only a single operation: foo := bar NAND baz assigns to the variable foo the result of the NAND of the variables bar and baz. There are no loops, if statements, or subroutines, so this corresponds to straightline programs that are of course the same as Boolean circuits. Since students are already familiar with programming, I believe that starting with such an ultra-simple programming language makes things more concrete. Moreover, thanks to the efforts of my wonderful teaching fellow Juan Esteller, there is an implementation of the NAND, NAND++, and NAND<< programming languages that are taught in this course.
• De-emphasize Turing machines: Rather than Turing machines, our universal computational model is an enhancement of the NAND programming language to the NAND++ programming language that allows loops by simply stipulating that the program execution goes back to the first line if the loop variable has the value 1. We also introduce an index variable i so that we can use foo_i to access a potentially unbounded memory. Of course, this is equivalent to Turing machines, and we show this equivalence (as well as equivalence to the lambda calculus and other models) . We also give a further enhancement of the NAND++ language that is equivalent to RAM programs, and so allows us to measure running time in the same it is measured in algorithms courses.
• Algorithms: While a theory of computation course is traditionally about the impossibility results or “lower bounds” part of TCS, it cannot afford to ignore algorithms completely. You can’t understand the challenge of trying to prove hardness before you’ve seen non-trivial algorithms. So, we will mention results such as the Karatsuba algorithm for multiplication, and how very often there is a fine line separating problems such as minimum cut and maximum cut, 2SAT and 3SAT, determinant and permanent, etc..
• Move fast and break things: Because we skip automata and don’t delve into the intricacies of Turing machines (and because our NAND model is essentially designed to make the proof of the Cook-Levin Theorem easy), we will (hopefully) be done with NP completeness before the mid-point of this course. This will allow us to talk about some advanced topics, see below.
• Randomness and cryptography: Randomness has become essential to computer science theory and practice, both as a computational resource and as a way to model the world. We talk about probabilistic algorithms, give some examples, and talk about derandomization (based on strong average-case assumptions), which is a nice seque into cryptography. In a cryptography lecture in an intro TCS course, people often show the RSA algorithm. We might do so too, but only as a way to motivate quantum computing later on. I want to convey the notion of how fantastic is the whole idea of public key encryption in the first place, and mention some of the even more fantastical notions such as fully homomorphic encryption. We will also see a public-key cryptosystem based on the hardness of solving noisy linear equations, which, unlike RSA, is probably going to be more similar to the commonly used public key systems 5-10 years from now. (Since I teach a whole course on cryptography, I might make the treatment of crypto in the TCS course briefer.)
• Algorithms and society: The TCS angle can and has provided useful insights on how we design algorithms where the input is provided by humans and their output effects humans. Students should at least know that this field exists, and mention issues such as incentive-compatibility, differential privacy and issues of governance in cryptocurrencies (perhaps tying this into the consensus problem in distributed computing).
• Entropy, coding, and compression: An understanding of entropy has become essential for both theoretical and applied computer science, whether it is to bound the complexity of a password, the number of samples required to learn a concept, or the length of a representation, entropy is all around us, and we will cover some basic information theory as well.
• Quantum computing: As mentioned, a theory of computer science has to talk about our realistic physical models for computation, and some of the surprising outcomes of quantum computation. While a full description of Shor’s algorithm may require too much lecture time, I find that Simon’s algorithm conveys the heart of its power and is much simpler to describe.

It is definitely an ambitious plan that will not make for an easy course to take or to teach.
Some might say that it’s a “recipe for disaster” but the saving grace is that, with the help of Salil Vadhan, we have assembled a wonderful teaching staff that should be a great help for the students in keeping up.
I will report back on how realistic it was at the end of the term.
Even with our fast pace, there are many areas of theory that are not mentioned above, but students should be exposed to. I hope to cover some of these topics in this course, or at least write lecture notes about them so that curious advanced students could read about on their own.

Once again, much of this is not novel, and courses such as the ones mentioned above have taken similar approaches. However, I still hope these notes can serve a useful resource for other people who teach similar courses.

Acknowledgements: These lecture notes are constantly evolving, and I am getting input from several people, for which I am deeply grateful.
Thanks to Jarosław Błasiok, Chi-Ning Chou, Juan Esteller, Alex Lombardi, Thomas Orton, Juan Perdomo, and Ryan Williams for helpful feedback.
Thanks to Anil Ada, Venkat Guruswami, and Ryan O’Donnell for helpful tips from their experience in teaching CMU 15-251.
Thanks to Juan Esteller for his work on implementing the NAND* languages.
Thanks to David Steurer for writing the scripts that we used for notes on sum of squares and that I am now repurposing to produce these notes and for his endless patience with me as I attempt to learn concepts such as git and makefiles. David’s code itself is based on several other packages, including pandoc, LateX, and the Tufte LaTeX and CSS packages.

(Guest post by Sanjeev Arora on behalf of the TheoryFest 2017 organizing committee)

Having entered into the organization of TheoryFest 2017 with some trepidation, we organizers were very relieved to see feedback such as  “Best. STOC. Ever”. This post shares with you the feedback we got from attendees, and our plans for the next couple of years.

Important: Next year’s Theory Fest will be June 25-29, 2018 in downtown LA. See you there!

Some Impressions from the event

Location, location, location. Smack in the middle of lovely Montreal, in the midst of an ongoing street festival/party, and within walking distance to the waterfront and good restaurants. I wouldn’t complain if the conference were held here every year!

No catered lunches. This greatly reduced registration fees, and (together with the weak Canadian dollar) allowed us to be more generous with food and drink during breaks (including an open bar on three nights!).  It also encouraged attendees to explore Montreal a bit more.

Every STOC paper also presented at poster session: a hit. Billed as the most controversial aspect of the TheoryFest, this ended up (based upon in-person and online feedback) as the most positive change. Respondents said they expected to hate poster sessions and ended up loving them. Having experienced the energy of poster sessions at non-theory conferences, I am not surprised. (We head the complaint that the poster room was a bit noisy, and will address it.)

Energy level. A day filled with different kinds of events seems to help keep up people’s energy levels. Attendance at the talks was high; I saw hardly any people loitering about in the public areas during talks. Possibly, it helped that  STOC talks were in three parallel sessions; 50% more choice of topics at any given moment.

Highest attendance among STOC/FOCS held abroad. 377 attendees, which is quite high for the past decade.

Junior-senior lunches. Via a google doc page, 3 junior researchers (grads/postdocs) got to sign up to go to lunch with a senior researcher.  These lunches got rave reviews, though not enough people participated due to the short notice. Next time we’ll be better organized.

Statistics from online survey

117 attendees have responded thus far to our online survey. Their average satisfaction with TheoryFest was 4.5/5 .

Large majorities (>75%) found the amount of time devoted to various sub-components “about right.”

In terms of quality, the poster session was the biggest hit, followed by the plenary long talks. STOC paper talks had somewhat weaker ratings. Here’s a more detailed feedback.

Our responses to the most important feedback.

 Given the general support for the changes introduced this year, next year’s event will see no more drastic changes; merely tweaks to improve the overall experience.

Some feedback we received include:

“Stoc talks need to be longer.” “Short stoc talks worked well; could shorten even more.”

The alternatives we see are:

• Longer 22 min talks in 4 parallel sessions instead of 3.
• Shorter 12 min talks in 2 parallel sessions (with poster sessions being the place to hear more details).

Both options have significant minority support but appear to lack majority support, which was the reason behind our split-the-baby decision of 17 min talks in 3 parallel sessions. We welcome further discussion. (The PC Chair Valerie King commented to me that she’d expected to dislike 17 min talks but ended up preferring this format.)
“The middle three days were a bit tiring; stretching from 9am to 10:30pm.”

We realize this and don’t see a good alternative. We hew to the philosophy that a big-tent theory conference should offer a large buffet of content, and attendees are free to decide how much to partake. One major problem with the old setup of STOC was an artificial cap on content —and arguably the day was nevertheless long and monotonous. Nobody complained about monotony this time.

“Some short plenary talks weren’t geared to a STOC audience.”

We’ll address  this by assigning each outside speaker a “theory envoy” who will give them feedback on their slides and talk plan. But clearly,  the problem will never go away 100%.

Overall, we welcome your feedback! If you didn’t fill out your Theory Fest survey thus far, please do so asap before we close it out, and feel free to also post your feedback as comments to this post.

The ITCS 2018 Call For Papers is now available!  

ITCS is a conference that stands apart from all others. For a decade now, it has been celebrating the vibrancy and unity of our field of Theoretical Computer Science. See this blog post for a detailed discussion of what makes ITCS so cool and the brief description of ITCS’17 at the end of this post.

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.

This year, ITCS will be held at MIT in Cambridge, MA from January 11-14, 2018.

The submission deadline is September 8, 2017, with notification of decisions by October 30, 2017.

Authors should strive to make their papers accessible not only to experts in their subarea, but also to the theory community at large. The committee will place a premium on writing that conveys clearly and in the simplest possible way what the paper is accomplishing.

Ten-page versions of accepted papers will be published in an electronic proceedings of the conference. However, the alternative of publishing a one page abstract with a link to a full PDF will also be available (to accommodate subsequent publication in journals that would not consider results that have been published in preliminary form in a conference proceedings).

You can find all the details in the official Call For Papers.

On last year’s ITCS (by the PC Chair Christos Papadimitriou)

This past ITCS (2017) was by all accounts the most successful ever.  We had 170+ submissions and 61 papers, including 5 “invited papers”, and 90+ registrants, all new records.  There was a voluntary poster session for authors to get a chance to go through more detail, and the famous Graduating Bits event, where the younger ones get their 5 minutes to show off their accomplishment and personality.

The spirit of the conference was invigorating, heartwarming, and great fun.  I believe none of the twelve sessions had fewer than 70 attendees — no parallelism, of course — while the now famous last session was among the best attended and went one hour overtime due to the excitement of discussion (compare with the last large conference that you attended).

Tomorrow is the last day of TheoryFest. My sense is that it was very successful in the most important metric that it was a great event for the people that attended it.  However, we will know more about this once we send out a questionnaire to attendees next week. (Please respond when you get it!)

Many people helped in making TheoryFest happen (my own role was quite limited: chairing the short invited paper committee), but two people that I think are worth singling out are the general chairs Hamed Hatami and Pierre McKenzie. Doing local arrangements often means a lot of work dealing with hotels, food, registrations, etc., without much recognition, but they really did an amazing job.

I might attempt later some longer expositions of some of the talks, but in the meantime, see Suresh’s and Dick’s posts. Luca writes about the awards. The best student paper awardee, Pasin Manurangsi, gave a wonderful talk about his almost tight hardness of approximation result for the classical densest-k-subgraph problem.  He managed to explain clearly what the result is, what are the limits of what we can hope for, and convey the main ideas of the proof, all in a 20 minute talk. The proof itself is beautiful: the reduction (from 3SAT) is simple and natural, but the analysis is quite subtle, combining clever new ideas with classical results in combinatorics.

Tomorrow is the workshop day which I am also looking forward to. Tselil Schramm said that we should probably have called our SOS workshop a “wutorial” since, while we will cover some “hot off the presses” results,  we are planning to mostly make the talks an accessible introduction to the field. In particular, Pablo Parrilo’s talk will be a broad overview of the sum of squares algorithm’s history, applications, and connections to other areas. (See my previous post for description of all the talks.) That said, there are some other great workshops in parallel to ours. That is probably one of the biggest problems with TheoryFest – too much great content and too little time..