Theory of Computing Blog Aggregator

Authors: Stefan Boettcher, Shanshan Li, Tharso D. Fernandes, Renato Portugal
Download: PDF
Abstract: Quantum walks provide a powerful demonstration of the effectiveness of the renormalization group (RG), here applied to find a lower bound on the computational complexity of Grover's quantum search algorithms in low-dimensional networks. For these, the RG reveals a competition between Grover's abstract algorithm, i.e., a rotation in Hilbert space, and quantum transport in an actual geometry. It can be characterized in terms of the quantum walk dimension $d^Q_w$ and the spatial (fractal) dimension $d_f$, even when translational invariance is broken. The analysis simultaneously determines the optimal time for a quantum measurement and the probability for successfully pin-pointing the sought-after element in the network. The RG further encompasses an optimization scheme, devised by Tulsi, that allows to tune that probability to certainty. Our RG considers entire families of problems to be studied, thereby establishing a large universality class for quantum search, here verified with extensive simulations.

at August 18, 2017 12:40 AM UTC

Authors: Raphaël Clifford, Tomasz Kociumaka, Ely Porat
Download: PDF
Abstract: We consider the problem of approximate pattern matching in a stream. In the streaming $k$-mismatch problem, we must compute all Hamming distances between a pattern of length $n$ and successive $n$-length substrings of a longer text, as long as the Hamming distance is at most $k$. The twin challenges of streaming pattern matching derive from the need both to achieve small and typically sublinear working space and also to have fast guaranteed running time for every arriving symbol of the text.

As a preliminary step we first give a deterministic $O(k(\log \frac{n}{k} + \log |\Sigma|) )$-bit encoding of all the alignments with Hamming distance at most $k$ between a pattern and a text of length $O(n)$. (We denote the input alphabet by the symbol $\Sigma$.) This result, which provides a solution for a seemingly difficult combinatorial problem, may be of independent interest. We then go on to give an $O(k\log^3 n\log\frac{n}{k})$-time streaming algorithm for the $k$-mismatch streaming problem which uses only $O(k\log{n}\log\frac{n}{k})$ bits of space. The space usage is within logarithmic factors of optimal and approximately a factor of $k$ improvement over the previous record [Clifford et al., SODA 2016]

at August 18, 2017 12:41 AM UTC

Authors: Yangming Zhou, Jin-Kao Hao, Béatrice Duval
Download: PDF
Abstract: This paper presents a hybrid approach called frequent pattern based search that combines data mining and optimization. The proposed method uses a data mining procedure to mine frequent patterns from a set of high-quality solutions collected from previous search, and the mined frequent patterns are then employed to build starting solutions that are improved by an optimization procedure. After presenting the general approach and its composing ingredients, we illustrate its application to solve the well-known and challenging quadratic assignment problem. Computational results on the 21 hardest benchmark instances show that the proposed approach competes favorably with state-of-the-art algorithms both in terms of solution quality and computing time.

at August 18, 2017 12:51 AM UTC

Authors: Branislav Kveton, S. Muthukrishnan, Hoa T. Vu
Download: PDF
Abstract: Data streams typically have items of large number of dimensions. We study the fundamental heavy-hitters problem in this setting. Formally, the data stream consists of $d$-dimensional items $x_1,\ldots,x_m \in [n]^d$. A $k$-dimensional subcube $T$ is a subset of distinct coordinates $\{ T_1,\cdots,T_k \} \subseteq [d]$. A subcube heavy hitter query ${\rm Query}(T,v)$, $v \in [n]^k$, outputs YES if $f_T(v) \geq \gamma$ and NO if $f_T(v) < \gamma/4$, where $f_T$ is the ratio of number of stream items whose coordinates $T$ have joint values $v$. The all subcube heavy hitters query ${\rm AllQuery}(T)$ outputs all joint values $v$ that return YES to ${\rm Query}(T,v)$. The one dimensional version of this problem where $d=1$ was heavily studied in data stream theory, databases, networking and signal processing. The subcube heavy hitters problem is applicable in all these cases.

We present a simple reservoir sampling based one-pass streaming algorithm to solve the subcube heavy hitters problem in $\tilde{O}(kd/\gamma)$ space. This is optimal up to poly-logarithmic factors given the established lower bound. In the worst case, this is $\Theta(d^2/\gamma)$ which is prohibitive for large $d$, and our goal is to circumvent this quadratic bottleneck.

Our main contribution is a model-based approach to the subcube heavy hitters problem. In particular, we assume that the dimensions are related to each other via the Naive Bayes model, with or without a latent dimension. Under this assumption, we present a new two-pass, $\tilde{O}(d/\gamma)$-space algorithm for our problem, and a fast algorithm for answering ${\rm AllQuery}(T)$ in $O(k/\gamma^2)$ time. Our work develops the direction of model-based data stream analysis, with much that remains to be explored.

at August 18, 2017 12:43 AM UTC

Authors: Imed Kacem, Hans Kellerer
Download: PDF
Abstract: In this paper, we consider four single-machine scheduling problems with release times, with the aim of minimizing the maximum lateness. In the first problem we have a common deadline for all the jobs. The second problem looks for the Pareto frontier with respect to the two objective functions maximum lateness and makespan. The third problem is associated with a non-availability constraint. In the fourth one, the non-availibility interval is related to the operator who is organizing the execution of jobs on the machine (no job can start, and neither can complete during the operator non-availability period). For each of the four problems, we establish the existence of a polynomial time approximation scheme (PTAS).

at August 18, 2017 12:50 AM UTC

Authors: Cetin Savkli, Ryan Carr, Matthew Chapman, Brant Chee, David Minch
Download: PDF
Abstract: A distributed semantic graph processing system that provides locality control, indexing, graph query, and parallel processing capabilities is presented.

at August 18, 2017 12:51 AM UTC

I have two new preprints on arXiv, from my two papers accepted to Graph Drawing.

  • “Triangle-free penny graphs: degeneracy, choosability, and edge count” (arXiv:1708.05152) is a conference-paper version of an earlier post here, which showed that the triangle-free penny graphs are 2-degenerate. The main article is short but also expands on a comment I made on that post, a bound on the largest possible number of edges in these graphs that is close to the known lower bound. In an appendix, I also included material from two later posts here: some analogous results for squaregraphs, and a counterexample showing that the same results do not extend to arbitrary 2-degenerate triangle-free planar graphs.

  • “The effect of planarization on width” (arXiv:1708.05155) is an extended version of my answer to a cstheory question by Bart Jansen. Bart asked whether it is possible to draw and then replace every crossing by a vertex, in such a way that the resulting planar graph has low pathwidth. The answer is no: every planarization of a drawing of has pathwidth . The proof idea from that answer turns out to generalize to treewidth as well as pathwidth, and I also looked at the same question for many other graph width parameters. Some of these parameters behave like treewidth and pathwidth, blowing up when you planarize even as simple a graph as , while others stay bounded when you planarize a bounded-width graph. Here’s one of the figures from the planarization paper, a carving decomposition of and its planarization:

Carving decomposition of K_{3,3} and its planarization

Graph Drawing has a policy of maintaining a shadow proceedings on, with the same content as the official proceedings, so I think we should be seeing quite a few more of these from other authors as the early-September proceedings deadline approaches.


by David Eppstein at August 17, 2017 10:42 PM UTC

A topical look at Norbert Blum’s paper and wider thoughts.

Cropped from source

Thales of Miletus may—or may not—have accurately predicted one or more total solar eclipses in the years 585 through 581 BCE.

Today we discuss the nature of science viewed from mathematics and computing. A serious claim of {\mathsf{NP \neq P}} by Norbert Blum has shot in front of what we were planning to say about next Monday’s total solar eclipse in the US.

Predicting eclipses is often hailed as an awakening of scientific method, one using mathematics both to infer solar and lunar cycles and for geometrical analysis. The aspects of science that we want to talk about are not “The Scientific Method” as commonly expounded in step-by-step fashion but rather the nature of scientific knowledge and human pursuits of it. We start with an observation drawn from a recent article in the Washington Post.

Despite several thousand years of experience predicting eclipses and our possession of GPS devices able to determine locations to an accuracy of several feet, we still cannot predict the zone of totality any closer than a mile.

The reason is not any fault on Earth but with the Sun: it bellows chaotically and for all we know a swell may nip its surface yea-far above the lunar disk at any time. Keeping open even a sliver of the nuclear furnace changes the character of the experience.

The Post’s article does a public service of telling people living on the edge of the swath not to think it is a sharp OFF/ON like a Boolean circuit gate. People must not always expect total sharpness from science. Happily there is a second point: you don’t have to drive very far to get a generous dose of totality. This is simply because as you move from the edge of a circle toward the center, the left-to-right breadth of the interior grows initially very quickly. This is our metaphor for how science becomes thick and solid quickly after we transit the time of being on its edge.

Incidentally, your GLL folks will be in the state of New York next week, nowhere near the swath. Next time in Buffalo. Also incidentally, Thales is said to be the first person credited with discovering mathematical theorems, namely that a triangle made by a circle’s diameter and another point on the circle is a right triangle and that lengths of certain intersecting line segments are proportional.

Norbert Blum’s Paper

The transit time is our focus on this blog: the experience of doing research amid inspirations and traps and tricks and gleams and uncertainty. Swaths of our community are experiencing another transit right now.

Norbert Blum has claimed a proof that P is not equal to NP. In his pedigree is holding the record for a concrete general Boolean circuit lower bound over the full binary basis for over 30 years—until it was recently nudged from his {3n} to {3.0116n.} His paper passes many filters of seriousness, including his saying how his proof surmounts known barriers. Ken and I want to know what we all want to know: is the proof correct?

