Ann will be missed

Ann Yasuhara was a mathematician and a complexity theorist, who passed away this June 11th. She lived over half of her 82 years in Princeton, and was a member of the faculty of computer science at Rutgers since 1972.

Today Ken and I send our thoughts and condolences to Ann’s husband Mitsuru Yasuhara, her family, and her many friends—Ann will be missed—she was special.

I have known Ann for what seems like an uncountable amount of time. She was always kind to everyone—everyone—and we all miss her. She had a wonderful laugh and no doubt brought smiles to many over her 82 years. Ken remembers meeting her in the 1980s. Ann and her husband and her student Elaine Weyuker also attended Princeton’s centennial celebration for Alan Turing two years ago.

Her obituary notes that she and Mitsuru settled in Princeton in 1970, but traveled widely while pursuing interests in music and art and Nature as well as mathematics. Alumni of her alma mater, Swarthmore College, posted a note of gratitude. Just today, the Princeton Comment website has posted a list of organizations she supported.

## Ann’s Work I

As a Quaker and social advocate, Ann was against all forms of violence and all forms of injustice. She co-founded several groups, based in Princeton, that put her beliefs into action. One of them, “Silent Prayers for Peace,” keeps a vigil every Wednesday in Palmer Square, while “Not In Our Town” fights racism and bullying. The Swarthmore item remarks on friends calling her “Mountain Woman” and quotes the Princeton obit:

Most recently she enthusiastically supported—and went on protests with—the nonviolent direct action group, Earth Quaker Action Team (EQAT), which works to end mountaintop removal coal mining. On her 79th birthday, she protested on a strenuous mountain climb in West Virginia mining country. In January, just before she was diagnosed with cancer, the Philadelphia-based group honored her as one of its outstanding “wise elders.”

After experience with a local family who came from Guatemala, Ann joined those founding the Latin American Legal Defense & Education Fund, Inc., based in New Jersey. She is still listed on their Advisory Council.

Ann also kept a Facebook page, and her last entry, this past January, says something interesting about commitment and works:

[T]here is a similar issue for all (most?) aspects of Quakerism—there are deep, not so easy to articulate, basics, and coming to know and wrestle with them takes a long time—maybe a lifetime. So, we want to give some short cuts, but in doing so, we may may be delineating a path that doesn’t really reach into the basic territory. This difficulty is an important example of the tension between covenant and enumeration or contract.

## Ann’s Work II

Ann was indeed a mathematician who worked on logic and its relationship to computational theory. Ann was the PhD advisor to Frank Hawrusik, Venkataraman Natarajan, and Elaine Weyuker. I would imagine that she made a great and caring advisor.

Ann’s own 1964 PhD thesis was on foundational issues, as was her textbook. Indeed her book Recursive Function Theory and Logic is one of my favorites, and I mentioned it in a recent post.

In order to understand what Ann’s book was about, what her research was about, and what she was about, we need to understand complexity theory in the 1960’s. This was well before the ${\mathsf{P=NP}}$ question, before random methods, before quantum, before many of the mainstream topics that we know and love. In these early days the focus was on the structure of recursive functions. Mathematicians were well aware that recursive functions were too large a class of functions, even though they were “computable.”

Primitive recursive functions were a much weaker subset that contained still many very powerful functions. In Ann’s book she studied these functions in great detail. One was the Grzegorczyk hierarchy, named after Andrzej Grzegorczyk: this hierarchy divides the primitive functions into a series of higher and higher classes of functions. Roughly the levels of this hierarchy correspond to growth rates of functions: lower levels grow slower than higher levels. For example, the class of elementary functions, is the part of the hierarchy that corresponds to the union of the exponential hierarchy.

Of course today we consider even just functions that take ${2^{n}}$ time to compute as not really elementary, in the sense that we usually cannot compute them in practice. But elementary includes

$\displaystyle 2^{2^{2^{n}}}$

for example.

## Ongoing ${W(r,k)}$

A nice example of a natural occurrence of this hierarchy is the function ${W(r,k)}$. The famous theorem of Bartel van der Waerden states that for any ${r,k}$ there is some number ${N}$ so that if the integers

$\displaystyle 1,2,\dots, N$

are colored with ${r}$ colors then there are at least ${k}$ integers in an arithmetic progression that all have the same color. The least ${N}$ is the value of ${W(r,k)}$.

The initial proof showed that ${W(r,k)}$ was well defined, was a recursive function. Later in a famous paper Saharon Shelah showed that ${W}$ was in the Grzegorczyk hierarchy—it was primitive recursive. The original proof of the existence of ${W(r,k)}$ used a double induction which lead to a non-primitive recursive bound. Shelah needed to avoid such a double recursion to get ${W}$ into the Grzegorczyk hierarchy, which he did in a clever way.

Later, in a breakthrough result Timothy Gowers lowered its place in the hierarchy by a huge jump:

$\displaystyle W(r,k) \le 2^{2^{r^{2^{2^{k+9}}}}}.$

This was not “just” primitive recursive, but was elementary. That is elementary in the sense of the Grzegorczyk hierarchy, not in the nature of the proof.

One of the great open problems is to get closer to the best lower bounds—bounds only slightly better than what follow from using a random coloring of the ${N}$-many integers. This is one of the great mysteries of complexity theory on the “high” end, but may mirror issues on the lower end.

In any event, the structure of this hierarchy and others like it were the things that Ann worked on her whole life. Read her textbook—even after almost fifty years, there are many interesting nuggets in there about primitive recursive functions.

## Open Problems

Again our best thoughts to all of Ann’s family and friends.

1. July 1, 2014 10:24 pm

sub though for thought in even thought they were “computable”

July 2, 2014 7:35 am

Jon

Thanks

3. July 2, 2014 1:54 pm

What an incredibly inspiring life, in both mathematics and in working for justice.

Thank you, Ann Yasuhara.

July 2, 2014 3:27 pm

Ann helped me quite a lot in my first job (as an assistant professor in the Rutgers computer science department). Thanks so much Ann. Rest in peace.

July 4, 2014 7:25 pm

Ann was one of the kindest persons I ever knew. She helped me so much during my stay at Rutgers. I can safely say that I would not have finished if she wasn’t around during that time. I miss her very much. She was always speaking up against injustice….. She will be missed by everyone whose life she touched.