User ashley montanaro - MathOverflow

A graph parameter possibly related to treewidth

2012-10-04T14:44:14Z

(Cross-posted from the Theoretical Computer Science StackExchange site after there was no conclusive answer after a week.)

I am interested in graphs on $n$ vertices which can be produced via the following process.

Start with an arbitrary graph $G$ on $k\le n$ vertices. Label all the vertices in $G$ as unused.
Produce a new graph $G'$ by adding a new vertex $v$, which is connected to one or more unused vertices in $G$, and is not connected to any used vertices in $G$. Label $v$ as unused.
Label one of the vertices in $G'$ to which $v$ is connected as used.
Set $G$ to $G'$ and repeat from step 2 until $G$ contains $n$ vertices.

Call such graphs "graphs of complexity $k$" (apologies for the vague terminology). For example, if $G$ is a graph of complexity 1, $G$ is a path.

I would like to know if this process has been studied before. In particular, for arbitrary $k$, is it NP-complete to determine whether a graph has complexity $k$?

This problem appears somewhat similar to the question of whether $G$ is a partial $k$-tree, i.e. has treewidth $k$. It is known that determining whether $G$ has treewidth $k$ is NP-complete. However, some graphs (stars, for example) may have much smaller treewidth than the measure of complexity discussed here.

Unbalancing lights in higher dimensions

2011-03-24T19:26:31Z

In ''The Probabilistic Method'' by Alon and Spencer, the following unbalancing lights problem is discussed. Given an $n \times n$ matrix $A = (a_{ij})$, where $a_{ij} = \pm 1$, we want to maximise the quantity

$x^T A y = \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i y_j$

over all $n$-dimensional vectors $x$, $y$ such that $x_i,y_j = \pm 1$. The name of the problem comes from interpreting $A$ as a grid of lights that are on or off, and $x$ and $y$ as sets of light switches, each associated with a row or column (respectively); flipping a switch flips all lights in that row or column, and the goal is to maximise the number of lights switched on.

Let $m(A)$ be the maximum of $x^T A y$ over $x$ and $y$ such that $x_i,y_j = \pm 1$. As Alon and Spencer discuss, for any $A$ it is possible to show that $m(A) \ge C n^{3/2}$ for some constant $0<C<1$ . On the other hand, there is an explicit family of matrices $A$ such that $m(A) = n^{3/2}$.

It is natural to generalise this problem to $n \times n \times \dots \times n$ arrays $A$ containing $\pm 1$ entries, writing

$A(x^1,\dots,x^d) := \sum_{i_1,\dots,i_d=1}^n a_{i_1\dots i_d} x^1_{i_1} x^2_{i_2} \dots x^d_{i_d}$

and defining $m(A)$ as the maximum of $A(x^1,\dots,x^d)$ over $x^1,\dots,x^d$, each of which is again an $n$-dimensional vector of $\pm 1$'s. Now it is known (and fun to prove!) that for this "$d$-dimensional" variant, one can always achieve $m(A) \ge C^d n^{(d+1)/2}$ for some universal constant $C$ between 0 and 1, and on the other hand there exists a family of $A$'s with $m(A) = n^{(d+1)/2}$.

My question is: can the lower bound be improved to $m(A) \ge C n^{(d+1)/2}$ for some universal constant $C>0$? Or even just improved so that the dependence on $d$ is subexponential? Conversely, can the upper bound be reduced?

Background

Finding a lower bound on $m(A)$ in the more general case where $A$ is an arbitrary bilinear form was considered by Littlewood back in 1930. The bound above for the $d$-dimensional case is a special case of a bound for general $d$-linear forms which was proven later by Bohnenblust and Hille. In the functional analysis literature, the quantity $m(A)$ is known as the injective tensor norm of $A$; this norm, and the above results, are discussed extensively in the book Analysis in Integer and Fractional Dimensions by Ron C. Blei. However, I could not find any information about whether the bounds can be improved.

Answer by Ashley Montanaro for Unbalancing lights in higher dimensions

2012-09-01T22:30:42Z

Belatedly answering my own question: Pellegrino and Seoane-Sepulveda have shown the lower bound that $m(A) \ge n^{(d+1)/2}/\text{poly}(d)$. As far as I know, it is still open whether the $\text{poly}(d)$ term can be replaced with a universal constant.

Answer by Ashley Montanaro for Are almost commuting hermitian matrices close to commuting matrices (in the 2-norm)?

2011-06-21T13:45:48Z

There is a recent paper by Glebsky titled "Almost commuting matrices with respect to normalized Hilbert-Schmidt norm" which shows that this is indeed true for any $k$ for Hermitian matrices (and in fact also unitary and normal matrices).

Binary matrices with constant row and column sums

2010-08-25T08:12:28Z

