Skip to content

Do we have TCS “Harvey Weinsteins”?

October 19, 2017

Following the Harvey Weinstein scandal, I’d like to believe that the academic environment at large, and theoretical computer science in particular, is a much better environment than Hollywood. But we would be misleading ourselves to think that we are completely without our issues. This story can be an opportunity for each of us, men and women, to think what can we do to eradicate such behavior from our field. I don’t have any easy answers, but all of us, especially senior men in positions of influence, should try to do what we can and not look the other way. There is not much that can be more damaging for a person coming up in a field than somebody abusing and objectifying them rather than treating them as a colleague and an intellectual.

This is not exactly related, but what prompted me to write this post was hearing from a  friend (who is a non CS faculty in another part of the U.S.) whose children were kicked out from a private (non religious) school when the principal learned they come from an LGBT family. I was truly shocked that something like that can happen in a fairly large U.S. city. It got me thinking (again) of how easy it is to believe that such issues are a thing of the past, or happen in only the remotest parts of the world or the country, when you are not part of the affected population.

 

STOC 2018 CFP

October 16, 2017

The call for paper for STOC is up, see  http://acm-stoc.org/stoc2018/ and  here. The deadline is November 3, 2017 4:59pm Eastern Daylight Time.

STOC 2018 will again be a Theory Fest and also celebrate the 50th anniversary of STOC. As part of the “retro” atmosphere, the STOC PC also asks submissions to be sent by mail in 20 printed copies at most 10 pages.

Michael Cohen

September 27, 2017

[This is a guest blog post on behalf of MSR, communicated to me by Yuval Peres. Like everyone who knew Michael, I was incredibly shocked and saddened by the news. I had relatively few interactions with Michael, but he has made a deep impression. I was always hoping we’d get a chance to collaborate , as it was clear to me that he’s exceptionally talented and creative.  If you’ve known Michael, feel free to share your perspective in the comments. -Boaz]

The Microsoft Research family is shocked and deeply saddened by the tragic loss of our colleague and friend Michael Cohen.  Michael was a brilliant mathematician and a rising star in his field.  He spent this past summer with us as a Microsoft Research Fellow, doing what he loved most. Over the summer, he made sweeping progress in online learning and online algorithms, two fields he had just recently become acquainted with. In addition to solving five open problems in these areas, he continued his substantial progress on the k-server problem, one of the most celebrated and notoriously difficult challenges in the space of adaptive algorithms.

 

Michael was a truly exceptional individual.  We will remember Michael for his infectious smile and his larger-than-life personality. We will never forget his unrelenting curiosity, his thirst for knowledge, and his deep love for mathematics and theoretical foundations of computing.  We are stunned by his loss.  We will hold onto our memories of Michael, and know that his ideas and scientific accomplishments will continue on as important advances.

 

We extend our most sincere condolences to Michael’s family and friends.

Special year on combinatorics and complexity

September 8, 2017

This year Harvard’s Center for Mathematical Sciences and Applications is running a special year on combinatorics and complexity. We have many long-term visitors and postdocs, and several events that theoretical computer scientists might wish to take part in, including four workshops:

Our Friday theory reading group will move to the CMSA center and feature many speakers from the special year.

In addition, the program will feature a series of public lectures by Noga Alon (Sept. 7), Jennifer Chayes (Nov. 2), Jacob Fox (Feb. 1), and Dan Spielman (March 20).

Combinatorics will also be featured in this year’s Ahlfors Lecture Series, given by Timothy Gowers (University of Cambridge) on October 11-12. Leslie Valiant will give the Ding Shum lecture on October 10.

Harvard will also host the Women In Theory workshop in the summer of 2018 (details forthcoming),

Participation: Researchers interested in participating in the special year through a short- or long-term visit to CMSA are encouraged to contact the organizers through the CMSA Administrative Coordinator, Sarah LaBauve (slabauve@math.harvard.edu).  Each of the workshops is also open to participation by all interested researchers subject to capacity. Registration forms can be found on the webpages for the individual workshops. 

 

Men in Computer Science

August 16, 2017

There have been some discussions lately on gender ratios and equality in Computer Science. In this post I don’t want to rehash the scientific studies, but just talk about my own experience as a man in the field of theoretical computer science, ever since I started graduate school nearly 20 years ago. I don’t presume to talk for all males, but I don’t think my story is completely non-representative. This is also a good opportunity to recommend that people read the research life stories series that Omer Reingold initiated on this blog, as well as the Turing centennial series on Luca Trevisan’s blog.

 

