A graph coloring problem from quantum physics (with prizes!)

What follows is a nice problem that was recently posed by Mario Krenn. Progress on this problem may lead to new insights in quantum physics (see this, this, this, and this for details). In addition, Mario has announced two cash prizes to encourage work in this direction. (!)

Consider a weighted and edge-colored bipartite graph G=(A,B,E,k,w) consisting of

  • disjoint vertex sets A and B,
  • an edge set E\subseteq A\times B,
  • an edge coloring k\colon E\to\mathbb{N}, and
  • a complex vertex weighting w\colon A\to\mathbb{C}.
Continue reading A graph coloring problem from quantum physics (with prizes!)

MATH 2568: Linear Algebra

This spring, I’m teaching a first-semester course on Linear Algebra at the Ohio State University.

Click here for a draft of my lecture notes.

I will update the above link periodically. Feel free to comment below.

Update #1: Added two sections to Chapter 1.

Update #2: Updated Chapter 1 and started Chapter 2.

Update #3: Added a section to Chapter 2.

Update #4: Added another section to Chapter 2.

Update #5: Added another section to Chapter 2.

Update #6: Added Chapter 3 and started Chapter 4.

Update #7: Updated Section 4.1.

Update #8: Added Section 4.2.

Update #9: Started Section 4.3.

Update #10: Added Section 4.4.

Spherical codes and designs

Later this month, Hans Parshall will participate in a summer school on “Sphere Packings and Optimal Configurations.” In preparation for this event, Hans was assigned the task of writing lecture notes that summarize the main results of the following paper:

P. Delsarte, J. M. Goethals, J. J. Seidel,

Spherical codes and designs,

Geometriae Dedicata 6 (1977) 363–388.

I found Hans’ notes to be particularly helpful, so I’m posting them here with his permission. I’ve lightly edited his notes for formatting and hyperlinks.

Without further ado:

Continue reading Spherical codes and designs

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

MATH 8610: Mathematics of Data Science

This spring, I’m teaching a graduate-level special topics course called “Mathematics of Data Science” at the Ohio State University. This will be a research-oriented class, and in lecture, I plan to cover some of the important ideas from convex optimization, probability, dimensionality reduction, clustering, and sparsity.

Click here for a draft of my lecture notes.

The current draft consists of a chapter on convex optimization. I will update the above link periodically. Feel free to comment below.

UPDATE #1: Lightly edited Chapter 1 and added a chapter on probability.

UPDATE #2: Lightly edited Chapter 2 and added a section on PCA.

UPDATE #3: Added a section on random projection.

UPDATE #4: Lightly edited Chapter 3. The semester is over, so I don’t plan to update these notes again until I teach a complementary special topics course next year.

UPDATE #5: As mentioned above, I’m teaching a complementary installment of this class this semester. I fixed several typos throughout, and I added a new section on embeddings from pairwise data.

UPDATE #6: Added a section on the clique problem.

UPDATE #7: Added a section on the Lovasz number.

UPDATE #8: Added a section on planted clique.

UPDATE #9: Added sections on maximum cut and minimum normalized cut.

UPDATE #10: Added a section on k-means clustering.

UPDATE #11: Started a chapter on compressed sensing.

UPDATE #12: Started a section on uniform guarantees.

UPDATE #13: Started a chapter on matrix analysis.

UPDATE #14: Started a section on matrix representations.

UPDATE #15: Started a section on spectral theory.

UPDATE #16: Added to the section on spectral theory.

UPDATE #17: Added more to the section on spectral theory.

UPDATE #18: Added even more to the section on spectral theory.

UPDATE #19: Finished the section on spectral theory and added a section on tensors.

UPDATE #20: Finished the section on tensors.

UPDATE #21: Added a section on random graphs.

A neat application of the polynomial method

Two years ago, Boris Alexeev emailed me a problem:

Let n \geq 2.  Suppose you have n^2 distinct numbers in some field.  Is it necessarily possible to arrange the numbers into an n\times n matrix of full rank?

Boris’s problem was originally inspired by a linear algebra exam problem at Princeton: Is it possible arrange four distinct prime numbers in a rank-deficient 2\times 2 matrix? (The answer depends on whether you consider -2 to be prime.) Recently, Boris reminded me of his email, and I finally bothered to solve it. His hint: Apply the combinatorial nullstellensatz. The solve was rather satisfying, and if you’re reading this, I highly recommend that you stop reading here and enjoy the solve yourself.

