Does This Make Sense?

What would it look like if I plotted the temperature of my morning coffee with respect to time? Image courtesy of Flick CC via Jen.

Some of my favorite questions to ask in class involve drawing up some sort of a mathematical model for my students and asking: does this make sense? Whether matching curves to the heating and cooling laws of my morning coffee, or studying how our shadows grow relative to our speed, it’s always a nice way to play with students’ quantitative intuition.

Recently, Dan Meyer of the blog dy/dan, wrote about this idea in The Difference Between Math and Modeling with Math in Five Seconds. He shows a video of a dog setting a world record for balloon popping (yeah, I know, I’m also simultaneously thrilled that’s a thing and deeply concerned about the fact that dogs love to eat deflated balloon bits) and then asks students to model the situation. He teases out the differences between linear and non-linear models, and the difference between just doing math and interpreting the realities of a situation.

I think that people underestimate the element of intuition and human touch in mathematics. Students ask questions like, how do I know which model to use? How do I know which integration technique to use? How do I know which convergence test to use? And I always feel like a bit of a jerk (slash, I also feel a bit like a wise old sage) when I say the only possible correct answer, namely “You use the one that works.”

But you have to develop some intuition for these things.

Models are interesting because people are typically using them to describe phenomenon that they already see happening. Trying to quantify the meaning of several different variables in the context of a larger system, and to forecast where that whole system might go if the variables change. Recently, I podcasted about another great example of mathematical modeling in several variables, sharing the recent work of Steven Strogatz and some folks at the MIT Sensible City Lab about the effectiveness of ridesharing.

Teaching calculus, the closest that we get to mathematical modeling is in studying the laws of natural growth, but this is already rich territory. If you really want to scare your class, have them watch this video from NPR abut population growth, tell them about the human carrying capacity of the earth. Then have them calculate how long we’ve got left.

For the less macabre among us, Meyer also points us towards the reindeer of St. Matthew’s Island.

Someone once said to me that computers will never put mathematicians out of business, because a computer can never match our human intuition. A computer can never look at a model with our human eyes and human sense of the world and say, does this make sense? I’m not sure if I believe that, what do you think? Let me know on Twitter @extremefriday.

Posted in Applied Math, Biomath | Tagged , , | Leave a comment

Adding to the Faces of Mathematics on Wikipedia

For better or for worse, Wikipedia is the first place most people look when they want to learn about someone or something online. I don’t use Wikipedia as my sole source for important facts, but it’s a great first stop when I’m researching a topic, and it often helps me find the more reliable resources I end up citing in articles I write.

Mathematician Vivienne Malone-Mayes, a professor at Baylor University from 1966-1994. Her picture was just added to her Wikipedia page. Credit: The Texas Collection, Baylor University. CC BY-SA 2.0

Last month on her PLOS blog Absolutely Maybe, Hilda Bastian wrote about her efforts to improve the Wikipedia pages of black women in science by both expanding on the articles and by adding pictures to ones that don’t have them. She writes:

As I’ve been combing through what seems like a bottomless pit of digitized old black and white photos of white scientists, the Black History Month stories and tweets about African-American women scientists were mostly about the same small group – although this year, plus the fabulous supersonic boost by Margot Lee Shetterly and the women of Hidden Figures.

That’s not because the supply of African-American women scientists from the past with gripping stories is tapped out. It’s not. Rather, when it comes to the stories of black women scientists, Diann Jordan writes, “The harvest is plentiful but the laborers are few”.

There is some randomness about whose stories have been told, who had compelling, high quality photos taken, and which images have surfaced online. Mostly it’s not random, though. The odds are stacked against visibility in the historical record, as it was in life – and for many of the same reasons.

