Game of Sloanes

Emily King recently launched an online competition to find the best packings of points in complex projective space. The so-called Game of Sloanes is concerned with packing n points in \mathbf{CP}^{d-1} for d\in\{2,\ldots,7\} and for n\in\{d+2,\ldots,49\}. John Jasper, Emily King and I collaborated to make the baseline for this competition by curating various packings from the literature and then numerically optimizing sub-optimal packings. See our paper for more information:

J. Jasper, E. J. King, D. G. Mixon, Game of Sloanes: Best known packings in complex projective space

If you have a packing that improves upon the current leader board, you can submit your packing to the following email address:

asongofvectorsandangles [at] gmail [dot] com

In this competition, you can win money if you find a new packing that achieves equality in the Welch bound; see this paper for a survey of these so-called equiangular tight frames (ETFs).

Continue reading Game of Sloanes

Advertisements

Some news regarding the Paley graph

Let \mathbb{F}_p denote the field with p elements, and let Q_p denote the multiplicative subgroup of quadratic residues. For each prime p\equiv 1\bmod 4, we consider the Paley graph G_p with vertex set \mathbb{F}_p, where two vertices are adjacent whenever their difference resides in Q_p. For example, the following illustration from Wikipedia depicts G_{13}:

800px-Paley13.svg

The purpose of this blog entry is to discuss recent observations regarding the Paley graph.

Continue reading Some news regarding the Paley graph

A few paper announcements

This last semester, I was a long-term visitor at the Simons Institute for the Theory of Computing. My time there was rather productive, resulting in a few (exciting!) arXiv preprints, which I discuss below.

1. SqueezeFit: Label-aware dimensionality reduction by semidefinite programming.

Suppose you have a bunch of points in high-dimensional Euclidean space, some labeled “cat” and others labeled “dog,” say. Can you find a low-rank projection such that after projection, cats and dogs remain separated? If you can implement such a projection as a sensor, then that sensor collects enough information to classify cats versus dogs. This is the main idea behind compressive classification.

Continue reading A few paper announcements

Partisan gerrymandering with geographically compact districts

The following tweet has been making the rounds on social media:

Notice that since the Democrats won overall, it would be impossible for Republicans to win all seven districts, no matter how the map was drawn. As such, you might say that Alabama has been gerrymandered as effectively as possible. Sure enough, you can find the usual tell-tale signs of gerrymandering: Some of the district boundaries exhibit strange jagged portions — these portions undoubtedly maneuver to include some parts of the map while avoiding others.

Continue reading Partisan gerrymandering with geographically compact districts

An impossibility theorem for gerrymandering

I just posted my latest paper on the arXiv, this one co-authored with Boris Alexeev. In this paper, we study a new technique that is currently being reviewed by the Supreme Court to detect unconstitutional gerrymandering. Recall that gerrymandering refers to the process whereby electoral district boundaries are manipulated in order to reduce or increase the voting power of a certain group of people. Gerrymandered districts are frequently detected by their bizarre shape. Here are some noteworthy examples (from Wikipedia):

Last year, the Supreme Court found NC-1 and NC-12 (the first two districts above) to be the result of unconstitutional racial gerrymandering. We’ll discuss IL-4 (the district on the right) later.

Continue reading An impossibility theorem for gerrymandering

Monte Carlo approximation certificates for k-means clustering

This week, I visited Afonso Bandeira at NYU to give a talk in the MaD seminar on the semidefinite relaxation of k-means. Here are the slides. The last part of the talk is very new; I worked it out with Soledad Villar while she visited me a couple weeks ago, and our paper just hit the arXiv. In this blog entry, I’ll briefly summarize the main idea of the paper.

Suppose you are given data points \{x_i\}_{i\in T}\subseteq\mathbb{R}^m, and you are tasked with finding the partition C_1\sqcup\cdots\sqcup C_k=T that minimizes the k-means objective

\displaystyle{\frac{1}{|T|}\sum_{t\in[k]}\sum_{i\in C_t}\bigg\|x_i-\frac{1}{|C_t|}\sum_{j\in C_t}x_j\bigg\|^2\qquad(T\text{-IP})}

(Here, we normalize the objective by |T| for convenience later.) To do this, you will likely run MATLAB’s built-in implementation of k-means++, which randomly selects k of the data points (with an intelligent choice of random distribution), and then uses these data points as proto-centroids to initialize Lloyd’s algorithm. In practice, this works very well: After running it a few times, you generally get a very nice clustering. But when do you know to stop looking for an even better clustering?

Continue reading Monte Carlo approximation certificates for k-means clustering

Optimal line packings from finite group actions

Joey Iverson recently posted our latest paper with John Jasper on the arXiv. This paper can be viewed as a sequel of sorts to our previous paper, in which we introduced the idea of hunting for Gram matrices of equiangular tight frames (ETFs) in the adjacency algebras of association schemes, specifically group schemes. In this new paper, we focus on the so-called Schurian schemes. This proved to be a particularly fruitful restriction: We found an alternate construction of Hoggar’s lines, we found an explicit representation of the “elusive” 7\times 36 packing from the real packings paper (based on a private tip from Henry Cohn), we found an 11\times 66 packing involving the Mathieu group M_{11} (this one beating the corresponding packing in Sloane’s database), we found some low-dimensional mutually unbiased bases, and we recovered nearly all small sized ETFs. In addition, we constructed the first known infinite family of ETFs with Heisenberg symmetry; while these aren’t SIC-POVMs, we suspect they are related to the objects of interest in Zauner’s conjecture (as in this paper, for example). This blog entry briefly describes the main ideas in the paper.

Continue reading Optimal line packings from finite group actions