Like many other new grad students, when I just started at the Weizmann Institute of Science, I was extremely anxious. While I loved (the little I knew about) theory, I was not sure if I’m smart enough to do original research in this area. The professors seemed like beings from another world, but one thing that helped was that at least I did share some background with them. Almost all of them were males (and in fact, this being Israel, almost all were, like me, Ashkenazi secular jews). So, it was not completely unthinkable to imagine that I would some day be like them.

 

Another thing that helped me a lot in my early time in Weizmann was my study group.
I quickly found three friends, all male, and we spent many hours together studying for exams, talking about research, but also playing video games.

 

As I progressed in the field, I’ve had a great many research interactions and collaborations. I’ve met people at all hours and various locations, including coffee shops, restaurants, and private homes. I’ve never had to worry about the potential for sexual harassment, nor that I would be judged by my looks or what I wear. I am the type of person that speaks their opinion loudly, perhaps sometimes a little too loudly. In my experience, women that act the same are judged by a different standard and often “rub people the wrong way” and get tagged as having problematic personalities. Also, I was never afraid to ask potentially stupid questions. I did not need to fear that asking such a question would confirm people’s bias about me that I don’t belong in this field. Asking potentially stupid questions is one of the most useful ways to learn and evolve as a scientist.

 

Last but not least, I would most definitely not be where I am if my wife did not quit her job in Israel to move with me across the Atlantic for my postdoc. Also, while I think of myself as an involved father, I have to admit that Ravit still does more of the childcare duties. (As I’m reading this out loud, my daughter is commenting that I am not such an involved father…) Again, I am not saying that all male scientists are like me, nor that there are no female scientists that greatly rely on the support of their partners, but I don’t think my situation is atypical.

 

On more general terms, one misconception I see about science in such discussions is that it is about “things” or “facts” and not people, and hence perhaps should be free of biases.
But in fact science is an extremely social enterprise. Since graduating, I have never written a solo paper. Much of my work is spent talking to people in front of a whiteboard or notepad, and I’ve learned a great deal from discussions with fellow scientists. This also explains why certain subfields of science can have outlying gender or ethnicities ratios. People just feel more comfortable working with others similar to them, and role models greatly influence the fields students choose to pursue. For example, there is nothing innately Hungarian about combinatorics. Similarly, there is nothing innately feminine about cryptography, but rather a few extremely strong female scientists have had a huge effect. The influence of people such as Shafi Goldwasser, Tal Rabin, and others has not been limited just to their (amazing) research results but also as role models and mentors to many female cryptographers (and many male cryptographers as well, myself included).

 

I don’t like the expression “leveling the playing field” because Science is not a game. This is not about competing but about collaborating with each other to uncover the mysteries of the universe. But us males (especially those that, like me, come from amply represented ethnicities), should be aware and grateful for the advantages we’ve had in our careers. We should not try to remove these advantages: access to role models, freedom from bias, ease of networking, are all good things. We should however strive for a world where everyone enjoys the same benefits. In such a world we’ll have more scientists that are more productive and happier, and that will only be better for science.

FOCS 2017: Registration and call for workshops

August 14, 2017

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.

The intermediate complexity conjecture

August 9, 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 poly(n) (with a small exponent, such as 1,2 or 3) or at least 2^{\Omega(n)} (with a not too small coefficient in the exponent). This is perhaps the main reason why we are excited when people discover an n^{20} (or even n^{polylog(n)}) 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 n^{10} > 2^{n^{0.1}} for every input length n 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 2^{\sqrt{n}} or n^{\log n} by padding exponentially hard problems. This is one of the reasons why Impagliazzo Paturi and Zane argued that for NP problems, the parameter n 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 \Sigma and constant k, a CSP CSP(\mathcal{P}) is characterized by a set \mathcal{P} of predicates from \Sigma^k \rightarrow \{0,1\}.
The input for CSP(\mathcal{P}) is a collection of functions P_1,\ldots,P_m :\Sigma^n \rightarrow \{0,1\}, each of which applies some predicate in \mathcal{P} to a k-subset of its coordinates.
The basic task in CSPs is exact satisfiability, where the goal is to tell whether there is some assignment x for the inputs that such that P_1(x)=\cdots = P_m(x)=1.
The celebrated CSP dichotomy conjecture (which perhaps should now be called a theorem) implies (in its modern, algebraic form) that for every \mathcal{P}, either there is a polynomial-time (in fact I believe that at most O(n^3) time) algorithm for the exact satisfiability of CSP(\mathcal{P}) or there is a constant-factor blowup reduction from 3SAT to CSP(\mathcal{P}), implying that (under the exponential-time hypothesis or ETH) its complexity is 2^{\Omega(n)}.