Continue reading A neat application of the polynomial method

Notes on Zauner’s conjecture

Last week, I visited Joey Iverson at the University of Maryland, and we spent a lot of time working through different approaches to Zauner’s conjecture. In general, my relationship with this problem is very similar to Steve Flammia‘s description, as paraphrased by smerkel on Physics Stack Exchange:

[Flammia described] the SIC-POVM problem as a “heartbreaker” because every approach you take seems super promising but then inevitably fizzles out without really giving you a great insight as to why.

Case in point, Joey and I identified a promising approach involving ideas from our association schemes paper. We were fairly optimistic, and Joey even bet me $5 that our approach would work. Needless to say, I now have this keepsake from Joey:

5dollars.png

While our failure didn’t offer any great insights (as Flammia predicted), the experience forced me to review the literature on Zauner’s conjecture a lot more carefully. A few things caught my eye, and I’ll discuss them here. Throughout, SIC denotes “symmetric informationally complete line set” and WH denotes “the Weyl-Heisenberg group.”

Continue reading Notes on Zauner’s conjecture

Introduction to the polynomial method (and other similar things)

The polynomial method has made some waves recently (see this and that, for instance), and last week, Boris Alexeev gave a very nice talk on various applications of this method. This post is loosely based on his talk. All errors are my own.

It’s hard to pin down what exactly the polynomial method is. It’s a technique in algebraic extremal combinatorics, where the goal is to provide bounds on the sizes of objects with certain properties. The main idea is to identify the desired cardinality with some complexity measure of an algebraic object (e.g., the dimension of a vector space, the degree of a polynomial, or the rank of a tensor), and then use algebraic techniques to estimate that complexity measure. If at some point you use polynomials, then you might say you applied the polynomial method.

What follows is a series of instances of this meta-method.

Continue reading Introduction to the polynomial method (and other similar things)

The HRT Conjecture

A couple of weeks ago, I attended a workshop hosted by Darrin Speegle on the HRT Conjecture. First posed twenty years ago by Chris Heil, Jay Ramanathan, and Pankaj Topiwala in this paper, the conjecture states that every finite collection of time-frequency shifts of any nonzero function in L^2(\mathbb{R}) is linearly independent. In this post, I will discuss some of the key ideas behind some of the various attempts at chipping away at HRT, and I’ll describe what appear to be fundamental barriers to a complete solution. For more information, see these survey papers: one and two.

First, some notation: Denote the translation-by-a and modulation-by-b operators by

(T_af)(x):=f(x-a),\qquad (M_bf)(x)=e^{2\pi i bx}f(x),

respectively. Then the formal conjecture statement is as follows:

The HRT Conjecture. For every 0\neq f\in L^2(\mathbb{R}) and every finite \Lambda\subset\mathbb{R}^2, the collection \{M_bT_af\}_{(a,b)\in\Lambda} is linearly independent.

What follows are some of the popular methods for tackling HRT:

Continue reading The HRT Conjecture

Clustering noisy data with semidefinite relaxations

Soledad Villar recently posted our latest paper on the arXiv (this one coauthored by her advisor, Rachel Ward). The paper provides guarantees for the k-means SDP when the points are drawn from a subgaussian mixture model. This blog entry will discuss one of the main ideas in our analysis, which we borrowed from Guedon and Vershynin’s recent paper.

Let’s start with two motivating applications:

The first application comes from graph clustering. Consider the stochastic block model, in which the n vertices are secretly partitioned into two communities, each of size n/2, and edges between vertices of a common community are drawn iid with some probability p, and all other edges are drawn with probability q<p. The goal of community estimation is to estimate the communities given a random draw of the graph. For this task, you might be inclined to find the maximum likelihood estimator for this model, but this results in an integer program. Relaxing the program leads to a semidefinite program, and amazingly, this program is tight and recovers the true communities with high probability when p=(\alpha\log n)/n and q=(\beta\log n)/n for good choices of (\alpha,\beta). (See this paper.) These edge probabilities scale like the threshold for connected Erdos-Renyi graphs, and this makes sense since we wouldn’t know how to assign vertices in isolated components. If instead, the probabilities were to scale like 1/n, then we would be in the “giant component” regime, so we’d still expect enough signal to correctly assign a good fraction of the vertices, but the SDP is not tight in this regime.

Continue reading Clustering noisy data with semidefinite relaxations