Posts

October 01, 2014

+
3:09 AM | Linkage for the end of September
Algomation animated algorithms (G+)Rush hour video, or, what our robot-driven future will be like (G+)The Washington Post rants about those evil student pirates, but neglects to mention the free alternatives (G+)A song video about knots, from the low-dimensional topology blog (G+)Fun hex grid facts, via MF (G+)SODA 2015 accepted papers (G+)KaTeX, a lobotomized but fast web math renderer (G+)Against laptops in lectures, via MF (G+)David Wade’s ‘Fantastic Geometry’ – The […]

September 29, 2014

+
3:16 AM | University of Würzburg graffiti
I neglected to pack my camera and its new lens with me for the trip to GD (oops), and anyway most of the time the weather wasn't very conducive to photography. But I did take a couple of cellphone snapshots of graffiti/murals on the University of Würzburg campus. This one, if Google translate is to be believed, proclaims Würzburg as the city of young researchers; it's on the wall of the Mensa where we ate lunch every day.And here's some advice to the students starting the new term, […]

September 28, 2014

+
1:29 AM | Report from Graph Drawing
I'm currently in the process of returning* from Würzburg, Germany, where I attended the 22nd International Symposium on Graph Drawing (GD 2014) and was one of the invited speakers at the associated EuroGIGA/CCC Ph.D. school on graph drawing.The format for the Ph.D. school was three one-hour lectures in the morning and three hours of working on exercises in the afternoon, for two days. My contribution was a high-level overview of graph drawing methods that involve curves (an updated version […]

September 21, 2014

+
1:05 AM | Which polycubes have planar graphs?
Joe Malkevitch recently asked me: which polycubes have planar graphs?By a polycube, I mean a set of unit cubes in the three-dimensional integer lattice whose dual graph (with vertices for cubes and edges for cubes that share a square with each other) is connected; Malkevitch had a more restrictive definition in mind in which the boundary of the union of the cubes is a connected manifold, but that turns out not to make a difference for this problem. The graph of a polycube is formed by the […]

September 16, 2014

+
6:20 AM | Linkage
Unexpected shapes in smoke plumes, as photographed by Thomas Herbrich (G+)ISAAC 2014 and COCOA 2014 accepted paper lists (G+)FOCS 2014 program and best paper winners (G+)Kinetic sculpture made of wooden balls on threads, with some extensive software simulation behind its design (G+)How a 19th century math genius taught us the best way to hold a pizza slice, or, a practical application of the theorem that when a flat surface is embedded in 3d, it remains flat in at least one direction […]

September 13, 2014

+
9:57 PM | Bren Hall, East Stairs
Just some test shots with my new travel lens (Canon's 17-40/F4 L, replacing a mysteriously nonfunctional and optically not as good 17-85IS).

September 10, 2014

+
5:15 AM | Algorithmic representative democracy
Did you ever wonder why different states of the US have the numbers of representatives in congress that they do? It's supposed to be proportional to population but that's not actually true: for instance the ratio of representatives to population is about 40% higher in Montana than California. What formula or algorithm do they use to pick the numbers?This has varied over the years but, Wikipedia tells me, currently it's the Huntington–Hill method. One way of describing this is by a simple […]

September 06, 2014

+
6:47 AM | Efficiency of Rado graph representations
The Rado graph has interesting symmetry properties and plays an important role in the logic of graphs. But it's an infinite graph, so how can we say anything about the complexity of algorithms on it?There are algorithmic problems that involve this graph and are independent of any representation of it, such as checking whether a first-order logic sentence is true of it (PSPACE-complete). But I'm interested here in problems involving the Rado graph where different ways of constructing and […]
1
8 Results