The approximation problem for CSP(\mathcal{P}) is parameterized by two numbers 0 < s < c < 1 (known as the soundness and completeness paramters) and asks to distinguish, given an input P_1,\ldots,P_m of CSP(\mathcal{P}), between the case that there is some assignment x such that \tfrac{1}{m}\sum_{i=1}^m P_i(x) \geq c, and the case that \tfrac{1}{m}\sum_{i=1}^m P_i(x) \leq s for every x\in \Sigma^n. 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 CSP(\neq)), 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 \epsilon>0, there exist some \mathcal{P}, 0<s<c<1 and \delta,\mu >0 such that c vs s approximation of CSP(\mathcal{P}) can be done in time 2^{n^\epsilon} but (the potentially easier) c+\mu vs s-\mu  approximation cannot be done in time 2^{n^\delta}.

This is a consequence of the subexponential time algorithm for unique games, which in particular implies that for, say, c=1/10, there is some \epsilon = \epsilon(s) that tends to zero with s such that the s vs c problem for the unique games CSP can be solved in time 2^{n^\epsilon}.
On the other hand, the Unique Games Conjecture implies that for every 0<s<c<1, no matter how close s is to zero, or c is to 1, the s vs c problem for unique games is NP hard and hence (under the ETH) cannot be solved in time 2^{n^{o(1)}}.

 

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 2^{n^{o(1)}} time or require at least 2^{n^{1-o(1)}} 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:

 

ug_graph

Figure 1: Conjectured time complexity of s vs c=0.99 approximation of unique games as a function of s assuming the unique games conjecture. The UGC characterizes the threshold \underline{s}>0 when the time complexity becomes 2^{n^\epsilon} for some \epsilon>0, while there is also a (not yet fully determined) threshold \overline{s}<c when there is a linear blowup reduction from 3SAT and hence (under the ETH) the complexity is 2^{n^{1-o(1)}}.

 

(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 s vs c approximation for unique games where c=0.499, and s can be arbitrarily close to 0. 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 c that is close to 1 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 G be the graph on n\times n binary matrices, such that two matrices A,B have an edge if A-B 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 S matrices of measure o(1) such that if we pick a random A\in S and a random neighbor B of A, then with constant probability B will also be in S. 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 U \subseteq GF(2)^{n\times n} is a basic set if U = \{ A : Au = v \} or U = \{ A : u^\top A = v^\top \} where u,v \in GF(2)^n are column vectors. Note that each such set has measure 2^{-n} among all matrices and that a random neighbor of an element in U will be in U with probability 1/2. For every constant c, you can clearly construct a set where a random neighbor stays inside with probability 2^{-c} by intersecting c 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 \epsilon>0 there exists some \delta>0 and c\in \mathbb{N} such that if n is large enough and G=G_n is the graph above with vertex set GF(2)^{n \times n} and A\sim B if rank(A+B)=1, then for every S \subseteq GF(2)^{n \times n}, if S satisfies \Pr_{A \in S, B \sim A}[B\in S] \geq \epsilon then there are c basic sets U_1,\ldots, U_c such that U = \cap_{i\in [c]} U_i satisfies |S \cap U | \geq \delta |U|.

I call this an “inverse conjecture” since it is aimed at characterizing the sets S 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 k \gg \ell, the vertices are dimension \ell subspaces of GF(2)^k, and two subspaces V,V' are neighbors if their intersection has dimension \ell-1.

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, 0.499 vs 0.001 unique games. By construction, the SOS value of this instance is \geq 0.499, 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 s vs 0.499 approximation of unique games would map an n variable instance to an instance of at least n^{2^{1/s}} (or maybe even n^{2^{2^{1/s}}})) size. Is this inherent?

  5. Is there a general conjecture that would predict for CSP(\mathcal{P}) (say even if \mathcal{P} is a single predicate) and 0< s < c < 1 what should be the time complexity of s \pm o(1) vs c \pm o(1) approximation for it? We have some approaches of trying to predict when the complexity should be 2^{n^{1-o(1)}} by considering pairwise independent distributions. I feel like a conjecture trying to characterize what can be done in 2^{n^{f(\epsilon)}} 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 1+\epsilon-wise independent CSP to a certain extent.