Vivienne Malone-Mayes is one of the women Bastian mentioned in her post. Malone-Mayes got her Ph.D. in math from the University of Texas in 1966 after navigating challenges such as being ostracized by her fellow students and being barred from classes taught by R.L. Moore, venerated pedagogue and notorious racist. She was the first African American professor at Baylor University. Her Wikipedia page was bereft of a photo because there wasn’t one available with the correct license. I am a Baylor alumna, so I wrote to my alma mater about making a picture they have in their archives available for Wikipedia. Hours later someone from the photo collection had changed the license uploaded it to Malone-Mayes’ Wikipedia page!

It only took me a few minutes to compose the email that liberated the photo, and it gave me a nice feeling of accomplishment for the day. Bastian has another post on her blog about how people can help get missing scientists’ faces added to their Wikipedia pages with tips you can use whether you have minutes or days you can devote to it. She also started the @MissingSciFaces Twitter account to encourage people to help write and share stories of scientists from underrepresented groups. I just signed up for a Wikipedia account, and I’m hoping to start contributing to Wikipedia pages of mathematicians from underrepresented groups and other math articles. I’m new to Wikipedia (as a contributor; not as a consumer), so I’ll be using WikiProject Women Scientists and Women in Red for inspiration as I get started. If you are so inclined, I hope you’ll join me.

Posted in people in math | Tagged , , , | 1 Comment

Diversify Your Blogfolio

No matter what we write with, we all approach math from a different angle. Image courtesy of lisamikulski via Flickr CC.

It’s March. As the sun sets on black history month and rises on women’s history month, I feel inclined, as I do every March, to draw attention to some of the great women who blog about math as well as several blogs that address diversity in mathematics.

The most recent exciting news on that front is the launch of inclusion/exclusion, a new blog in the AMS family. The blog is edited by Edray Goins, Piper Harron, Brian Katz, Luis Leyva, and Adriana Salerno (former editor of another great AMS blog PhD + epsilon). The mission of the blog is brought into clear focus in their first post, Inclusion/Exclusion Principle. The editors aim to change the common notion of what it is to be “professorial,” to include a diverse array of views through conversations about the profession, and to provide us with strategies for addressing the diversity in the classroom and in the field.

One of my favorite posts so far came from Piper Harron, who formerly (and perhaps still?) blogged as The Liberated Mathematician. In her post, Hands Off My Confidence, Harron attacks the common “women-lack-confidence narrative,” by describing her own relationship with confidence through the arc of her life. She makes important points about the difference between lacking confidence and making calculated decisions within a system.

It’s often a challenge to understand how a person’s life experiences have shaped their outlook and relationship to math when we haven’t necessarily experienced the same life. Recently my co-blogger Evelyn Lamb, who also blogs for Scientific American at Roots of Unity published Being a Trans Mathematician: A Q&A with Autumn Kent. In it Kent admits that her story of transition is not necessarily the same one shared by all trans women, but it’s very worthwhile to read about her story of coming out occurring in parallel with her trajectory as an academic mathematician.

Finally, this year at the JMM the outgoing MAA president Francis Su gave an address, which is now posted to his blog as Mathematics for Human Flourishing. His message of inclusions is a poignant one, and he speaks to the experience of minorities in math. In his post he addresses how important mathematics and a sense of belonging in the mathematical community are to our ability to flourish as humans. Whether we explore math for play, beauty, justice, or truth, math has something to teach us about the larger world. In it, Su says, “justice is required for human flourishing. We flourish—we experience shalom—when we treat others justly and when we are treated justly.”

Posted in Issues in Higher Education, women in math | Tagged , , , , , , | Leave a comment

A Thrice-a-Day Complex Analysis Infusion

Sometimes I like to sit back and take in math via pictures only. The newest addition to my math picture blog stable is where three times a day, a beautiful picture appears.

Credit: Thomas Baruchel

These are graphs of complex-valued functions based on continued fractions. White points are where the function takes on real values, black are imaginary, and the other points are colored according to angle. On the blog’s “about” page, Baruchel explains the notation, which is not the most common continued fraction notation. 