My question is about $m \times n$ binary matrices (aka $\{0,1\}$ -matrices), whose rows all sum to the same value, and whose columns all sum to the same value (but these two values may be different).

The first question is simply: is there a standard name for such matrices? They correspond to the biadjacency matrices of so-called "biregular bipartite graphs", but this terminology doesn't appear to be commonly used.

Second, are there any "interesting" constructions of families of such matrices, in particular that are connected to other combinatorial objects?

Two simple examples of constructions of these matrices are the $\binom{n}{k} \times n$ matrix whose rows consist of every $n$-bit string with Hamming weight $k$; and the $2^n \times 2^n$ Sylvester-Hadamard matrices with the first row and column removed.

I did find a paper by Brualdi titled "Matrices of Zeros and Ones with Fixed Row and Column Sum Vectors", but this seems to be more concerned with the question of existence of these matrices, rather than constructing them.

Answer by Ashley Montanaro for Enumerative algorithm through inclusion-exclusion

2010-09-12T09:55:22Z

There has been some research on algorithms for approximate inclusion-exclusion, in the following sense. If we know the size of all intersections between any $2 \le k \le n$ sets in some family of $n$ sets, we can compute the size of the union of all $n$ sets in the family exactly, by inclusion-exclusion. But what if we only want to approximate the size of the union?

Linial and Nisan have shown that a good approximation can be found if we just know the size of all $k$-wise intersections, for $k=O(\sqrt{n})$. Sherstov has recently extended this to computing more general functions than just the size of the union (where how big $k$ needs to be depends on the function to be computed).

Answer by Ashley Montanaro for Are there any known quantum algorithms that clearly fall outside a few narrow classes?

2010-07-28T10:11:59Z

While most famous quantum algorithms fall into your categories (2)-(4) ("linear algebra" isn't especially informative, as all of quantum computation can be understood as an application of linear algebra...), there are some others that don't.

First, there's an algorithm of Childs et al that uses a quantum walk to traverse a graph in polynomial time, for which any classical algorithm requires exponential time. This relies on the fact that quantum walks can hit exponentially faster than classical random walks. There are a number of other algorithms based around quantum walks; I guess you could characterise these as "quantum search", but some have a different feel to them.

Second, there are quantum algorithms for approximating the Jones polynomial and other graph invariants (see, for example, the paper of Aharonov, Jones and Landau, or Section X of the paper by Childs and van Dam you linked to). These algorithms essentially work by encoding the problem instance to be solved directly into a quantum circuit.

Third, there is an algorithm of Harrow, Hassidim and Lloyd which calculates properties of solutions to large systems of linear equations exponentially more efficiently. The main ingredient that goes into this (phase estimation) is also used in algorithms for factoring etc, but the application seems very different.

There are also some algorithms which may not achieve especially large speed-ups, but which demonstrate different design techniques. For example, there's a nice algorithm of Hoyer, Neerbek and Shi that solves the task of search in an ordered list somewhat faster than classical binary search. The algorithm is based on searching a number of subtrees of a binary tree in quantum parallel. I should also mention a nice algorithm of van Dam (quant-ph/9805006) which demonstrates that an n bit string can be read from an oracle using just over n/2 quantum queries.

Finally, there are algorithms for purely quantum information theoretic tasks, which are by their nature different again. In particular, the algorithm of Bacon, Chuang and Harrow for the Schur transform has a number of applications in quantum information theory (eg. state estimation, entanglement concentration and communication without a shared reference frame).

Comment by Ashley Montanaro

2012-10-05T13:58:00Z

Thanks for those great pictures, which do follow the rules (unless I've made a mistake myself!).

Comment by Ashley Montanaro

2012-10-05T09:10:30Z

And thanks for the comment about degeneracy -- it does seem like a similar concept, I should try to think whether it's related.

Comment by Ashley Montanaro

2012-10-05T09:01:22Z

I think the case $k=2$ is equivalent to the following (possibly not useful) "zig-zag ladder" characterisation: can the graph be formed by taking a graph with a bipartite planar embedding (ie. the graph can be drawn in the plane as two columns of vertices, such that all edges are between "left" vertices and "right" vertices), then connecting all "left" vertices with a path from top to bottom, and all "right" vertices with a path from top to bottom. I haven't worked out if recognising graphs of this form is hard, but I suspect it is in P.

Comment by Ashley Montanaro

2010-08-25T21:09:26Z

Thanks very much - that's very helpful.

Comment by Ashley Montanaro

2010-08-25T13:23:00Z

Thanks for the link; some of those references were useful. In particular, the term "semi-regular bipartite graph" seems to be yet another way of describing these matrices.

Comment by Ashley Montanaro

2010-08-25T12:59:29Z

Thanks; this connection to other types of object is indeed the sort of thing I was looking for.

Comment by Ashley Montanaro

2010-08-25T12:56:29Z

Thanks, this is a nice alternative way to look at these matrices.