More generally, even if the proof is flawed, does it contain new ideas that may be useful in the future? Blum’s proof claims a very strong lower bound of {2^{\Omega(N^{1/6})}} on the circuit complexity of whether a graph of {N} edges has a clique of size {N^{1/3}}. He gets a lower bound of {2^{\tilde{\Omega}(N^{1/4})} } for another function, where the tilde means up to factors of {\log N} in the exponent. We would be excited if he had even proved that this function has a super-linear Boolean complexity.

Blum’s insight is that the approximation methods used in monotone complexity on the clique function can be generalized to non-monotone complexity. It is launched by technical improvements to these methods in a 1999 paper by Christer Berg and Staffan Ulfberg. This is the very high level of what he tries to do, and is the one thing that we wish to comment on.

The Structure Of The Proof

Looking quickly at the 38 page argument an issue arose in our minds. We thought we would share this issue. It is not a flaw, it is an issue that we think needs to be thought about more expressly.

As we understand his proof it takes a boolean circuit for some monotone function {f} and places it in some topological order. Let this be

\displaystyle g_{1},g_{2},\dots,g_{m}.

So far nothing unreasonable. Note {g_{m}} is equal to {f}, of course. Then it seems that he uses an induction on the steps of the computation. Let {I_{k}} be the information that he gathers from the first {k} steps. Technically {I_{k}} tells us something about the computation so far. The punch line is then that {I_{m}} tells us something impossible about {g_{m}} which is of course {f}. Wonderful. This implies the claimed lower bound on {f} which solves the {\mathsf{NP \neq P}} question.

The Issue

The trouble with this is the following—we studied this before and it is called the “bait and switch” problem. Let {r} be some random function of polynomial Boolean complexity and let {s=r \oplus f}. Then assume that there is a polynomial size circuit for {f}. Clearly there is one for {r} and {s} too. Create a circuit that mixes the computing of {r} and {s} in some random order. Let the last step of the circuit be take {r} and {s} and form {r \oplus s}, Note this computes {f}.

The key point is this:

No step of the computation along the way has anything obvious to do with {f}. Only at the very last step does {f} appear.

This means intuitively to us that an inductive argument that tries to compute information gate by gate is in trouble. How can the {I_{k}}‘s that the proof compute have any information about {f} during the induction? This is not a “flaw” but it does seem to be a serious issue.

If nothing else we need to understand how the information suddenly at the end unravels and reveals information about {f}. I think this issue is troubling—at least to us. It is important to note that this trick cannot seem to be applied to purely monotone computations, since the last step must be non-monotone—it must compute the {\oplus} function. The old post also notes a relation between the standard circuit complexity {C_{st}(f)} and the monotone complexity {C_m(L_f)} of a related function {L_f}.

The Outer Structure of the Proof

While we are grappling with the paper and writing these thoughts we are following an ongoing discussion on StackExchange and in comments to a post by Luca Trevisan, a post by John Baez, and a Hacker News thread, among several other places.

The paper has a relatively short “crunch” in its sections 5 and 6, pages 25–35. These follow a long section 4 describing and honing Berg and Uffberg’s work. What the latter did was show that a kind of circuit approximation obatined via small DNF formulas in Alexander Razborov’s famous lowerbound papers (see also these notes by Tim Gowers) can also be obtained with small CNF formulas. What strikes us is that Blum’s main theorem is literally a meta-theorem referencing this process:

Theorem 6: Let {f \in B_n} be any monotone Boolean function. Assume that there is a CNF-DNF-approximator {A} which can be used to prove a lower bound for {C_m(f)}. Then {A} can also be used to prove the same lower bound for {C_{st}(f)}.

The nub being discussed now is whether this theorem is “self-defeating” by its own generality. There may be cases of {f} that meet the hypotheses but have polynomial {C_{st}(f)}. The StackExchange thread is discussing this for functions {f_k} of Boolean strings denoting {m}-node {N}-edge graphs that give value {1} whenever the graph is a {k}-clique (with no other edges) and {0} when it is a complete {(k-1)}-partite graph. Some such functions related to the theta function of László Lovász (see also “Theorem 1” in this post for context) have polynomial complexity, meet the conditions of Razborov’s method, and don’t appear to obstruct Berg and Uffberg’s construction as used by Blum. But if they go through there, and if Blum’s further constructions using an inductively defined function {R} would go through transparently, then there must be an error.

Inner Issues and Calculating

The details of {R} in section 5 have also been called into question. We are unsure what to say about a claim by Gustav Nordh that carrying out the inductive construction as written yields a false conclusion that the monomial {x} is an implicant of a formula equivalent to {x \wedge y}. There are also comments about unclarity of neighboring definitions, including this from Shachar Lovett in Luca’s blog since we drafted this section.

But this leads us to a larger point. Both of us are involved right now with painstaking constructions involving quantum circuits and products of permutations that we are programming (in Python). Pages 27–28 of Blum’s paper give a construction that can be programmed. If this is done enough to crank out some examples, then we may verify that potential flaws crop up or alternatively bolster confidence in junctures of the proof so as to focus on others first. This ability is one way we are now empowered to sharpen “fuzzy edges” of our science.

Open Problems

Is the proof correct? Or will it fall into eclipse? We will see shortly no doubt. Comparing this table of eclipses since 2003 and Gerhard Woeginger’s page of claimed proofs over mostly the same time period, we are struck that ‘{\mathsf{P\neq NP}}‘ and ‘{\mathsf{P=NP}}‘ claims have been about twice as frequent as lunar and solar eclipses, respectively.

[restored missing links; a few word and format changes]

by rjlipton at August 17, 2017 09:24 PM UTC

Next Fall I am teaching a special topics class in complexity theory. Below and here is the formal announcement, including a highly tentative list of topics. Some of the topics are somewhat ambitious, but that problem lies well in the future, concerning not me but my future self. He also appreciates suggestions and pointers of cool results to include.

Special topics in complexity theory


Emanuele Viola


Class 1:35 pm – 3:15 pm Tuesday Friday Ryder Hall 273.

First class Sep 08, 2017.

Running at the same time Program on Combinatorics and Complexity at Harvard.

Tentative syllabus

This class will present recent (amazing) progress in complexity theory and related areas. A highly tentative list of topics follows:

(1) Pseudorandom generators. Bounded independence, small-bias, sandwiching polynomials. Bounded independence fools And, bounded independence fools AC0 (Braverman’s result), the Gopalan-Kane-Meka inequality, the Gopalan-Meka-Reingold-Trevisan-Vadhan generator. Vadhan’s survey, Amnon Ta-Shma’s class

(2) Approximate degree. Bounded indistinguishability. Bounded indistinguishability of Or, And-Or, and Surjectivity (the Bun-Thaler proof)

(3) Circuit complexity. Williams’ lower bounds from satisfiability. Succinct and explicit NP-completeness. ACC0-SAT algorithms. Exposition in web appendix of Arora and Barak’s book.

(4) Quasi-random groups. Austin’s corner theorem in SL(2,q).

(5) Communication complexity and quasi-random groups. Determinism vs. randomization in number-on-forehead communication complexity. Number-in-hand lower bounds for quasi-random groups. Various notes.

(5) Data structures. Overview: static, dynamic, bit-probe, cell-probe. Siegel’s lower bound for hashing. The Larsen-Weinstein-Yu superlogarithmic lower bound.

(6) Arithmetic circuits. Overview. The chasm at depth 3. (The Gupta-Kamath-Kayal-Saptharishi result.) Shpilka and Yehudayoff’s survey Survey

(7) Fine-grained complexity reductions (SETH, 3SUM)


Each student will scribe #lectures/#students, and present a lecture. Grade is based on scribe, presentation, and class participation.

Scribes: due 72 hours from the time of the lecture. Feel free to send me a draft and ask for suggestions before the cutoff. Scribe templates: lyx, tex. Optionally, the lectures will be posted on my blog. Using this template minimizes the risk that my wordpress compiler won’t work.

Presentations: should convey both a high-level overview of the proof of the result, as well as a self-contained exposition of at least one step. Talk to me for suggestions. Discuss with me your presentation plan at least 1 week before your presentation.

Presentation papers:

Note: Always look if there is an updated version. Check the authors’ webpages as well as standard repositories (arxiv, ECCC, iacr, etc.)


Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes.

(Perhaps Avraham Ben-Aroya, Dean Doron and Amnon Ta-Shma. An efficient reduction from non-malleable extractors to two-source extractors, and explicit two-source extractors with near-logarithmic min-entropy.)

Prahladh Harsha, Srikanth Srinivasan: On Polynomial Approximations to AC0

SAT algorithms for depth-2 threshold circuits:

Here and here,

Quasirandom groups:

Higher-dimensional corners

Data structures:

Parts of Larsen-Weinstein-Yu superlogarithmic we left out.

Any of the many lower bounds we didn’t see.

Arithmetic circuit complexity:

Parts of the reduction we did not see.



Regularity lemmas:

TTV, Skorski

Fine-grained reductions:

Dynamic problems, LCS, edit distance.

There are many other reductions in this area.


  1. 2017-09-08 Fri
  2. 2017-09-12 Tue
  3. 2017-09-15 Fri
  4. 2017-09-19 Tue
  5. 2017-09-22 Fri
  6. 2017-09-26 Tue
  7. 2017-09-29 Fri
  8. 2017-10-03 Tue. Additive combinatorics workshop. NO CLASS
  9. 2017-10-06 Fri. Additive combinatorics workshop. NO CLASS
  10. 2017-10-10 Tue
  11. W-R Lectures by Gowers
  12. 2017-10-13 Fri
  13. 2017-10-17 Tue
  14. 2017-10-20 Fri
  15. 2017-10-24 Tue
  16. 2017-10-27 Fri
  17. 2017-10-31 Tue
  18. 2017-11-03 Fri
  19. 2017-11-07 Tue
  20. 2017-11-10 Fri
  21. 2017-11-14 Tue. Workshop. Class planned as usual, but check later
  22. 2017-11-17 Fri. Workshop. Class planned as usual, but check later
  23. 2017-11-21 Tue
  24. 2017-11-24 Fri. Thanksgiving, no classes.
  25. 2017-11-28 Tue
  26. 2017-12-01 Fri
  27. 2017-12-05 Tue
  28. 2017-12-08 Fri
  29. 2017-12-12 Tue
  30. 2017-12-15 Fri