It’s fun to look at a graph and try to figure out why it looks the way it does: why are there purely real or imaginary values in particular places, why a graph has horizontal or vertical symmetry, and so on. These are not straightforward functions, so I must admit I don’t always get anywhere, but it’s fun to think about anyway. If I were teaching complex analysis, I would probably try to work this blog into my class somehow, if only to gawk at pretty things with my students.

I’ve been trying to decide which kinds of graphs are prettiest. “Flowers” are nice.

Credit: Thomas Baruchel

But so are hearts.

Credit: Thomas Baruchel

Graphs that evoke mathematical symbols are always on trend.

Credit: Thomas Baruchel

Simple ones are nice.

Credit: Thomas Baruchel

And so are the wild, busy ones.

Credit: Thomas Baruchel

Luckily you don’t have to choose. Just add the blog to your feed, put your feet up, and relax with some gorgeous mathematical illustrations.

Posted in Mathematics and Computing, Mathematics and the Arts | Tagged , , , | 2 Comments

A Circular Approach To Linear Algebra

Sadly, this is not actually the way linear transformations work, from xkcd.

This semester I’m teaching Linear Algebra for the first time, so naturally, I am constantly on the prowl for all of the linear algebra resources the internet has to offer. To begin with, I’m using a free online textbook called Linear Algebra Done Wrong by Sergei Treil. I’ve found that it’s a bit…intense. As a person who understands linear algebra the book is very nicely written and has a logical presentation and abundant clever examples. But for a person who has never seen linear algebra, well, let’s just say it’s a bit like diving into the deep end with no floaties on while someone shoots you with a paintball gun.

Consequently, this semester has left me foraging the world wide web for supplementary resources to help my poor flailing floatieless students as they try to navigate the waters of vectors and matrices.

A great place for students to begin if they are totally lost is a series of wonderful YouTube videos called the Essence of Linear Algebra, from 3Blue1Brown. The animations really help to bring out some of the geometric intuition behind vector spaces, which can seem abstract (and sometimes totally impenetrable!) to students seeing them for the first time. Of course Khan Academy also hosts a linear algebra series, but my students haven’t found them as helpful.

Don’t like the dog? You can also toggle between a cat and a mouse. Screenshot from Wolfram Demonstrations Project.

On the theme of helpful animations, which teaching linear transformations, I found some really great demonstrations on Wolfram that let you transform a dog, more specifically, a Scottish Terrier, by a personalized 2×2 matrix. You can stretch, flip, and shear the Scottish Terrier by changing the values in the accompanying matrix. Somehow this is way more convincing than just drawing pictures and waving your hands around. The Wolfram Demonstrations Project is packed with great demos for transforming vector spaces, and you can share your own.

Finally, when I ask former math majors what most mystified them about Linear Algebra I almost always hear something about eigenvectors. It’s shocking how many students get in and out of Linear Algebra and have no intuitive idea what an eigenvector or eigenvalue are. And I’m not passing judgement here. When I took Linear Algebra as an undergraduate I was in the same boat! I knew how to compute them, but I had no idea what I was really looking at.

Not just a beautiful pirouette, but also a great example of a linear transformation with eigenvector e2 and eigenvalue 1.

Luckily, we have Steven Strogatz to the rescue with a most concise and intuitive explanation of eigenvectors and eigenvalues. He compares a linear transformation of 3-dimensional space to snapshot of a dancer, arms outstretched spinning in a pirouette-like motion. Her arms (a vector in the x direction) are moving, her gaze (a vector in the z direction) is moving, but the leg she’s spinning on (a vector in the y direction) stays fixed. This fixed vector is an eigenvector. And if she comes down of her pointed toes, then there is some element of scaling. This is an eigenvalue.

Mathew Simonson, who wrote about his own “eigenightmares” for the AMS Grad Student blog, proposes a spiral approach to pedagogy to combat those eigenfears. Students learn early on to express linear transformations as matrices, at this point they already can get some sense of eigen-type behavior just by acting on a simply figure in a vector space. Say, maybe, a nice little Scottish Terrier. In this way, students can see that eigenvectors are happening, before formally knowing what they are. This puts the intuitive before the formal, which I like.

