A fearful sphere, whose center is everywhere

In a beautiful article, The Mathematics of Doodling, Ravi Vakil poses two problems:

1. Given a random curve, like a doodle, in what sense do closed curves successively drawn around the doodle become more and more circular?
2. How do geometric invariants, like area and volume, of the closed curves relate with the original shape and with each other?

2-butterfly derangement

The hallmark of the Cooley-Tukey algorithm for  Fast Fourier Transform is the butterfly network, which helps reduce O(N^2) computations to O(NlogN). Butterflies are very special graphs entangled in routing [Arora], switching [Chung], shuffling [Yang], and mixing [Czumaj].

Three butterflies – FFT flow graph, shuffling network, and a nonblocking interconnect

Maximum weighted independent set – connected component

Given a weighted connected component, what is the weight of of the maximum independent set, and how many different sets have this weight? A Petersen graph GP(5, 2) with zero vertex weights has three maximal subsets by size, 0 maximum set weight but 76 distinct independent sets with this weight.

Maximum weighted independent set – singletons and forest

Gus wants to open franchises of his restaurant, Los Pollos Hermanos, along Central Avenue. There are n possible locations for franchises, where location i is at mile i on Central. Each location i > 1, is thus a distance of 1 mile from the previous one. There are two rules.

1. At each location, there can be at most one restaurant, and the profit of a restaurant at location i is p_i.
2. Any two restaurants must be at least 2 miles apart.

Generalized heaps

Min-max heaps were introduced in [ASSS86] as an efficient way to support heap operations for both minimum and maximum values. Structurally, the min-max heap levels alternate between min-heap condition and max-heap, and hence evaluates grandchildren/grandparents during insertion or search. Min-max heaps can also be generalized to find the k-th smallest element in O(1) time.

Rational numbers in decimal

In decimal representation, rational numbers either terminate after a finite number of digits or produce a repeating sequence. Conversely, any repeating decimal can be converted into a rational number e.g. (10 * 0.333.. – 0.333…) / 9 = 1/3.

Obituaries: Herbert Scarf (1930 – 2015)

In addition to inventory policy, Scarf had at least four more major breakthroughs. Perhaps his most famous discovery is the Scarf algorithm.  Arrow and Debreu had proved that the equations describing economic equilibrium always have a solution when goods are divisible, but they were baffled by the problem of how to find one, except in special cases. The Scarf algorithm always finds an equilibrium, no matter how complicated the economy. This gave applied economists the ability to work with much more realistic models of the economy and thus to predict the consequences of major policy reforms including NAFTA and the U.S. tax system.

In memoriam: Herbert Scarf, pioneering economist and inspiring teacher

A Terrible Summary – The Risks of Reporting on Research

Tags

econometrics, no-regret learning, sponsored search, value inference

Two reasons why I think that A Beautiful Algorithm? The Risks of Automating Online Transactions is way off in its report on an otherwise interesting paper [Econometrics for Learning Agents].

Continued Fractions

Tags

continued fractions, Fibonacci numbers, matrix formulation

Farey tessellation in complex plane

In fact, the matrix formulation of Fibonacci numbers mentioned before can be generalized to represent any 2-D matrix and, by way of continued fractions, any real number – not just the golden mean. This post is inspired from David Austin’s AMS feature column and draws on Phillipe Flajolet’s beautiful survey on continued fractions to set the stage for a future post on Diophantine approximation.

Obituaries: Alexander Grothendieck (1928–2014)

More will be told of this story as his voluminous writings from the hinterland are being read. But between 1945 and 1970 he published mathematics of unparalleled sweep and power, conveying escalations of abstraction to the solution of concrete problems, and this is the part we wish to appreciate.

Alexander Grothendieck 1928–2014 | Gödel’s Lost Letter and P=NP.