Update: Igor has asked about prime-counting and #P at https://cstheory.stackexchange.com/q/43954/95

The International Mathematical Union renames its Nevanlinna Prize (given every four years to major accomplishments in theoretical computer science; see https://en.wikipedia.org/wiki/Nevanlinna_Prize) to the IMU Abacus Medal: https://scilogs.spektrum.de/hlf/imu-abacus-medal/

The article doesn't say why but it's because Nevanlinna was a Nazi sympathizer and collaborator. The prize was named after him in the early 1980s because its funding came from Finland, but Nevanlinna also never had much to do with TCS.

@JordiGH @ptvirgo I started to watch Sense8, but stalled out after getting too distracted by all the racial stereotyping, sometime around when the Jewish diamond dealer showed up. (It wasn't specifically about him, that just brought to my attention how much else of the like was already happening.) Does it get better?

Ono et al prove that almost all Jensen-Pólya polynomials have only real roots; the Riemann Hypothesis is equivalent to the statement that they all do. The same thing works for similar families of polynomials associated with partition functions and proves a conjecture of Chen. See popularized account at https://phys.org/news/2019-05-mathematicians-revive-abandoned-approach-riemann.html, talk slides at http://people.oregonstate.edu/~petschec/ONTD/Talk1.pdf, and paper at https://www.pnas.org/content/early/2019/05/20/1902572116. Via https://mathstodon.xyz/@helger/102138884170343694

New blog post congratulating Bálint Tillman on his successful doctoral defense: https://11011110.github.io/blog/2019/05/21/congratulations-dr-tillman.html

Bálint is a student of Athina Markopoulou working on problems related to the reconstruction of graphs from their joint degree distributions; see the post for more.

The Wikipedia article on Gardens of Eden in cellular automata — https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton) — has now been listed as a Good Article.

@dimpase It's only known up to 18 points and lines: https://oeis.org/A023994

Estimating from the growth rate, there could easily be half a trillion of these things for n=21.

This is the Grünbaum–Rigby configuration (https://en.wikipedia.org/wiki/Gr%C3%BCnbaum%E2%80%93Rigby_configuration), three overlaid regular heptagrams with 21 points and lines, 4 points per line, and 4 lines per point. Klein studied it in the complex projective plane in 1879, but it wasn't known to have a nice real realization until Grünbaum and Rigby (1990). Wikipedia editor "Tomo" (I'll let you figure out who that is) started a new article a month ago, and now it's on the front page of Wikipedia in the "Did you know" section.

Two new blog posts by Brent Yorgey concern the Euler totient function: https://mathlesstraveled.com/2019/05/09/computing-the-euler-totient-function-part-1/ and https://mathlesstraveled.com/2019/05/18/computing-the-euler-totient-function-part-2-seeing-phi-is-multiplicative/

Computing it quickly would break RSA; Brent describes using factoring to do better than brute force. The problem is clearly in #P. I recently visited UCLA where Igor Pak asked me for natural candidates of #P-intermediate problems. I think this is one, and Igor thinks the prime-counting function is another, but neither is very combinatorial. Anyone have better candidates?

@jsiehler Igor Pak gave me the reference "On the complexity of computing the Tutte polynomial of bicircular matroids" (Omer Giménez and Marc Noy, Combin. Probab. Comput. 2006, https://doi.org/10.1017/S0963548305007327), which shows that counting graphs in which each component is a tree + one edge is #P-complete. Your problem is counting graphs of this type with only one component, so it doesn't directly apply, but hints that there may not be a direct formula for the answer like there is for the number of trees.

Also discussed at https://boingboing.net/2019/05/17/denying-cryptographers-problem.html

Prominent cryptographers Adi Shamir and Ross J. Anderson were both denied visas to travel to the US (for a conference and a book awards ceremony respectively). In https://www.schneier.com/blog/archives/2019/05/why_are_cryptog.html Bruce Schneier mentions "two other prominent cryptographers who are in the same boat". Odd and troubling.

For more on Shamir and Anderson see https://en.wikipedia.org/wiki/Adi_Shamir and https://en.wikipedia.org/wiki/Ross_J._Anderson

No maths for Europe: https://plus.maths.org/content/democratic-dilemmas

Sadly, the EU parliament has passed up a chance to find a nice (or even not-so-nice) formula for its apportionment of seats to countries (see https://en.wikipedia.org/wiki/Highest_averages_method for several possible principled methods for doing this), instead opting for back-room deals and numbers pulled out of a hat.

In a recent poll, "56% of Americans said Arabic numerals should not be taught in American schools".

@christianp You might be interested in new Wikipedia article https://en.wikipedia.org/wiki/Hazel_Perfect — according to https://aperiodical.com/2013/03/much-ado-about-noether/ she's your mathematical hero despite the unclear connection with your name.

Of course their internet blockage is hardly the biggest problem with China these days.

I was surprised to find that some of my usually-well-informed friends hadn't even heard of "the largest mass incarceration of the 21st century" and "precursors to genocide", China's concentration camps for its Uighurs (an ethnic group of 11M people in western China). So read and learn: https://www.amnesty.org/en/latest/news/2018/09/china-up-to-one-million-detained/

https://www.theguardian.com/world/2018/dec/07/uighur-leaders-warn-chinas-actions-could-be-precursors-to-genocide

https://www.washingtonpost.com/opinions/global-opinions/china-cant-prettify-the-human-rights-catastrophe-in-xinjiang/2019/03/24/4c844f62-45ca-11e9-90f0-0ccfeec87a61_story.html

https://www.france24.com/en/20190510-reporters-plus-surviving-china-uighur-camps-repression

China is now blocking all language editions of Wikipedia, expanding its previous block which applied only to the Mandarin edition: https://ooni.torproject.org/post/2019-china-wikipedia-blocking/, via https://boingboing.net/2019/05/13/report-china-now-blocks-wikip.html

Did you know that Swiss mathematician Alice Roth invented Swiss cheese? See https://en.wikipedia.org/wiki/Alice_Roth and https://en.wikipedia.org/wiki/Swiss_cheese_(mathematics)

A Swiss cheese is a disk with smaller disks removed, leaving no interior. Scientific American column https://blogs.scientificamerican.com/roots-of-unity/the-serendipity-of-swiss-cheese/ alerted me to this amusing terminology but I think http://www.math.tamu.edu/~boas/courses/618-2015a/roth.pdf gives a clearer idea what they're good for (this exercise shows complex conjugation to be well-behaved on a compact domain but hard to approximate by rational functions).

Algorithms and natural history: https://discrete-notes.github.io/natural-history

In a new blog, Laurent Feuilloley writes about some algorithmic problems on polyhedra coming from the measurement of skulls, diamond cutting, and the use of symmetry to undo deformations of fossils.

Tensor products of graphs can require fewer colors than their factors: https://arxiv.org/abs/1905.02167

This short new preprint by Yaroslav Shitov gives counterexamples to Hedetniemi’s conjecture (https://en.wikipedia.org/wiki/Hedetniemi%27s_conjecture) from 1966. In a new blog post (https://gilkalai.wordpress.com/2019/05/10/sansation-in-the-morning-news-yaroslav-shitov-counterexamples-to-hedetniemis-conjecture/) Gil Kalai explains the construction.

- Home page
- https://www.ics.uci.edu/~eppstein/

I'm a computer scientist at the University of California, Irvine, interested in algorithms, data structures, discrete geometry, and graph theory.

Joined Apr 2017