Do you have any favorite online resources for teaching or understanding Linear Algebra? Let me know on Twitter @extremefriday.

Posted in Math Education | Tagged , , , | 4 Comments

How to Communicate in a Post-Truth World

“No, you’re a snowflake!” Two Men in Conversation by Hans Schliessmann. Public domain, via the Metropolitan Museum of Art.

Fake news is not new. For years I have rolled my eyes and scrolled by quack health and science stories, links from the satirical Borowitz Report shared credulously, and other incorrect information in my Facebook feed. I have often written well-researched, thoughtful comments challenging those posts and deleted them before posting. What’s the use? Is it worth being a spoilsport and telling my friend that no, she probably doesn’t have an extra type of cone that allows her to see more colors than most of us mere mortals? During and since the past election cycle, though, fake news has felt urgent. It is a problem that has launched a thousand thinkpieces, and I’m naturally suspicious of all of them.

I am both a mathematician and a science writer. My first instinct is to fact-check. But ever since starting my career as a science writer I have been reading and processing pushback to the “throw facts at it” strategy. Sometimes called the “deficit model” of science communication, the idea that we can change people’s beliefs and what they do about them by filling their heads with facts is both appealing and wrong. There are studies suggesting that telling people they are wrong about emotional issues such as climate change or vaccination not only doesn’t help, it can further entrench them into their beliefs. Great. I believe that the deficit model doesn’t work, that throwing facts at a problem doesn’t help. Doing nothing certainly doesn’t correct anything. So what should a math or science communicator or concerned friend and citizen do in the face of “alternative facts”?

People arguing against the deficit model often seem short on practical solutions for communicating more effectively. And that’s fair. Just because you know something isn’t right doesn’t mean you have a better solution. I can (and do) reject the dozens of crank proofs people send me about P vs. NP or the Riemann Hypothesis without solving the problems myself.

But a few articles I’ve read in the past month have offered more concrete suggestions and even made me a little hopeful that I’m not shouting into a void. Rachel Gross wrote an article for Undark about the shortcomings of the deficit model and the need for science writers to acknowledge their own preconceptions and recognize that science is not the only source of truth and meaning for anyone, including the people who read our articles or Facebook comments.

Even more optimistic is an Atlantic article by Olga Khazan that covers recent research suggesting that people who are scientifically curious do sometimes change their minds.

But, surprisingly, the science-curious among them didn’t harbor the same knee-jerk biases. They were more likely than the non-curious to read a news story that clashed with their political affiliation. The liberals, for example, opted to read a newspaper article headlined, “Scientists Report Surprising Evidence: Ice Increasing in Antarctic, Not Currently Contributing To Sea-Level Rise.” They craved novelty, even when they knew they wouldn’t agree with it.

In other words, curiosity seems to be the pin that bursts our partisan bubbles, allowing new and sometimes uncomfortable information to trickle in. Nothing else works like curiosity does, the authors point out—not being reflective, or good at math, or even well-educated.

With the usual caveat that this is preliminary research, it does make me wonder if there are ways to challenge people’s beliefs by piquing curiosity rather than telling people they’re wrong at the outset. That is, can we plant some of that curiosity, or will we only ever be able to reach people who are naturally more scientifically curious?

Finally, I appreciated Brooke Borel’s thoughtful blog post How to Talk to Your Facebook Friends about Fake News for The Open Notebook. Borel is a journalist, author, and fact-checker who recently literally wrote the book on fact-checking, and she says in another recent article for 538 that “fact checking will not save us from fake news.” Her Open Notebook post centers not fact-checking but empathy and engaging “the person, not the content” by finding common ground. This advice gets a little tricky because it feels like it could be a tone-policing suggestion. But I am taking it as a suggestion for people who are not actively marginalized or hurt by the item being discussed. People never have an obligation to disagree politely, especially when they are being hurt, but for people in a position of relative privilege in a particular conversation, it is one way to make it more likely for another privileged person to listen to the argument instead of disengaging immediately.