by Manu at August 17, 2017 06:19 PM UTC

Andrew Tomkins and I cohosted the KDD 2017 panel on AI Assistants.  The panelists were Usama Fayyad, Larry Heck, Deepak Agarwal and Bing Liu, representing the spectrum from entreprenueral to academic including corporate research, in many cases individually.
  • For AI assistant technology today, talk about either a current success story, or a shortcoming in the market.   (Success story for "head", goal oriented bot: Siri, Alexa, Cortana, Google Assistant, DuerOS (Baidu), or Wechat bot Xiaoice  for chit-chat) Need:  The need by a broad set of companies for AI assistants is a given/assumed → broad engagement/interest by many companies to build/leverage AI assistant technology. 
  • "Help me plan a trip” versus “Connect me to my travel agent.”  Does user talk with one “butler” agent versus many specialized agents?  Follow-on:  What critical standards are required to enable assistants to operate effectively across multiple sensory domains?  How are we doing at developing these standards?
  • What implications will artificially intelligent assistants have for teens?  How about in the workplace?  Follow-on:  what are the expectations for task-focused versus chit-chat assistants?
  • How should a user be able to empower AI assistants to operate on the user’s behalf?
    1. “I’m sorry, Joe’s not available right now.”
    2. “I booked the show you wanted.  It’s 7:30 tonight.”
    3. “I found a great date for you this Saturday night.  Dress nice.”
    4. BTW, I bought you a house.
  •  What are research bottlenecks? (Dialogue understanding and large scale availability of suitable data, information elicitation methods, classical AI open issues like common sense reasoning, etc.) 
  • What role should assistants take in your life?
    1. Servant: does as you say
    2. Friend: emotional support
    3. Mentor/therapist: provides guidance
    4. Psychological role: assistant as id, ego, super-ego
    5. Deity: superhuman being with power over your fortunes, lead a way even if we dont see the rationale or even punish.
  • You can only optimize what you can measure.  For these different roles of an assistant, what are the right metrics?  
  • If assistant is built by multiple companies loosely cooperating and employing black-box learning techniques, why would its goals be perfectly aligned with yours?  What goals should we expect?
  • Could there be an assistant for your pet, wild animals and plants?
  • Which portrayal of AI assistants from literature or film do you find most compelling?
  • What is needed to unleash a technological ecosystem around AI assistants and what are the challenges? 
  • Last question to conclude the discussion: 1 prediction for the future of artificially intelligent assistants that you would like to be correct about and 1 that you wish you were wrong about. 
There was a lively discussion with people wondering about the implication of AI assistants among other things. 

In parallel, we had the following ads shown on the screen: 
  • Do you want to make $1000 a week from the comfort of your home? Get
  • Save AI-Assistant lives! Get
  • Are you bored as a parent? Wait for
  • Do you want someone to do award-winning research for you? Get
  • Need VC funding? Get

