• Jul 15, 2019

  Linkage

  • Turkey has charged over 700 academics with terrorism for signing a peace petition ($\mathbb{M}$). Among the most severely penalized is Tuna Altınel, a mathematician in France who was arrested visiting family in Turkey, and who has now been imprisoned for over 50 days (via).
• Jul 13, 2019

  Connectivity and finiteness in modal graph logic

  I read with interest Joel David Hamkins’ recent blog post on modal model theory. This week, on a long plane flight home from Italy, I was inspired to play with the modal logic of graphs, in which one describes properties of graphs by simpler properties of their (induced) supergraphs. My interest is less in what this says about set theory and model theory, and more in how expressive this language is: which graph properties can it describe? Joel showed in his post how to describe $k$-colorability in this theory, but I thought it would be of interest to start with something simpler than an $\mathsf{NP}$-complete problem. And what could be simpler for graphs than testing whether a graph is connected or finite?

• Jun 30, 2019

  Linkage

  Ok, some of these are not so much links as mini-reports from SPAA/STOC/FCRC. For an actual conference report, see Lance’s post.

• Jun 21, 2019

  Report from SoCG

  As I mentioned in my previous post, I just finished attending the Symposium on Computational Geometry in Portland. The conference proceedings are open access through LIPIcs.

• Jun 20, 2019

  Portland street art

  I’ve been in Portland, Oregon this week for Computational Geometry Week. Here are a few photos of local street art, the first set I’ve taken with my new Pixel 3 XL cellphone (I neglected to bring an actual camera for this trip):

• Jun 15, 2019

  Linkage for the end of an academic year

  The Spring term just ended at UCI (we’re on a quarter system, so we run later into June and then start up again later in September than most other US universities). I haven’t yet turned in my grades, but I can already feel summer setting in.

• Jun 11, 2019

  Dancing arc-quadrilaterals

  Several of my past papers concern Lombardi drawing, which I and my coauthors named after conspiracy-theory artist Mark Lombardi. In this style of drawing, edges are drawn as circular arcs, and must meet at equal angles around every vertex. Not every graph has such a drawing, but many symmetrical graphs do (example below: the smallest zero-symmetric graph with only two edge orbits).

• Jun 7, 2019

  A little knowledge can make the next step harder

  Suppose you have a fill-in-the-unknowns puzzle, like Sudoku. Can making some deductions and filling in those parts of the puzzle make the whole thing harder to solve than it was before you started? Sometimes, yes!

• May 31, 2019

  Linkage

  • No maths for Europe ($\mathbb{M}$). 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, instead opting for back-room deals and numbers pulled out of a hat.
• May 27, 2019

  Shattering and quasipolynomiality

  An inadequately-explained phenomenon in computational complexity theory is that there are so few natural candidates for $\mathsf{NP}$-intermediate problems, problems in $\mathsf{NP}$ but neither in $\mathsf{P}$ nor $\mathsf{NP}$-complete. Of course, if $\mathsf{P}=\mathsf{NP}$ there are none, and the dichotomy theorem implies that there are no intermediate Boolean constraint satisfaction problems. But there are a lot of other types of problems in $\mathsf{NP}$, and a theorem of Ladner¹ shows that there should be an infinite hierarchy of degrees of hardness within $\mathsf{NP}$. So where are all the members of this hierarchy, and why are they so shy?

  1. Ladner, Richard (1975), “On the structure of polynomial time reducibility”, J. ACM 22 (1): 155–171. ↩

subscribe via RSS