Borel’s post ends with a sobering dose of reality. These suggestions might be a good way to have conversations that don’t devolve into calling each other snowflakes, but they might not actually change people’s minds. “Whether any of these tactics will actually work is unclear….So, should you try to enter the fray of the Facebook fake-news fights? And if you do, will it make any difference? The answer is: It depends. But if you do try to change hearts and minds on social media, come with your facts, but also your empathy.”

Borel’s post is the first story in The Open Notebook’s series “Six Tools for an Uncertain Era.” The Open Notebook is an excellent website for anyone who is interested in math and science communication. They publish Q&A’s with great science writers like Erica Klarreich, one of my math communication role models, along with many other helpful resources for those who want to hone their communication skills. In the past few months, mathematicians have been more openly politically active—for example, by getting involved in gerrymandering research and trials and opposing the executive order on immigration. Knowing how to reach a wide variety of people as effectively as possible will be an important skill for all of us moving forward, whether it’s just talking with our friends on Facebook or getting ready to testify in court about why that legislative district looks so funny.

Posted in Math Communication | Tagged , , , , , | 2 Comments

They Answered The Call Of Numbers

Hidden Figures is a book about people like you, who answered the call of numbers,” said the author Margot Lee Shetterly, addressing a packed room at the Joint Math Meetings in Atlanta this January. The book, which tells the story about the black women mathematicians who took up positions at Langley Research Center during World War II and eventually went on to make critical contributions to the space race, is a powerful one. Set against the backdrop of Jim Crow era Virginia, at a time when women weren’t allowed to be anything other than human computers and segregation was still a dominating force, these women’s incredible and undeniable talents made them unstoppable.

Image via Wikimedia Commons

Image via Wikimedia Commons

The film adaptation of Hidden Figures has been a huge success, and glowing reviews continue to pour in all over the internet. Gizmodo praises the beautiful portraits of humanity painted by the characters. ArsTechnica calls it “the perfect space race movie.” The movie even inspired an SNL sketch featuring Leslie Jones, who says “it taught me something I never knew, black women helped astronauts go to space! Why didn’t they teach me that in school?!?” Good question, Leslie. Good question.

There’s something wild to the fact that this story has just been sitting there in our relatively recent history, just waiting to be told. In a world where young women — especially young black women — struggle to identify with the scientists and mathematics of legend, hearing this story has the power to help us change the way we see ourselves.

Author Margot Lee Shetterly speaks on a panel after a screening of the film at the White House in December, 2016. Image via Wikimedia Commons.

Author Margot Lee Shetterly speaks on a panel after a screening of the film at the White House in December, 2016. Image via Wikimedia Commons.

And given the overwhelming reception of the book and film, its safe to say that we were so ready for this. Perhaps we’ve been ready for it, or maybe there’s just something reassuring about a good math story during this age of uncertainly. Along with a long list of accolades, Hidden Figures is the top grossing oscar nominee of 2017. It actually earned $447 million in the first 24 days.

But I have to be honest, watching this beautiful movie during this very week in February 2017, I couldn’t shake some sad feelings. The movie was a testament to inclusivity and the great scientific achievements we are capable of when we allow everyone to sit at the table. And it was not lost on me that right now our president is stopping people from sitting at the table and grossly undermining so much of the scientific progress that we should rightly be celebrating. Hidden Figures is an incredible story about brilliant people who were on the right side of history. I hope that we can live up to their dream for America.

Posted in History of Mathematics, women in math | Tagged | Leave a comment

Celebrating Black Mathematicians


The first four mathematicians featured on the Mathematically Gifted and Black website: Trachette Jackson, Arlie Petters, Tasha Innis, and Mohamed Omar.

