## A Circuitous Parable

Last week I accidentally built a bookcase that didn’t fit my bed.

Obviously, that sentence doesn’t make sense.  Do you know what else doesn’t make much sense?  Research.

Actually, research does make sense.  In fact, it makes perfect sense (assuming it’s mathematically rigorous research).  And the first statement I made actually makes sense too.

Theorem: Last week I accidentally built a bookcase that didn’t fit my bed.

This is the quintessence of research:  A true statement that makes absolutely no sense out of context.

So what’s the context?

Proof: I got a bed frame from IKEA.  I finally got myself around to (another quintessential phrase of research) putting it together around 11pm.  I kind of knew this was a mistake and that it would take quite a while.

Well, after an hour or so of labor, I had just a piece of the bed frame put together and I was pretty sleepy and not too happy that the rest would probably take another couple hours.  So I decided to finish the rest the next day.

But, hey, at least I built this thing… Actually, what the hell is this thing?

Turned out it was a bookcase.  It was just a superfluous part of the bed frame design that you put the bed frame up against but isn’t even connected to.  I didn’t even build any of the parts that I actually cared about that would support the bed!

And then, on a second look, the bookcase seemed pretty narrow.  Too narrow for my bed that was supposed to lie up against it in the actual bed frame.  Huh, that’s weird.

So I measured my bed and, surely enough, it was too big for my bookcase.  My bed was a queen-size and I measured the remaining bed frame parts to find out that it was for a full-size.

So, I accidentally built a bookcase that didn’t fit my bed. $\blacksquare$

So there, a clear goal that failed and was recast as a confusing, out-of-context result: the quintessence of research.

All joking aside, theory research is immensely exciting and profound, as are its results.  The aim and results of research are generally trying to answer questions and it finds partial but crucial answers that piece together the landscape of our collective understanding.  It is not just recasting failures as results or missing the big picture of what it’s supposed to be answering.

(Feel free to skip this sectioned off part if you don’t want technical stuff)

Nevertheless, if you tell a new grad student (or advanced undergrad) Ryan Williams’ groundbreaking 2010 result that NEXP $\nsubseteq$ ACC, it will likely mean very little to them, seem daunting, and, most crucially, not seem to answer any profound question they’re aware of.

Even if they have some working undergrad knowledge about complexity, know why the P $\neq$ NP question is important, can guess that the ‘N‘ in NEXP stands for non-deterministic, and can Wikipedia the definition of ACC and understand it, it’s still very non-obvious why the result is groundbreaking or even natural.

If I asked someone for a bed frame (e.g. whether or not P $\neq$ NP) and they came back 40 years later with a bookcase that didn’t fit the bed or even connect to the bed frame (e.g. NEXP $\nsubseteq$ ACC ), I would be very confused, especially when everyone gets very excited, as to what happened in those 40 years.

I would first have to be told that NEXP $\nsubseteq$ ACC wasn’t just a fact being told to me (that could sound as bizarre as the above-proved “Theorem”),  but was actually a result that made progress on my original P $\neq$ NP question.  But then there’s a whole slew of moving parts that need to be known to get any semblance of how they’re related.

But then that would hardly help.

Knowing all the definitions does not let us draw the connection.  There’s so much swimming around: non-uniformity, exponential time, oddly specific circuits, how this type of non-uniform subset inequality constitutes as a lower bound, etc.  But knowing each of these still isn’t quite enough to see where this result came from, much less why it’s celebrated.

