# AMS Network Science Mathematical Research Community

I don’t usually write promotional posts because I don’t enjoy reading them as much as I enjoy reading the technical posts. But I know that a lot of early graduate students and undergraduates read my blog, and this would be of interest to many of them.

I just got back from Utah yesterday where I attended a 5-day workshop run by the American Mathematical Society, called the Network Science Mathematical Research Community (MRC).

The point of the program is to bring graduate students and early career folks together from all over the country to start new collaborations. The AMS runs multiple MRC sessions every year, and this year the topics ranged from network science to quantum physics. We had a group of about 20 people, including statisticians, applied mathematicians, computer scientists, and a handful of pure combinatorialists. We self-organized into groups of four, and spent pretty much all day for the next four days eating great food, thinking about problems, proving theorems, enjoying the view, and discussing our ideas with the three extremely smart, successful, and amicable organizers. There were also career panels every evening that were, in my opinion, better than the average career panel.

The network science group (you can see me peeking out from the back, just left of center).

Anyway, it was a really fun and valuable experience, and the AMS pays for everything and a bag of chips (if by chips you mean more travel money to meet up with your collaborators and a ticket to the AMS Joint Mathematics Meeting the following January). I’m excited to blog about the work that come out of this, as network science is right up there with the coolest of topics in math and programming.

So if you’re eligible, keep an eye out for next year’s program.

# Three Years Old, and an Idea for a Podcast

Happy birthday, Math ∩ Programming!

Today marks the end of the third year I’ve been writing Math ∩ Programming, and I’m excited to keep it going as I start my research career. In the last year I’ve started a secondary writing blog for some smaller, less technical bits, mostly to get thoughts out of my head. And while I could use this anniversary post to preview future Math ∩ Programming posts or review old favorites, I’ll instead share an idea that has been bouncing around my head for a few weeks. I’d love to hear your feedback in the comments.

I listen to podcasts and radio shows a lot, mostly storytelling and interviews. And they’re always bringing on these fancy-sounding people who write books on the New York Times Bestsellers list and who often have very interesting things to say. When discussing science they can often convey the ideas to the clueless listener, usually because it’s experimental science that’s naturally easy to understand (state the setup, state the results, hypothesize about the implications). But almost unilaterally there’s nothing substantive about math. All the mathematical content is popular math, how beautiful is $\pi$ and such; math education, which I love to read and talk about but is common; or math history, which I’m not as interested in. And when there is some breakthrough, like Grigori Perelman solving a Millennium prize problem, the focus is entirely on the person and not the achievement. This isn’t specific to podcasts, but all news. I just happen to prefer my news in podcast form.

And so, aside from the myriad of excellent technical blogs by active researchers, what is there really that conveys the excitement I experience in theoretical computer science? There are publications like the ACM SIGACT monthly newsletter, which has a ton of book reviews and a handful of technical columns. Unfortunately it’s hidden behind a paywall, which basically immediately excludes it from being accessed by anyone not already embedded deep in academia. That being said it often has really interesting pieces like a poll by Bill Gasarch (2002, 2012) of researchers and their opinions on P vs NP. It’s really interesting to see just how much people differ on their desire to see other parts of mathematics incorporated into its resolution.

So if you don’t want to pay the ACM for a monthly newsletter, what can you do? Many of these ideas and opinions don’t exist in textbooks, and textbooks can be dry and bad at conveying why things are interesting or exciting. There are abstruse technical papers that you have to finish a graduate degree before you can even parse what’s being said. And then there are talks, which vary in quality almost as much as prose in technical papers do.

I recently came across a paper by Ryan Williams, a prominent researcher in circuit complexity. Roughly, when you study circuit complexity you try to understand which problems provably require big circuits to solve, and you study those proof techniques. It sounds boring but it’s interesting for three reasons: it’s extremely hard, there are many “embarrassing” open problems, and many of these problems imply wonderful things like $P \neq NP$. I actually get really excited by circuit complexity.

Anyway, this paper was titled “A Casual Tour Around a Circuit Complexity Bound,” in which Ryan reflects on the path which led him to one of the biggest breakthroughs in the last five years in circuit complexity. His writing is more or less informal (it was published in the SIGACT newsletter, though I had to access it through arXiv), and it focuses heavily on the big picture. It struck me as mostly how to think about circuit complexity. This kind of thing is truly invaluable for a graduate student and anyone, I imagine, trying to learn more about circuit complexity. Honestly, I’d love to see more of this in academic literature. Often papers are expanded from relatively simple principles into a mess of technical details, and reversing this process is slow and difficult.