As you may know, February is Black History Month in the U.S. To celebrate, the new website Mathematically Gifted and Black is featuring a different black mathematician every day this month. The site was started by mathematicians Erica Graham, Raegan Higgins, Candice Price, and Shelby Wilson, who were inspired by Lathisms, a similar project featuring Latinx and Hispanic mathematicians in September and October. (I wrote about that project here in October.) As they write in their mission statement,

Our mission is to feature and share the accomplishments of blacks in the mathematical sciences. The mathematicians highlighted here have made significant contributions in research, mentoring, and teaching. This platform provides access to the diverse and dynamic community of black mathematicians.

So far I’ve seen two familiar faces and four new ones on the calendar, and I’m looking forward to seeing who else pops up this month. You can suggest people for next year by emailing the organizers. Price, Wilson, Syvillia Averett, and Dandrielle Lewis are also making short videos about black mathematicians and posting one each Sunday this month. The first one is here.

The Mathematically Gifted and Black website banner.

The Mathematically Gifted and Black website banner.

The runaway success of the movie Hidden Figures, which brings to light the work black women did in the early days of NASA in spite of racist and sexist barriers they faced, makes me optimistic that more people want to learn about people like Katherine Johnson, Dorothy Vaughan, and Mary Jackson. I know the movie has been a source of inspiration for teachers who want to get their students excited about math and science and broaden their perspective on who mathematicians and scientists are. Sites like Mathematically Gifted and Black and this Marie Claire article about black women currently working at NASA are also good places to meet more people who follow in that legacy.

For more resources for learning about black mathematicians, check out this roundup I wrote last year.

Posted in Events, History of Mathematics, people in math | Tagged , , , , | Leave a comment

Solidarity with Scientists

Mathematics has an interesting relationship to science. People often think of mathematicians as a subset of scientists, and scientists definitely use mathematics in their work, but our day-to-day work, careers, and the kinds of problems and thinking that interest us most are often very different. Right now, in the face of an administration that is muzzling scientists, mathematicians need to think about joining forces with scientists to advocate for policies that are important to us as mathematicians/scientists as well as educators and members of society. In November, I wrote a post about what mathematicians should do now in the wake of the surprising presidential election result. This post is a follow-up, more focused on actions scientists are currently taking.

A marcher carries a pro-science sign at the Utah Women's March on Monday, January 23, 2017. Image: Monica Hymas Rasmussen.

A marcher carries a pro-science sign at the Utah Women’s March on Monday, January 23, 2017. “What do we want? Evidence based science! When do we want it? After peer review!” Image: Monica Hymas Rasmussen.

A few days ago, a group of scientists and science lovers started organizing a March for Science on Washington. There are very few details available so far, but you can follow their blog to stay up-to-date. I hope they take seriously the people, especially black scientists, critiquing the organizers and encouraging them to prioritize intersectionality, diversity, and inclusion.

If the word “intersectionality” has you scrambling to find the volume of a Steinmetz solid, don’t worry. If there’s one thing mathematicians should be good at, it’s learning new definitions and how they fit into existing contexts. Alycia Mosley Austin, associate director of the Interdisciplinary Neuroscience Program and assistant dean of graduate recruitment and diversity initiatives at the University of Rhode Island, has a post for scientists new to activism, highlighting resources you can use to get up to speed.

There are many science-related policies Trump has discussed that cause me alarm, but I believe the absolute most crucial one is climate. Climate change is a pressing, urgent problem. It will impact many areas of our lives: economic stability, infectious disease, social justice, food and water safety. We should oppose efforts to silence scientists speaking about climate change and other important scientific issues. That means scientists at the EPA, NASA, national parks, and other organizations must be able to do research and share information with the public regardless. In response to censorship of their social media accounts, some rogue national park rangers created @altNatParkSer (though they have since given it to people who are not employed by the National Park Service). People from other agencies have followed suit. You can find them all on Alice Stollmeyer’s Twistance list.