What needs to be known is the journey.  The human journey that got us here is the context that lets us know what’s exciting about this and where it came from.  We’d have to know how, in trying to prove P$\neq$NP, we found that Turing machines are hard to reason about and that some of the first complexity bounds we were able to cut our teeth on were circuit lower bounds.  We’d have to have some intuition of the history of how the nice, concrete, and finite structure of circuits let us unconditionally show the limitations of some classes of circuits.  We’d have to understand the excitement of the time, where the concreteness of circuits (you could almost put your hands on them) seemed like proving P$\neq$NP was right around the corner.  You’d have to see that P/poly, the non-uniform/circuit version of P, gave us an attack plan to show P$\neq$NP: Since P$\subset$P/poly then showing NP $\nsubseteq$ P/poly would show P$\neq$NP.  And we’d have to acknowledge the early results that encouraged hope for the success of this.  We’d need to see how the easily tangible class of $\textbf{AC}^0$ was a natural notion of a circuit (and a natural generalization of a CNF formula that simply nested its AND‘s and OR‘s a constant number of times) and that its naturalness and simplicity allowed some of the first circuit lower bounds.  We’d need to picture those first bounds of showing that counting mod 2 is “hard for” $\textbf{AC}^0$ excited the community and spurred them to the next natural step of showing that even if you could count mod 2 then it would be hard to count mod 3 (i.e. mod 3 is hard for $\textbf{AC}^0\textbf{[2]}$).  You may even see how, after generalizing this to counting mod q being hard even if you could count mod p for any primes and q (i.e. mod q is hard for $\textbf{AC}^0\textbf{[p]}$), the next natural step was to see what was possible if you could count mod n for any integer n .  And, finally, we see how we arrive at ACC$\textbf{AC}^0$ with “counters” (note that ACC still seems to be a much weaker class than P/poly).  We might finally glimpse that from the initial results of circuit lower bounds (which held so much promise for solving P$\neq$NP) how the class ACC might have arisen naturally.  And then we can guess that we wanted to show something is hard for ACC, as was conjectured for the MAJORITY function.  But, as we might guess, as not much progress was made for the MAJORITY function, attention shifted to showing that at least some problem in NP was hard for ACC (i.e. NP$\nsubseteq$ACC).  And, while we might realize that (since ACC is weaker than P/poly and doesn’t seem to contain P) an answer to this wouldn’t resolve P$\neq$NP, it would certainly be worth answering and even arose naturally from the journey that brought us here.  And we might even now foresee that getting stuck on NP$\nsubseteq$ACC, may cause us to step back and realize that we don’t even know if NEXP$\nsubseteq$ACC!  We could imagine the shame of absolutely knowing that something as hard as NEXP has things much much too hard for ACC but not even being able to show that.  And finally we can almost picture waiting through the quarter-of-a-century stagnation in complexity theory where very few new results came from Boolean circuit lower bounds.  But then we might feel anticipation, shock, and exultation bubbling in us as Ryan Williams not only closes this open question but does it with insightful, novel, and philosophically mind-boggling perspectives: algorithm design’s art of showing what’s possible is the key to solving this problem of circuit complexity’s art of showing what’s impossible.  Upper bounds give us our lower bounds!

Whew!  What a journey!

What a very very human and (dare I say) natural journey.

Context, context, context.

Everything about research is context.  And not just because it’s complicated and there’s a lot of background.  But because it’s such a human endeavor and that that fully shapes what’s surprising, what’s counter-intuitive, what’s beautiful and exciting.

Luckily we have some very human people living and searching for beauty and sharing it.  Ryan Williams writes phenomenal introductions and gives context and allure to his already beautiful concepts.  And we have very human people blogging (already giving the story I gave today) and mentoring and teaching.

But I think it is very worth saying that research is not about results being dropped as facts from the aether, but is about human journeys and what they evoke in us as we explore.

And I obviously wasn’t around during the journey I described that led to Ryan’s result, but I had the opportunity to be taken through it by very human people this semester at the Simons Institute and there’s much to be evoked and much to be explored.  And most of it ends up on a weird, windy, circuitous path of bed-frame building.  And it leads to sentences like “Last week I accidentally built a bookcase that didn’t fit my bed.”

But I wouldn’t have it any other way…except that everyone relishes in the context and human experience.  Grad school is a weird place full of bookcases masquerading as bed-frames and journeys masquerading as facts, all marinating in Impostor’s Syndrome.  Drop all the masks and human it up.

So continue on researchers!  Keep beds in your bookcase and books in your bed and we’ll all do just fine.