But even besides these huge breakthroughs there are often really great ways to explain new problems and solutions. For example, this paper of Andrew Drucker, titled “High-Confidence Predictions under Adversarial Uncertainty,” starts with a really easy to understand setup:

A frog wants to cross the road at some fixed location, to get to a nice pond. But she is concerned about cars. It takes her a minute to cross the road, and if a car passes during that time, she will be squashed. However, this is no ordinary frog. She is extremely patient, and happy to wait any finite number of steps to cross the road. What’s more, she can observe and remember how many cars have passed, as well as when they passed. She can follow any algorithm to determine when to cross the road based on what she has seen so far, although her senses aren’t keen enough to detect a car before it arrives…

[Even if we assume the cars arrive according to a fixed probability distribution,] the frog may not have a detailed idea of how the cars are generated. It may be that the frog merely knows or conjectures some constraint obeyed by the car-stream. We then ask whether there exists a strategy which gets the frog safely across the road (at least, with sufficiently high probability), for any car-stream obeying the constraint.

This kind of story is better than coffee at keeping people awake during talks!

And so, I have been thinking a lot about what a podcast about theoretical computer science might entail. I imagine it going something like this: every episode is a half-hour conversation with a prominent researcher. The discussion would cover something about past work, something about future ideas of what’s important and a high level idea of the burgeoning techniques, and overarching questions about how one approaches research. Computer science is particularly interesting because most graduate students know enough to start working on open problems in their first year (so the topics are more accessible than, say, algebraic geometry), and because basically all of the theorems with names are named after people still active in the research community. Moreover the format of a podcast would require the interviewees to phrase their research in a way that doesn’t require a chalkboard or notation.

What do you think of the idea? Would you listen to a theory podcast? Do you have a good idea for a catchy name? Are you a theory researcher who would like to have a conversation with me the next time we’re at a conference together? *fingers crossed* I’d love to hear from you.

# Midwest Theory (of Computing) Day at Purdue University

I’ll be giving a talk at Purdue University on Saturday, May 3 as part of the 65th Midwest Theory Day. If any readers happen to live in West Lafayette, Indiana and are interested in hearing about some of my recent research, you can register for free by April 28 (one week from today). Lunch and snacks are provided, and the other talks will certainly be interesting too.

Here’s the title and abstract for my talk:

Resilient Coloring and Other Combinatorial Problems

A good property of a problem instance is that it’s easy to solve. And even better property is resilience: that the instance remains easy to solve under arbitrary (but minor) perturbations. We informally define the resilience of an instance of a combinatorial problem, and discuss recent work on resilient promise problems, including resilient satisfiability and resilient graph coloring.
Hope to see you there!

# Where Math ∩ Programming is Headed

This week is Spring break at UI Chicago. While I’ll be spending most of it working, it does give me some downtime to reflect. We’ve come pretty far, dear reader, in these almost three years. I learned, you learned. We all laughed. My blog has become my infinite source of entertainment and an invaluable tool for synthesizing my knowledge.

But the more I write the more ideas I have for articles, and this has been accelerating. I’m currently sitting on 55 unfinished drafts ranging from just a title and an idea to an almost-completed post. A lot of these ideas have long chains of dependencies (I can’t help myself but write on all the background math I can stomach before I do the applications). So one day I decided to draw up a little dependency graph to map out my coarse future plans. Here it is:

A map of most of my current plans for blog posts and series, and their relationships to one another. Click to enlarge.

Now all you elliptic curve fanatics can rest assured I’ll continue working that series to completion before starting on any of these big projects. This map basically gives a rough picture of things I’ve read about, studied, and been interested in over the past two years that haven’t already made it onto this blog. Some of the nodes represent passed milestones in my intellectual career, while others represent topics yet to be fully understood. Note very few specific applications are listed here (e.g., what might I use SVM to classify?), but I do have ideas for a lot of them. And note that these are very long term plans, some of which are likely never to come to fruition.

So nows your chance to speak up. What do you want to read about? What do you think is missing?