University of California Riverside mathematician and prolific math and science blogger John Baez has been helping to organize and publicize the Azimuth Climate Data Backup Project to save that important information in the event that government agencies that have collected it are asked to destroy it. He has written about the project in several posts on his blog, starting last December. We can all hope that it is unnecessarily alarmist, but Trump’s first few days have not made me optimistic, and it would truly be devastating to lose that information.

It would also be devastating for us to lose the contributions of our Iranian friends and other immigrants and refugees from Muslim countries. Part of why America’s math and science research are so strong is that we attract some of the best mathematicians and scientists from all over the world. Some came as children in refugee families, some came as adults to study or work. While we speak out about clear attacks on science in the form of intimidation at the EPA and national parks, we should also speak out about the threat to science if we lose the contributions of immigrants and refugees as a result of a travel ban on visitors from majority-Muslim countries. The National Iranian American Council has more details on the potential executive order, and Scott Aaronson has a blog post elaborating on how terrible this would be. ETA: Since I published this post, the executive order has been signed, and it has immediately gone into effect. If you are an academic who opposes it, here is a petition you can sign.

Since the election, I’ve heard more murmurs than ever from mathematicians and scientists thinking about running for office. As far as I know, there’s only one mathematician in Congress, California representative Jerry McNerney. But the website and blog 314 Action, which aims to help STEM professionals speak to government or run for office, is inviting mathematicians to the party by using the first few (decimal) digits of π—the math version of the bat signal—in their name. The AAAS congressional fellowship is another way for mathematicians and scientists to get involved in politics. Applications open in May, so you’ve got a little time to put yours together. ETA: See Karen Saxe’s comment for more information on these fellowships. The AMS sponsors one that is due February 15.

I must admit, dear readers, I’m worried, and I don’t really know what to do. I’d rather disengage, cross my fingers and hope nothing bad happens. When I feel like that, I read University of Hawaii at Manoa mathematician Piper Harron’s reminder to Stay Screaming.

Posted in Events | Tagged , , , , | 3 Comments

More Graph Isomorphism Drama

That plucky graph isomorphism problem is at it again! In November 2015, University of Chicago computer scientist Laszlo Babai announced an algorithm to determine whether two graphs are isomorphic in quasipolynomial time, and there was much rejoicing. (My co-blogger Anna Haensch covered it here at the time.)

But earlier this month, University of Göttingen and CNRS mathematician Harald Helfgott posted on his blog that he had found an error in the proof, and it looked to be a major one. Babai’s algorithm was still a big improvement over earlier algorithms but only ran at subexponential rather than quasipolynomial time. (Complexity jargon got your head spinning? Check out Jeremy Kun’s primers on Big-O notation and P vs NP. There’s also a Wikipedia page on time complexity. He attended Babai’s talk announcing the result in November 2015 and posted about it then, with a few updates since.)

Luckily, Babai has fixed the problem, so people with potentially isomorphic graphs they’d like to check in quasipolynomial time can rejoice once again.

I’ve been keeping up with graph isomorphism news by reading Erica Klarreich’s posts about it on the Quanta Magazine Abstractions blog. She explained the error Helfgott found on January 5th and posted an update on the fix nine days later. I am especially fond of her analogy for quasipolynomial time: “Very roughly speaking, his algorithm carries the graph isomorphism problem almost all the way across the gulf between the problems that can’t be solved efficiently and the ones that can — it’s now splashing around in the shallow water off the coast of the efficiently-solvable problems, whose running time is what computer scientists call ‘polynomial.’”

On Saturday, Helfgott gave a Bourbaki lecture on graph isomorphism. Francophones can watch it on Youtube. (Others can also watch it on Youtube but will understand less of it.) I’ll also be keeping an eye on the Gödel’s Lost Letter and P=NP blog. They’ve been covering Babai’s work on the graph isomorphism problem since he announced it, and if the weather cooperated, they just went to a conference where Babai gave a distinguished lecture on the topic.

Update, January 17, 2017: As he reports on his blog, Helfgott’s Bourbaki article is now on arXiv as well (in French).

Posted in Mathematics and Computing | Tagged , , , , | Leave a comment