by metoo ( at August 17, 2017 04:30 PM UTC

I wanted to address diversity after the Google memo controversy but that shouldn't come from an old white man. I asked my daughter Molly, a college student trying to set her course, to give her thoughts.

The world is not for me. It never has been, and it never will be. This truth is bleak, but unavoidable. The world does not belong to women.

The possibilities for my life are not endless. The achievements in my sight are not mine to take. If I want them, I have to fight harder, prove more about myself, please people more, defy more first impressions. I’ll have to be smarter, stronger, more patient and more assertive. Every expectation of me has a mirror opposite, fracturing my success into a thing of paradoxes. I know this, and I’ve always known it, to some extent. As I get older, the more I learn and the more I educate myself, the more words I have to describe it.

So you’ll forgive me for not being surprised that sexism exists, especially in such male-dominated fields as technology and computing. You’ll forgive me for calling it out by name, and trying to point it out to those I care about. You’ll forgive me for being scared of tech jobs, so built by and for white men and controlled by them that the likelihood of a woman making a difference is almost none. And you’ll forgive me for trying to speak my mind and demand what I deserve, instead of living up to the natural state of my more “agreeable” gender.

I know this disparity is temporary. I know these fields could not have come nearly as far as they have come without the contributions of many extraordinary women who worked hard to push us into the future. I know that other fields that once believed women were simply incapable of participating are now thriving in the leadership of the very women who defied those odds. And I know, with all of my being, that the world moves forward, whether or not individuals choose to accept it.

I’m so fortunate to live the life I do, and to have the opportunities I have. This is not lost on me. But neither is the understanding that this world was not built for me, and still won’t have been built for me even when the tech world is ruled by the intelligent women who should already be in charge of it. The existence of people who believe genders to be inherently different will always exist, always perpetuate the system that attaches lead weights to my limbs, padlocks to my mouth.

But that doesn’t mean I’ll give up. It’s what women do, because it’s what we have to do, every day of our lives: we defy the odds. We overcome. The future includes us in it, as it always has, and it’s because of the women who didn’t give up. And I’ll be proud to say I was one of them.

by Lance Fortnow ( at August 17, 2017 03:28 PM UTC

Authors: Jeremy F. Alm, Andrew Ylvisaker
Download: PDF
Abstract: Proper relation algebras can be constructed using $\mathbb{Z}/p\mathbb{Z}$ as a base set using a method due to Comer. The cycle structure of such an algebra must, in general, be determined \emph{a posteriori}, normally with the aid of a computer. In this paper, we give an improved algorithm for checking the cycle structure that reduces the time complexity from $\mathcal{O}(p^2)$ to $\mathcal{O}(p)$.

at August 17, 2017 12:48 AM UTC

Authors: Alan Frieze, Samantha Petti
Download: PDF
Abstract: We consider the allocation problem in which $m \leq (1-\epsilon) dn $ items are to be allocated to $n$ bins with capacity $d$. The items $x_1,x_2,\ldots,x_m$ arrive sequentially and when item $x_i$ arrives it is given two possible bin locations $p_i=h_1(x_i),q_i=h_2(x_i)$ via hash functions $h_1,h_2$. We consider a random walk procedure for inserting items and show that the expected time insertion time is constant provided $\epsilon = \Omega\left(\sqrt{ \frac{ \log d}{d}} \right).$

at August 17, 2017 12:47 AM UTC

Authors: Colin Cooper, Alan Frieze, Samantha Petti
Download: PDF
Abstract: We analyze the covertime of a biased random walk on the random graph $G_{n,p}$. The walk is biased towards visiting vertices of low degree and this makes the covertime less than in the unbiased case

at August 17, 2017 12:46 AM UTC

Authors: Nguyen Kim Thang
Download: PDF
Abstract: Non-linear, especially convex, objective functions have been extensively studied in recent years in which approaches relies crucially on the convexity property of cost functions. In this paper, we present primal-dual approaches based on configuration linear programs to design competitive online algorithms for problems with arbitrarily-grown objective. This approach is particularly appropriate for non-linear (non-convex) objectives in online setting.

We first present a simple greedy algorithm for a general cost-minimization problem. The competitive ratio of the algorithm is characterized by the mean of a notion, called smoothness, which is inspired by a similar concept in the context of algorithmic game theory. The algorithm gives optimal (up to a constant factor) competitive ratios while applying to different contexts such as network routing, vector scheduling, energy-efficient scheduling and non-convex facility location.

Next, we consider the online $0-1$ covering problems with non-convex objective. Building upon the resilient ideas from the primal-dual framework with configuration LPs, we derive a competitive algorithm for these problems. Our result generalizes the online primal-dual algorithm developed recently by Azar et al. for convex objectives with monotone gradients to non-convex objectives. The competitive ratio is now characterized by a new concept, called local smoothness --- a notion inspired by the smoothness. Our algorithm yields tight competitive ratio for the objectives such as the sum of $\ell_{k}$-norms and gives competitive solutions for online problems of submodular minimization and some natural non-convex minimization under covering constraints.

at August 17, 2017 12:41 AM UTC

Authors: Orgad Keller, Avinatan Hassidim, Noam Hazon
Download: PDF
Abstract: We study the problem of coalitional manipulation---where $k$ manipulators try to manipulate an election on $m$ candidates---under general scoring rules, with a focus on the Borda protocol. We do so both in the weighted and unweighted settings. We focus on minimizing the maximum score obtainable by a non-preferred candidate.

In the strongest, most general setting, we provide an algorithm for any scoring rule as described by a vector $\vec{\alpha}=(\alpha_1,\ldots,\alpha_m)$: for some $\beta=O(\sqrt{m\log m})$, it obtains an additive approximation equal to $W\cdot \max_i \lvert \alpha_{i+\beta}-\alpha_i \rvert$, where $W$ is the sum of voter weights.

For Borda, both the weighted and unweighted variants are known to be $NP$-hard. For the unweighted case, our simpler algorithm provides a randomized, additive $O(k \sqrt{m \log m} )$ approximation; in other words, if there exists a strategy enabling the preferred candidate to win by an $\Omega(k \sqrt{m \log m} )$ margin, our method, with high probability, will find a strategy enabling her to win (albeit with a possibly smaller margin). It thus provides a somewhat stronger guarantee compared to the previous methods, which implicitly implied a strategy that provides an $\Omega(m)$-additive approximation to the maximum score of a non-preferred candidate.

For the weighted case, our generalized algorithm provides an $O(W \sqrt{m \log m} )$-additive approximation, where $W$ is the sum of voter weights. This is a clear advantage over previous methods: some of them do not generalize to the weighted case, while others---which approximate the number of manipulators---pose restrictions on the weights of extra manipulators added.

Our methods are based on carefully rounding an exponentially-large configuration linear program that is solved by using the ellipsoid method with an efficient separation oracle.

at August 17, 2017 12:47 AM UTC

Authors: Quentin Mérigot, Jocelyn Meyron, Boris Thibert
Download: PDF
Abstract: We present in this paper a generic and parameter-free algorithm to efficiently build a wide variety of optical components, such as mirrors or lenses, that satisfy some light energy constraints. In all of our problems, one is given a collimated or point light source and a desired illumination after reflection or refraction and the goal is to design the geometry of a mirror or lens which transports exactly the light emitted by the source onto the target. We first propose a general framework and show that eight different optical component design problems amount to solving a Light Energy Conservation equation that involves the computation of Visibility diagrams. We show that these diagrams all have the same structure and can be obtained by intersecting a 3D Power Diagram with a planar or spherical domain. This allows us to propose an efficient and fully generic algorithm capable to solve the eight optical component design problems. Our solutions can satisfy design constraints such as convexity or concavity and are always graphs over the plane or the sphere. We show the effectiveness of our algorithm on numerous simulated examples.

at August 17, 2017 12:48 AM UTC

Authors: Vida Dujmović, David R. Wood
Download: PDF
Abstract: This paper studies questions about duality between crossings and non-crossings in graph drawings via the notions of thickness and antithickness. The "thickness' of a graph $G$ is the minimum integer $k$ such that in some drawing of $G$, the edges can be partitioned into $k$ noncrossing subgraphs. The "antithickness" of a graph $G$ is the minimum integer $k$ such that in some drawing of $G$, the edges can be partitioned into $k$ thrackles, where a "thrackle" is a set of edges, each pair of which intersect exactly once. So thickness is a measure of how close a graph is to being planar, whereas antithickness is a measure of how close a graph is to being a thrackle. This paper explores the relationship between the thickness and antithickness of a graph, under various graph drawing models, with an emphasis on extremal questions.

at August 17, 2017 12:48 AM UTC

Authors: Ken-ichi Kawarabayashi, Anastasios Sidiropoulos
Download: PDF
Abstract: In the minimum planarization problem, given some $n$-vertex graph, the goal is to find a set of vertices of minimum cardinality whose removal leaves a planar graph. This is a fundamental problem in topological graph theory. We present a $\log^{O(1)} n$-approximation algorithm for this problem on general graphs with running time $n^{O(\log n/\log\log n)}$. We also obtain a $O(n^\varepsilon)$-approximation with running time $n^{O(1/\varepsilon)}$ for any arbitrarily small constant $\varepsilon > 0$. Prior to our work, no non-trivial algorithm was known for this problem on general graphs, and the best known result even on graphs of bounded degree was a $n^{\Omega(1)}$-approximation [Chekuri and Sidiropoulos 2013].

As an immediate corollary, we also obtain improved approximation algorithms for the crossing number problem on graphs of bounded degree. Specifically, we obtain $O(n^{1/2+\varepsilon})$-approximation and $n^{1/2} \log^{O(1)} n$-approximation algorithms in time $n^{O(1/\varepsilon)}$ and $n^{O(\log n/\log\log n)}$ respectively. The previously best-known result was a polynomial-time $n^{9/10}\log^{O(1)} n$-approximation algorithm [Chuzhoy 2011].

Our algorithm introduces several new tools including an efficient grid-minor construction for apex graphs, and a new method for computing irrelevant vertices. Analogues of these tools were previously available only for exact algorithms. Our work gives efficient implementations of these ideas in the setting of approximation algorithms, which could be of independent interest.

at August 17, 2017 12:42 AM UTC

Authors: Trajan Hammonds, Jeremy Johnson, Angela Patini, Robert M. Walker
Download: PDF
Abstract: Until recently, the only known method of finding the roots of polynomials over prime power rings, other than fields, was brute force. One reason for this is the lack of a division algorithm, obstructing the use of greatest common divisors. Fix a prime $p \in \mathbb{Z}$ and $f \in ( \mathbb{Z}/p^n \mathbb{Z} ) [x]$ any nonzero polynomial of degree $d$ whose coefficients are not all divisible by $p$. For the case $n=2$, we prove a new efficient algorithm to count the roots of $f$ in $\mathbb{Z}/p^2\mathbb{Z}$ within time polynomial in $(d+\operatorname{size}(f)+\log{p})$, and record a concise formula for the number of roots, formulated by Cheng, Gao, Rojas, and Wan.

at August 17, 2017 12:40 AM UTC

Authors: Tuğkan Batu, Clément L. Canonne
Download: PDF
Abstract: In this work, we revisit the problem of uniformity testing of discrete probability distributions. A fundamental problem in distribution testing, testing uniformity over a known domain has been addressed over a significant line of works, and is by now fully understood.

The complexity of deciding whether an unknown distribution is uniform over its unknown (and arbitrary) support, however, is much less clear. Yet, this task arises as soon as no prior knowledge on the domain is available, or whenever the samples originate from an unknown and unstructured universe. In this work, we introduce and study this generalized uniformity testing question, and establish nearly tight upper and lower bound showing that -- quite surprisingly -- its sample complexity significantly differs from the known-domain case. Moreover, our algorithm is intrinsically adaptive, in contrast to the overwhelming majority of known distribution testing algorithms.

at August 17, 2017 12:47 AM UTC

Authors: Jack Murtagh, Omer Reingold, Aaron Sidford, Salil Vadhan
Download: PDF
Abstract: We give a deterministic $\tilde{O}(\log n)$-space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating hitting times, commute times, and escape probabilities for undirected graphs. Previously, such systems were known to be solvable by randomized algorithms using $O(\log n)$ space (Doron, Le Gall, and Ta-Shma, 2017) and hence by deterministic algorithms using $O(\log^{3/2} n)$ space (Saks and Zhou, FOCS 1995 and JCSS 1999).

Our algorithm combines ideas from time-efficient Laplacian solvers (Spielman and Teng, STOC `04; Peng and Spielman, STOC `14) with ideas used to show that Undirected S-T Connectivity is in deterministic logspace (Reingold, STOC `05 and JACM `08; Rozenman and Vadhan, RANDOM `05).

at August 17, 2017 12:40 AM UTC

Authors: Faez Ahmed, John P. Dickerson, Mark Fuge
Download: PDF
Abstract: Bipartite matching, where agents on one side of a market are matched to agents or items on the other, is a classical problem in computer science and economics, with widespread application in healthcare, education, advertising, and general resource allocation. A practitioner's goal is typically to maximize a matching market's economic efficiency, possibly subject to some fairness requirements that promote equal access to resources. A natural balancing act exists between fairness and efficiency in matching markets, and has been the subject of much research.

In this paper, we study a complementary goal---balancing diversity and efficiency---in a generalization of bipartite matching where agents on one side of the market can be matched to sets of agents on the other. Adapting a classical definition of the diversity of a set, we propose a quadratic programming-based approach to solving a supermodular minimization problem that balances diversity and total weight of the solution. We also provide a scalable greedy algorithm with theoretical performance bounds. We then define the price of diversity, a measure of the efficiency loss due to enforcing diversity, and give a worst-case theoretical bound. Finally, we demonstrate the efficacy of our methods on three real-world datasets, and show that the price of diversity is not bad in practice.

at August 17, 2017 12:47 AM UTC

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.

by Boaz Barak at August 16, 2017 08:35 AM UTC

Edited 8/16 to correct attributions to Alon and Boppana and to Tardos, thanks to an anonymous commenter for the correction

Yesterday, Norbert Blum posted a preprint with a claimed proof that {P\neq NP}. An incorrect comment that I made last night and corrected this morning caused a lot of confusion, so let me apologize by summarizing the claims in the paper.

Coincidentally, this week, there is an Oberwolfach workshop on proof complexity and circuit complexity, so I am confident that by the end of the week we will hear substantive comments on the technical claims in the paper.

Recall that if a decision problem is solvable by an algorithm running in time {t(n)} on inputs of length {n} then, for every {n}, it is also solved, on inputs of length {n}, by a circuit of size {O(t^2(n))}. Thus, if a problem is solvable in polynomial time it is also solvable by a family of polynomial size circuits (or, in short, it has polynomial circuit complexity).

The paper claims that Clique has exponential circuit complexity, and hence it has no polynomial time algorithm and {P\neq NP}. The argument leverages known results from monotone circuit complexity.

A monotone circuit is a boolean circuit that has only AND gates and OR gates, but does not have any NOT gates. A decision problem is a monotone problem if, for every fixed input length, it is solvable by a monotone circuit. For example, the problem to decide if a given {n}-vertex graph has a clique of size at least {\sqrt n} is a monotone problem (if the input graph is presented as a boolean adjacency matrix), and so is the problem of deciding if a given graph has a perfect matching.

In the 1980s, Razborov proved that Clique cannot be computed by polynomial size monotone circuits. Later Andreev proved that there is a monotone problem in NP that requires exponential size monotone circuits, and Tardos Alon and Boppana proved that Clique itself requires exponential size monotone circuits. At the time, it was conjectured that if a monotone problem is in P, then it is solvable by a family of polynomial size monotone circuits. Under this conjecture, Razborov’s result would imply that Clique is not in P, and hence {P\neq NP}.

Unfortunately, Razborov refuted this conjecture, by showing that the perfect matching problem, which is in P, does not have polynomial size monotone circuits. Tardos showed that the Alon-Boppana exponential lower bound for clique holds for any monotone function sandwiched between the clique number and the chromatic number of a graph, including the Lovasz Theta function. Since the Theta function is polynomial time computable, and hence has polynomial size circuits, this shows that the gap between monotone circuit complexity and general circuit complexity can be exponentially large. (See first comment below.)

Razborov’s proof of the Clique lower bound for monotone circuits introduced the powerful approximation method. Roughly speaking, his approach was to start from a hypothetical polynomial size family of monotone circuits for Clique, and, from that, build a family of approximating circuits, which are just DNF formulas. The approximating circuits constructed by his method do not solve the Clique problem in general, but they solve a “promise” version of the problem, that is, they solve Clique on a certain subset of graphs. Then Razborov finishes the argument by showing that the approximating circuits are so simple that it is impossible for them to even solve Clique on that subset of inputs, thus reaching a contradiction to the assumption that there are monotone polynomial size circuits for Clique. The approximation method, variously modified, was also used to prove the lower bounds for Andreev’s problem and for matching.

Tim Gowers wrote a wonderful exposition of Razborov’s method, trying to show how one would come up with the various ideas, rather than just presenting the proof step by step.

Berg and Ulfberg simplify the proofs of Razborov, Andreev and Tardos for Clique and Andreev’s problem (but not for matching) by showing how to construct an approximator that has both small DNF complexity and small CNF complexity. The stronger claim makes an inductive argument in the construction easier to establish.

(At this point, I should clarify that I have never properly studies these results, so I am probably getting some details wrong. Please post corrections in the comments.)

The main claim in Blum’s paper is Theorem 6, which claims that if polynomial-size monotone circuits for a monotone problem admit a “CNF-DNF approximator” for a promise restriction of the problem (like the Berg-Ulfberg one), then also general circuits for the same problem admit such an approximator. Thus, if the approximator does not exist, it not only follows that the monotone complexity of the problem is super-polynomial, but also the general circuit complexity of the problem is superpolynomial.

Together with the Berg-Ulfberg approximator for monotone circuits for Clique, this implies that Clique is not in P.

Now, what could possibly go wrong with this argument?

  • What about natural proofs?

    This argument can only applied to (certain) monotone problems, and monotone problems are a vanishing fraction of all problems, hence one does not have the “largeness” property of natural proofs, and the argument is not a natural proof. (This is noted in the paper.)

  • What about relativization and algebrization?

    The argument starts from a boolean circuit for a given problem. If one is given an oracle circuit, with gates that answer oracle queries, or give evaluation of a polynomial extension of the problem, the argument cannot be applied.

  • But this argument is lifting monotone circuit lower bounds to general circuit lower bounds, and so what about perfect matching, which has an exponential monotone circuit lower bound and a polynomial general circuit upper bound?

    It is not known how to make the known lower bound for matching work via a “CNF-DNF approximator” and the claims in the paper only concern monotone lower bounds proved in this way. (Edited to add: but what about the Lovasz theta function?)

  • But didn’t Razborov prove that the approximation method cannot prove a better-than-quadratic lower bound for general circuits?

    Like any no-go theorem, Razborov’s impossibility result makes some assumption on what it means to “apply the approximation method to general circuits” and Blum claims that the assumptions do not apply to his argument.

  • But where is the “heavy lifting” done? Shouldn’t every proof of a major result have one or more steps that are unlike anything done before?

    I don’t have a good answer to this question. All the work is done in the proof of Theorem 6, which is the construction of the approximator starting from an arbitrary circuit. Maybe the argument is right and the heavy lifting was in Razborov’s work and subsequent extension and simplifications, and the fact that one can handle NOT gates at the bottom can be handled with an argument that is syntactically similar to previous work. Or, something goes wrong in the construction. Either way we will probably know soon.

by luca at August 16, 2017 05:18 AM UTC

Authors: Juling Zhang, Guowu Yang, William N. N. Hung, Yan Zhang
Download: PDF
Abstract: An efficient pairwise Boolean matching algorithm to solve the problem of matching single-output specified Boolean functions under input negation and/or input permutation and/or output negation (NPN) is proposed in this paper. We present the Structural Signature (SS) vector, which is composed of a 1st signature value, two symmetry marks, and a group mark. As a necessary condition for NPN Boolean matching, the structural signature is more effective than is the traditional signature. Two Boolean functions, f and g, may be equivalent when they have the same SS vector. The symmetry mark can distinguish symmetric variables and asymmetric variables and search multiple variable mappings in a single variable-mapping search operation, which reduces the search space significantly. Updating the SS vector using Shannon decomposition provides benefits in distinguishing unidentified variables, and the group mark and the phase collision check discover incorrect variable mappings quickly, which also speeds up the NPN Boolean matching process. Using the algorithm proposed in this paper, we tested both equivalent and non-equivalent matching peeds on the MCNC benchmark circuit sets and the random circuit sets. In the experiment, our algorithm is two times faster than competitors when testing equivalent circuits and averages at least one hundred times faster when testing non-equivalent circuits. The experimental results show that our approach is highly effective in solving the NPN Boolean matching problem.

at August 16, 2017 01:27 AM UTC

Authors: Lars Jaffke, O-joung Kwon, Jan Arne Telle
Download: PDF
Abstract: We give the first polynomial-time algorithms on graphs of bounded maximum induced matching width (mim-width) for problems that are not locally checkable. In particular, we give $n^{\mathcal{O}(w)}$-time algorithms on graphs of mim-width at most $w$, when given a decomposition, for the following problems: Longest Induced Path, Induced Disjoint Paths and $H$-Induced Topological Minor for fixed $H$. Our results imply that the following graph classes have polynomial-time algorithms for these three problems: Interval and Bi-Interval graphs, Circular Arc, Permutation and Circular Permutation graphs, Convex graphs, $k$-Trapezoid, Circular $k$-Trapezoid, $k$-Polygon, Dilworth-$k$ and Co-$k$-Degenerate graphs for fixed $k$.

at August 16, 2017 12:00 AM UTC

Authors: Yinan Li, Youming Qiao
Download: PDF
Abstract: A classical difficult isomorphism testing problem is to test isomorphism of p-groups of class 2 and exponent p in time polynomial in the group order. It is known that this problem can be reduced to solving the alternating matrix space isometry problem over a finite field in time polynomial in the underlying vector space size. We propose a venue of attack for the latter problem by viewing it as a linear algebraic analogue of the graph isomorphism problem. This viewpoint leads us to explore the possibility of transferring techniques for graph isomorphism to this long-believed bottleneck case of group isomorphism.

In 1970's, Babai, Erd\H{o}s, and Selkow presented the first average-case efficient graph isomorphism testing algorithm (SIAM J Computing, 1980). Inspired by that algorithm, we devise an average-case efficient algorithm for the alternating matrix space isometry problem over a key range of parameters, in a random model of alternating matrix spaces in vein of the Erd\H{o}s-R\'enyi model of random graphs. For this, we develop a linear algebraic analogue of the classical individualisation technique, a technique belonging to a set of combinatorial techniques that has been critical for the progress on the worst-case time complexity for graph isomorphism, but was missing in the group isomorphism context. This algorithm also enables us to improve Higman's 57-year-old lower bound on the number of p-groups (Proc. of the LMS, 1960). We finally show that Luks' dynamic programming technique for graph isomorphism (STOC 1999) can be adapted to slightly improve the worst-case time complexity of the alternating matrix space isometry problem in a certain range of parameters.

at August 16, 2017 12:00 AM UTC

Authors: Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
Download: PDF
Abstract: We study the problem of finding all $k$-periods of a length-$n$ string $S$, presented as a data stream. $S$ is said to have $k$-period $p$ if its prefix of length $n-p$ differs from its suffix of length $n-p$ in at most $k$ locations.

We give a one-pass streaming algorithm that computes the $k$-periods of a string $S$ using $\text{poly}(k, \log n)$ bits of space, for $k$-periods of length at most $\frac{n}{2}$. We also present a two-pass streaming algorithm that computes $k$-periods of $S$ using $\text{poly}(k, \log n)$ bits of space, regardless of period length. We complement these results with comparable lower bounds.

at August 16, 2017 12:00 AM UTC

Authors: Shashwat Garg
Download: PDF
Abstract: A central problem in scheduling is to schedule $n$ unit size jobs with precedence constraints on $m$ identical machines so as to minimize the makespan. For $m=3$, it is not even known if the problem is NP-hard and this is one of the last open problems from the book of Garey and Johnson.

We show that for fixed $m$ and $\epsilon$, $(\log n)^{O(1)}$ rounds of Sherali-Adams hierarchy applied to a natural LP of the problem provides a $(1+\epsilon)$-approximation algorithm running in quasi-polynomial time. This improves over the recent result of Levey and Rothvoss, who used $r=(\log n)^{O(\log \log n)}$ rounds of Sherali-Adams in order to get a $(1+\epsilon)$-approximation algorithm with a running time of $n^{O(r)}$.

at August 16, 2017 12:00 AM UTC

Authors: Adib Hassan, Po-Chien Chung, Wayne B. Hayes
Download: PDF
Abstract: Graphlets are small connected induced subgraphs of a larger graph $G$. Graphlets are now commonly used to quantify local and global topology of networks in the field. Methods exist to exhaustively enumerate all graphlets (and their orbits) in large networks as efficiently as possible using orbit counting equations. However, the number of graphlets in $G$ is exponential in both the number of nodes and edges in $G$. Enumerating them all is already unacceptably expensive on existing large networks, and the problem will only get worse as networks continue to grow in size and density. Here we introduce an efficient method designed to aid statistical sampling of graphlets up to size $k=8$ from a large network. We define graphettes as the generalization of graphlets allowing for disconnected graphlets. Given a particular (undirected) graphette $g$, we introduce the idea of the canonical graphette $\mathcal K(g)$ as a representative member of the isomorphism group $Iso(g)$ of $g$. We compute the mapping $\mathcal K$, in the form of a lookup table, from all $2^{k(k-1)/2}$ undirected graphettes $g$ of size $k\le 8$ to their canonical representatives $\mathcal K(g)$, as well as the permutation that transforms $g$ to $\mathcal K(g)$. We also compute all automorphism orbits for each canonical graphette. Thus, given any $k\le 8$ nodes in a graph $G$, we can in constant time infer which graphette it is, as well as which orbit each of the $k$ nodes belongs to. Sampling a large number $N$ of such $k$-sets of nodes provides an approximation of both the distribution of graphlets and orbits across $G$, and the orbit degree vector at each node.

at August 16, 2017 12:00 AM UTC

Authors: Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, Jara Uitto
Download: PDF
Abstract: The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree $\Delta$. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes.

1. We simplify the \emph{round elimination} technique of Brandt et al. and prove that $(2\Delta-2)$-edge coloring requires $\Omega(\log_\Delta \log n)$ time w.h.p. and $\Omega(\log_\Delta n)$ time deterministically, even on trees. The simplified technique is based on two ideas: the notion of an irregular running time and some general observations that transform weak lower bounds into stronger ones.

2. We give a randomized edge coloring algorithm that can use palette sizes as small as $\Delta + \tilde{O}(\sqrt{\Delta})$, which is a natural barrier for randomized approaches. The running time of the algorithm is at most $O(\log\Delta \cdot T_{LLL})$, where $T_{LLL}$ is the complexity of a permissive version of the constructive Lovasz local lemma.

3. We develop a new distributed Lovasz local lemma algorithm for tree-structured dependency graphs, which leads to a $(1+\epsilon)\Delta$-edge coloring algorithm for trees running in $O(\log\log n)$ time. This algorithm arises from two new results: a deterministic $O(\log n)$-time LLL algorithm for tree-structured instances, and a randomized $O(\log\log n)$-time graph shattering method for breaking the dependency graph into independent $O(\log n)$-size LLL instances.

4. A natural approach to computing $(\Delta+1)$-edge colorings (Vizing's theorem) is to extend partial colorings by iteratively re-coloring parts of the graph. We prove that this approach may be viable, but in the worst case requires recoloring subgraphs of diameter $\Omega(\Delta\log n)$. This stands in contrast to distributed algorithms for Brooks' theorem, which exploit the existence of $O(\log_\Delta n)$-length augmenting paths.

at August 16, 2017 12:00 AM UTC

by David Eppstein at August 15, 2017 09:56 PM UTC

Rao Kosaraju will be stepping down soon from his position as Director of the Division of Computing and Communication Foundations at NSF, after several years of terrific service.  The official job announcement for a new director was just posted.  This is an extremely important position — please consider applying!

by timroughgarden at August 15, 2017 07:08 PM UTC

The universal relation is the communication problem in which Alice and Bob get as inputs two distinct strings, and they are required to find a coordinate on which the strings differ. The study of this problem is motivated by its connection to Karchmer-Wigderson relations, which are communication problems that are tightly related to circuit-depth lower bounds. In this paper, we prove a direct sum theorem for the universal relation, namely, we prove that solving $m$ independent instances of the universal relation is $m$ times harder than solving a single instance. More specifically, it is known that the deterministic communication complexity of the universal relation is at least $n$. We prove that the deterministic communication complexity of solving $m$ independent instances of the universal relation is at least $m \cdot (n-O(\log m))$.

at August 15, 2017 05:37 PM UTC

Unrelated Update: To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the paper won’t stand, except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: please stop asking, and if the thing hasn’t been refuted by the end of the week, you can come back and tell me I was a closed-minded fool.

In my post “The Kolmogorov Option,” I tried to step back from current controversies, and use history to reflect on the broader question of how nerds should behave when their penchant for speaking unpopular truths collides head-on with their desire to be kind and decent and charitable, and to be judged as such by their culture.  I was gratified to get positive feedback about this approach from men and women all over the ideological spectrum.

However, a few people who I like and respect accused me of “dogwhistling.” They warned, in particular, that if I wouldn’t just come out and say what I thought about the James Damore Google memo thing, then people would assume the very worst—even though, of course, my friends themselves knew better.

So in this post, I’ll come out and say what I think.  But first, I’ll do something even better: I’ll hand the podium over to two friends, Sarah Constantin and Stacey Jeffery, both of whom were kind enough to email me detailed thoughts in response to my Kolmogorov post.

Sarah Constantin completed her PhD in math at Yale. I don’t think I’ve met her in person yet, but we have a huge number of mutual friends in the so-called “rationalist community.”  Whenever Sarah emails me about something I’ve written, I pay extremely close attention, because I have yet to read a single thing by her that wasn’t full of insight and good sense.  I strongly urge anyone who likes her beautiful essay below to check out her blog, which is called Otium.

Sarah Constantin’s Commentary:

I’ve had a women-in-STEM essay brewing in me for years, but I’ve been reluctant to actually write publicly on the topic for fear of stirring up a firestorm of controversy.  On the other hand, we seem to be at a cultural inflection point on the issue, especially in the wake of the leaked Google memo, and other people are already scared to speak out, so I think it’s past time for me to put my name on the line, and Scott has graciously provided me a platform to do so.

I’m a woman in tech myself. I’m a data scientist doing machine learning for drug discovery at Recursion Pharmaceuticals, and before that I was a data scientist at Palantir. Before that I was a woman in math — I got my PhD from Yale, studying applied harmonic analysis. I’ve been in this world all my adult life, and I obviously don’t believe my gender makes me unfit to do the work.

I’m also not under any misapprehension that I’m some sort of exception. I’ve been mentored by Ingrid Daubechies and Maryam Mirzakhani (the first female Fields Medalist, who died tragically young last month).  I’ve been lucky enough to work with women who are far, far better than me.  There are a lot of remarkable women in math and computer science — women just aren’t the majority in those fields. But “not the majority” doesn’t mean “rare” or “unknown.”

I even think diversity programs can be worthwhile. I went to the Institute for Advanced Studies’ Women and Math Program, which would be an excellent graduate summer school even if it weren’t all-female, and taught at its sister program for high school girls, which likewise is a great math camp independent of the gender angle. There’s a certain magic, if you’re in a male-dominated field, of once in a while being in a room full of women doing math, and I hope that everybody gets to have that experience once.  

But (you knew the “but” was coming), I think the Google memo was largely correct, and the way people conventionally talk about women in tech is wrong.

Let’s look at some of his claims. From the beginning of the memo:

  • Google’s political bias has equated the freedom from offense with psychological safety, but shaming into silence is the antithesis of psychological safety.
  • This silencing has created an ideological echo chamber where some ideas are too sacred to be honestly discussed.
  • The lack of discussion fosters the most extreme and authoritarian elements of this ideology.
  • Extreme: all disparities in representation are due to oppression
  • Authoritarian: we should discriminate to correct for this oppression

Okay, so there’s a pervasive assumption that any deviation from 50% representation of women in technical jobs is a.) due to oppression, and b.) ought to be corrected by differential hiring practices. I think it is basically true that people widely believe this, and that people can lose their jobs for openly contradicting it (as James Damore, the author of the memo, did).  I have heard people I work with advocating hiring quotas for women (i.e. explicitly earmarking a number of jobs for women candidates only).  It’s not a strawman.

Then, Damore disagrees with this assumption:

  • Differences in distributions of traits between men and women may in part explain why we don’t have 50% representation of women in tech and leadership. Discrimination to reach equal representation is unfair, divisive, and bad for business.

Again, I agree with Damore. Note that this doesn’t mean that I must believe that sexism against women isn’t real and important (I’ve heard enough horror stories to be confident that some work environments are toxic to women).  It doesn’t even mean that I must be certain that the different rates of men and women in technical fields are due to genetics.  I’m very far from certain, and I’m not an expert in psychology. I don’t think I can do justice to the science in this post, so I’m not going to cover the research literature.

But I do think it’s irresponsible to assume a priori that there are no innate sex differences that might explain what we see.  It’s an empirical matter, and a topic for research, not dogma.

Moreover, I think discrimination on the basis of sex to reach equal representation is unfair and unproductive.  It’s unfair, because it’s not meritocratic.  You’re not choosing the best human for the job regardless of gender.

I think women might actually benefit from companies giving genuine meritocracy a chance. “Blind” auditions (in which the evaluator doesn’t see the performer) gave women a better chance of landing orchestra jobs; apparently, orchestras were prejudiced against female musicians, and the blinding canceled out that prejudice. Google’s own research has actually shown that the single best predictor of work performance is a work sample — testing candidates with a small project similar to what they’d do on the job. Work samples are easy to anonymize to reduce gender bias, and they’re more effective than traditional interviews, where split-second first impressions usually decide who gets hired, but don’t correlate at all with job performance. A number of tech companies have switched to work samples as part of their interview process.  I used work samples myself when I was hiring for a startup, just because they seemed more accurate at predicting who’d be good at the job; entirely without intending to, I got a 50% gender ratio.  If you want to reduce gender bias in tech, it’s worth at least considering blinded hiring via work samples.

Moreover, thinking about “representation” in science and technology reflects underlying assumptions that I think are quite dangerous.

You expect interest groups to squabble over who gets a piece of the federal budget. In politics, people will band together in blocs, and try to get the biggest piece of the spoils they can.  “Women should get such-and-such a percent of tech jobs” sounds precisely like this kind of politicking; women are assumed to be a unified bloc who will vote together, and the focus is on what size chunk they can negotiate for themselves. If a tech job (or a university position) were a cushy sinecure, a ticket to privilege, and nothing more, you might reasonably ask “how come some people get more goodies than others? Isn’t meritocracy just an excuse to restrict the goodies to your preferred group?”

Again, this is not a strawman. Here’s one Vox response to the memo stating explicitly that she believes women are a unified bloc:

The manifesto’s sleight-of-hand delineation between “women, on average” and the actual living, breathing women who have had to work alongside this guy failed to reassure many of those women — and failed to reassure me. That’s because the manifesto’s author overestimated the extent to which women are willing to be turned against their own gender.

Speaking for myself, it doesn’t matter to me how soothingly a man coos that I’m not like most women, when those coos are accompanied by misogyny against most women. I am a woman. I do not stop being one during the parts of the day when I am practicing my craft. There can be no realistic chance of individual comfort for me in an environment where others in my demographic categories (or, really, any protected demographic categories) are subjected to skepticism and condescension.

She can’t be comfortable unless everybody in any protected demographic category — note that this is a legal, governmental category — is given the benefit of the doubt?  That’s a pretty collectivist commitment!

Or, look at Piper Harron, an assistant professor in math who blogged on the American Mathematical Society’s website that universities should simply “stop hiring white cis men”, and explicitly says “If you are on a hiring committee, and you are looking at applicants and you see a stellar white male applicant, think long and hard about whether your department needs another white man. You are not hiring a researching robot who will output papers from a dark closet. You are hiring an educator, a role model, a spokesperson, an advisor, a committee person … There is no objectivity. There is no meritocracy.”

Piper Harron reflects an extreme, of course, but she’s explicitly saying, on America’s major communication channel for and by mathematicians, that whether you get to work in math should not be based on whether you’re actually good at math. For her, it’s all politics.  Life itself is political, and therefore a zero-sum power struggle between groups.  

But most of us, male or female, didn’t fall in love with science and technology for that. Science is the mission to explore and understand our universe. Technology is the project of expanding human power to shape that universe. What we do towards those goals will live longer than any “protected demographic category”, any nation, any civilization.  We know how the Babylonians mapped the stars.

Women deserve an equal chance at a berth on the journey of exploration not because they form a political bloc but because some of them are discoverers and can contribute to the human mission.

Maybe, in a world corrupted by rent-seeking, the majority of well-paying jobs have some element of unearned privilege; perhaps almost all of us got at least part of our salaries by indirectly expropriating someone who had as good a right to it as us.

But that’s not a good thing, and that’s not what we hope for science and engineering to be, and I truly believe that this is not the inevitable fate of the human race — that we can only squabble over scraps, and never create.  

I’ve seen creation, and I’ve seen discovery. I know they’re real.

I care a lot more about whether my company achieves its goal of curing 100 rare diseases in 10 years than about the demographic makeup of our team.  We have an actual mission; we are trying to do something beyond collecting spoils.  

Do I rely on brilliant work by other women every day? I do. My respect for myself and my female colleagues is not incompatible with primarily caring about the mission.

Am I “turning against my own gender” because I see women as individuals first? I don’t think so. We’re half the human race, for Pete’s sake! We’re diverse. We disagree. We’re human.

When you think of “women-in-STEM” as a talking point on a political agenda, you mention Ada Lovelace and Grace Hopper in passing, and move on to talking about quotas.  When you think of women as individuals, you start to notice how many genuinely foundational advances were made by women — just in my own field of machine learning, Adele Cutler co-invented random forests, Corrina Cortes co-invented support vector machines, and Fei Fei Li created the famous ImageNet benchmark dataset that started a revolution in image recognition.

As a child, my favorite book was Carl Sagan’s Contact, a novel about Ellie Arroway, an astronomer loosely based on his wife Ann Druyan. The name is not an accident; like the title character in Sinclair Lewis’ Arrowsmith, Ellie is a truth-seeking scientist who battles corruption, anti-intellectualism, and blind prejudice.  Sexism is one of the challenges she faces, but the essence of her life is about wonder and curiosity. She’s what I’ve always tried to become.

I hope that, in seeking to encourage the world’s Ellies in science and technology, we remember why we’re doing that in the first place. I hope we remember humans are explorers.

Now let’s hear from another friend who wrote to me recently, and who has a slightly different take.  Stacey Jeffery is a quantum computing theorist at one of my favorite research centers, CWI in Amsterdam.  She completed her PhD at University of Waterloo, and has done wonderful work on quantum query complexity and other topics close to my heart.  When I was being viciously attacked in the comment-171 affair, Stacey was one of the first people to send me a note of support, and I’ve never forgotten it.

Stacey Jeffery’s Commentary

I don’t think Google was right to fire Damore. This makes me a minority among people with whom I have discussed this issue.  Hopefully some people come out in the comments in support of the other position, so it’s not just me presenting that view, but the main argument I encountered was that what he said just sounded way too sexist for Google to put up with.  I agree with part of that, it did sound sexist to me.  In fact it also sounded racist to me. But that’s not because he necessarily said anything actually sexist or actually racist, but because he said the kinds of things that you usually only hear from sexist people, and in particular, the kind of sexist people who are also racist.  I’m very unlikely to try to pursue further interaction with a person who says these kinds of things for those reasons, but I think firing him for what he said between the lines sets a very bad precedent.  It seems to me he was fired for associating himself with the wrong ideas, and it does feel a bit like certain subjects are not up for rational discussion.  If Google wants an open environment, where employees can feel safe discussing company policy, I don’t think this contributes to that.  If they want their employees, and the world, to think that they aim for diversity because it’s the most rational course of action to achieve their overall objectives, rather than because it serves some secret agenda, like maintaining a PC public image, then I don’t think they’ve served that cause either.  Personally, this irritates me the most, because I feel they have damaged the image for a cause I feel strongly about.

My position is independent of the validity of Damore’s attempt at scientific argument, which is outside my area of expertise.  I personally don’t think it’s very productive for non-social-scientists to take authoritative positions on social science issues, especially ones that appear to be controversial within the field (but I say this as a layperson).  This may include some of the other commentary in this blog post, which I have not yet read, and might even extend to Scott’s decision to comment on this issue at all (but this bridge was crossed in the previous blog post).  However, I think one of the reasons that many of us do this is that the burden of solving the problem of too few women in STEM is often placed on us.  Some people in STEM feel they are blamed for not being welcoming enough to women (in fact, in my specific field, it’s my experience that the majority of people are very sympathetic).  Many scientific funding applications even ask applicants how they plan to address the issue of diversity, as if they should be the ones to come up with a solution for this difficult problem that nobody knows the answer to, and is not even within their expertise.  So it’s not surprising when these same people start to think about and form opinions on these social science issues.  Obviously, we working in STEM have valuable insight into how we might encourage women to pursue STEM careers, and we should be pushed to think about this, but we don’t have all the answers (and maybe we should remember that the next time we consider authoring an authoritative memo on the subject).

Scott’s Mansplaining Commentary

I’m incredibly grateful to Sarah and Stacey for sharing their views.  Now it’s time for me to mansplain my own thoughts in light of what they said.  Let me start with a seven-point creed.

1. I believe that science and engineering, both in academia and in industry, benefit enormously from contributions from people of every ethnic background and gender identity.  This sort of university-president-style banality shouldn’t even need to be said, but in a world where the President of the US criticizes neo-Nazis only under extreme pressure from his own party, I suppose it does.

2. I believe that there’s no noticeable difference in average ability between men and women in STEM fields—or if there’s some small disparity, for all I know the advantage goes to women. I have enough Sheldon Cooper in me that, if this hadn’t been my experience, I’d probably let it slip that it hadn’t been, but it has been.  When I taught 6.045 (undergrad computability and complexity) at MIT, women were only 20% or so of the students, but for whatever reasons they were wildly overrepresented among the top students.

3. I believe that women in STEM face obstacles that men don’t.  These range from the sheer awkwardness of sometimes being the only woman in a room full of guys, to challenges related to pregnancy and childcare, to actual belittlement and harassment.  Note that, even if men in STEM fields are no more sexist on average than men in other fields—or are less sexist, as one might expect from their generally socially liberal views and attitudes—the mere fact of the gender imbalance means that women in STEM will have many more opportunities to be exposed to whatever sexists there are.  This puts a special burden on us to create a welcoming environment for women.

4. Given that we know that gender gaps in interest and inclination appear early in life, I believe in doing anything we can to encourage girls’ interest in STEM fields.  Trust me, my four-year-old daughter Lily wishes I didn’t believe so fervently in working with her every day on her math skills.

5. I believe that gender diversity is valuable in itself.  It’s just nicer, for men and women alike, to have a work environment with many people of both sexes—especially if (as is often the case in STEM) so much of our lives revolves around our work.  I think that affirmative action for women, women-only scholarships and conferences, and other current efforts to improve gender diversity can all be defended and supported on that ground alone.

6. I believe that John Stuart Mill’s The Subjection of Women is one of the masterpieces of history, possibly the highest pinnacle that moral philosophy has ever reached.  Everyone should read it carefully and reflect on it if they haven’t already.

7. I believe it’s a tragedy that the current holder of the US presidency is a confessed sexual predator, who’s full of contempt not merely for feminism, but for essentially every worthwhile human value. I believe those of us on the “pro-Enlightenment side” now face the historic burden of banding together to stop this thug by every legal and peaceful means available. I believe that, whenever the “good guys” tear each other down in internecine warfare—e.g. “nerds vs. feminists”—it represents a wasted opportunity and an unearned victory for the enemies of progress.

OK, now for the part that might blow some people’s minds.  I hold that every single belief above is compatible with what James Damore wrote in his now-infamous memo—at least, if we’re talking about the actual words in it.  In some cases, Damore even makes the above points himself.  In particular, there’s nothing in what he wrote about female Googlers being less qualified on average than male Googlers, or being too neurotic to code, or anything like that: the question at hand is just why there are fewer women in these positions, and that in turn becomes a question about why there are fewer women earlier in the CS pipeline.  Reasonable people need not agree about the answers to those questions, or regard them as known or obvious, to see that the failure to make this one elementary distinction, between quality and quantity, already condemns 95% of Damore’s attackers as not having read or understood what he wrote.

Let that be the measure of just how terrifyingly efficient the social-media outrage machine has become at twisting its victims’ words to fit a clickbait narrative—a phenomenon with which I happen to be personally acquainted.  Strikingly, it seems not to make the slightest difference if (as in this case) the original source text is easily available to everyone.

Still, while most coverage of Damore’s memo was depressing in its monotonous incomprehension, dissent was by no means confined to the right-wingers eager to recruit Damore to their side.  Peter Singer—the legendary leftist moral philosopher, and someone whose fearlessness and consistency I’ve always admired whether I’ve agreed with him or not—wrote a powerful condemnation of Google’s decision to fire Damore.  Scott Alexander was brilliant as usual in picking apart bad arguments.  Megan McArdle drew on her experiences to illustrate some of Damore’s contentions.  Steven Pinker tweeted that Damore’s firing “makes [the] job of anti-Trumpists harder.”

Like Peter Singer, and also like Sarah Constantin and Stacey Jeffery above, I have no plans to take any position on biological differences in male and female inclinations and cognitive styles, and what role (if any) such differences might play in 80% of Google engineers being male—or, for that matter, what role they might play in 80% of graduating veterinarians now being female, or other striking gender gaps.  I decline to take a position not only because I’m not an expert, but also because, as Singer says, doing so isn’t necessary to reach the right verdict about Damore’s firing.  It suffices to note that the basic thesis being discussed—namely, that natural selection doesn’t stop at the neck, and that it’s perfectly plausible that it acted differently on women and men in ways that might help explain many of the population-level differences that we see today—can also be found in, for example, The Blank Slate by Steven Pinker, and other mainstream works by some of the greatest thinkers alive.

And therefore I say: if James Damore deserves to be fired from Google, for treating evolutionary psychology as potentially relevant to social issues, then Steven Pinker deserves to be fired from Harvard for the same offense.

Yes, I realize that a employee of a private company is different from a tenured professor.  But I don’t see why it’s relevant here.  For if someone really believes that mooting the hypothesis of an evolutionary reason for average differences in cognitive styles between men and women, is enough by itself to create a hostile environment for women—well then, why should tenure be a bar to firing, any more than it is in cases of sexual harassment?

But the reductio needn’t stop there.  It seems to me that, if Damore deserves to be fired, then so do the 56% of Googlers who said in a poll that they opposed his firing.  For isn’t that 56% just as responsible for maintaining a hostile environment as Damore himself was? (And how would Google find out which employees opposed the firing? Well, if there’s any company on earth that could…)  Furthermore, after those 56% of Googlers are fired, any of the remaining 44% who think the 56% shouldn’t have been fired should be fired as well!  And so on iteratively, until only an ideologically reliable core remains, which might or might not be the empty set.

OK, but while the wider implications of Damore’s firing have frightened and depressed me all week, as I said, I depart from Damore on the question of affirmative action and other diversity policies.  Fundamentally, what I want is a sort of negotiated agreement or bargain, between STEM nerds and the wider culture in which they live.  The agreement would work like this: STEM nerds do everything they can to foster diversity, including by creating environments that are welcoming for women, and by supporting affirmative action, women-only scholarships and conferences, and other diversity policies.  The STEM nerds also agree never to talk in public about possible cognitive-science explanations for gender disparities in which careers people choose, or overlapping bell curves,  or anything else potentially inflammatory.  In return, just two things:

  1. Male STEM nerds don’t regularly get libelled as misogynist monsters, who must be scaring all the women away with their inherently gross, icky, creepy, discriminatory brogrammer maleness.
  2. The fields beloved by STEM nerds are suffered to continue to exist, rather than getting destroyed and rebuilt along explicitly ideological lines, as already happened with many humanities and social science fields.

So in summary, neither side advances its theories about the causes of gender gaps; both sides simply agree that there are more interesting topics to explore.  In concrete terms, the social-justice side gets to retain 100% of what it has now, or maybe even expand it.  And all it has to offer in exchange is “R-E-S-P-E-C-T“!  Like, don’t smear and shame male nerds as a class, or nerdy disciplines themselves, for gender gaps that the male nerds would be as happy as anybody to see eradicated.

The trouble is that, fueled by outrage-fests on social media, I think the social-justice side is currently failing to uphold its end of this imagined bargain.  Nearly every day the sun rises to yet another thinkpiece about the toxic “bro culture” of Silicon Valley: a culture so uniquely and incorrigibly misogynist, it seems, that it still intentionally keeps women out, even after law and biology and most other white-collar fields have achieved or exceeded gender parity, their own “bro cultures” notwithstanding.  The trouble with this slander against male STEM nerds, besides its fundamental falsity (which Scott Alexander documented), is that puts the male nerds into an impossible position.  For how can they refute the slander without talking about other possible explanations for fields like CS being 80% male, which is the very thing we all know they’re not supposed to talk about?

In Europe, in the Middle Ages, the Church would sometimes enjoy forcing the local Jews into “disputations” about whose religion was the true one.  At these events, a popular tactic on the Church’s side was to make statements that the Jews couldn’t possibly answer without blaspheming the name of Christ—which, of course, could lead to the Jews’ expulsion or execution if they dared it.

Maybe I have weird moral intuitions, but it’s hard for me to imagine a more contemptible act of intellectual treason, than deliberately trapping your opponents between surrender and blasphemy.  I’d actually rather have someone force me into one or the other, than make me choose, and thereby make me responsible for whichever choice I made.  So I believe the social-justice left would do well to forswear this trapping tactic forever.

Ironically, I suspect that in the long term, doing so would benefit no entity more than the social-justice left itself.  If I had to steelman, in one sentence, the argument that in the space of one year propelled the “alt-right” from obscurity in dark and hateful corners of the Internet, to the improbable and ghastly ascent of Donald Trump and his white-nationalist brigade to the most powerful office on earth, the argument would be this:

If the elites, the technocrats, the “Cathedral”-dwellers, were willing to lie to the masses about humans being blank slates—and they obviously were—then why shouldn’t we assume that they also lied to us about healthcare and free trade and guns and climate change and everything else?

We progressives deluded ourselves that we could permanently shame our enemies into silence, on pain of sexism, racism, xenophobia, and other blasphemies.  But the “victories” won that way were hollow and illusory, and the crumbling of the illusion brings us to where we are now: with a vindictive, delusional madman in the White House who has a non-negligible chance of starting a nuclear war this week.

The Enlightenment was a specific historical period in 18th-century Europe.  But the term can also be used much more broadly, to refer to every trend in human history that’s other than horrible.  Seen that way, the Enlightenment encompasses the scientific revolution, the abolition of slavery, the decline of all forms of violence, the spread of democracy and literacy, and the liberation of women from domestic drudgery to careers of their own choosing.  The invention of Google, which made the entire world’s knowledge just a search bar away, is now also a permanent part of the story of the Enlightenment.

I fantasize that, within my lifetime, the Enlightenment will expand further to tolerate a diversity of cognitive styles—including people on the Asperger’s and autism spectrum, with their penchant for speaking uncomfortable truths—as well as a diversity of natural abilities and inclinations.  Society might or might not get the “demographically correct” percentage of Ellie Arroways—Ellie might decide to become a doctor or musician rather than an astronomer, and that’s fine too—but most important, it will nurture all the Ellie Arroways that it gets, all the misfits and explorers of every background.  I wonder whether, while disagreeing on exactly what’s meant by it, all parties to this debate could agree that diversity represents a next frontier for the Enlightenment.

Comment Policy: Any comment, from any side, that attacks people rather than propositions will be deleted.  I don’t care if the comment also makes useful points: if it contains a single ad hominem, it’s out.

As it happens, I’m at a quantum supremacy workshop in Bristol, UK right now—yeah, yeah, I’m a closet supremacist after all, hur hur—so I probably won’t participate in the comments until later.

by Scott at August 15, 2017 09:26 AM UTC

Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct?

Also on topic: where else (on the internet) is its correctness being discussed?

Note: the focus of this question text has changed over time. See question comments for details.

by Warren Schudy at August 14, 2017 10:27 PM UTC

I agreed a while ago, so despite physical health-related challenges, I will travel to cohost a KDD 2017 panel on Artificially Intelligent Assistants with the immaculate Andrew Tomkins.  We have great panelists, check out the official site

by metoo ( at August 14, 2017 06:08 PM UTC

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

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

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.

by Boaz Barak at August 14, 2017 04:17 PM UTC

(Thanks to Rachel Folowoshele for bringing this to my attention)

John Urschel is a grad student in applied math at MIT. His webpage is here.

Some students go straight from ugrad to grad (I did that.)

Others take a job of some sort and then after a few years go to grad school.

That's what John did;  however, his prior job was unusual among applied math grad students

He was in the NFL as a professional football player! See here for more about the career change, though I'll say that the brain-problems that NFL players have (being hit on the head is not a good for your brain) was a major factor for doing this NOW rather than LATER.

How unusual is this? Looking around the web I found lists of smart football players, and lists of football players with advanced degrees (these lists were NOT identical but there was some overlap) but the only other NFL player with a PhD in Math/CS/Applied math was

Frank Ryan- see his wikipedia page here. He got his Phd WHILE playing football. He was a PhD student at Rice.

I suspect that a professional athlete getting a PhD in Math or CS or Applied Math or Physics or... probably most things, is rare.  Why is this? NOT because these people are dumber or anything of the sort, but because its HARD to do two things well, especially now that both math and football have gotten more complex. Its the same reason we don't have many Presidents with PhD's (Wilson was the only one) or Presidents who know math (see my post on presidents who knew math: here) or Pope's who are scientists (there was one around 1000 AD, see here).

If you know of any professional athlete who has a PhD in some science or math, please leave a comment on such.

(ADDED LATER- a commenter pointed out Angela Merkel who has a PhD in Physical Chemistry,
is chancellor of Germany, and there is a musical about her, see here.)

(ADDED LATER- some of the comments were for Olympic Athletes and hence not professional and another comment pointed this out. So I clarify: Olympic is fine too, I really meant serious athlete.)

by GASARCH ( at August 14, 2017 01:45 AM UTC