User ashley montanaro - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T11:13:44Z http://mathoverflow.net/feeds/user/7767 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108824/a-graph-parameter-possibly-related-to-treewidth A graph parameter possibly related to treewidth Ashley Montanaro 2012-10-04T14:44:14Z 2012-10-05T23:45:04Z <p>(<a href="http://cstheory.stackexchange.com/questions/12744/a-graph-parameter-possibly-related-to-treewidth" rel="nofollow">Cross-posted</a> from the Theoretical Computer Science StackExchange site after there was no conclusive answer after a week.)</p> <p>I am interested in graphs on $n$ vertices which can be produced via the following process.</p> <ol> <li>Start with an arbitrary graph $G$ on $k\le n$ vertices. Label all the vertices in $G$ as <i>unused</i>.</li> <li>Produce a new graph $G'$ by adding a new vertex $v$, which is connected to one or more <i>unused</i> vertices in $G$, and is not connected to any <i>used</i> vertices in $G$. Label $v$ as <i>unused</i>.</li> <li>Label one of the vertices in $G'$ to which $v$ is connected as <i>used</i>.</li> <li>Set $G$ to $G'$ and repeat from step 2 until $G$ contains $n$ vertices.</li> </ol> <p>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.</p> <p>I would like to know if this process has been studied before. In particular, for arbitrary $k$, <b>is it NP-complete to determine whether a graph has complexity $k$?</b></p> <p>This problem appears somewhat similar to the question of whether $G$ is a <a href="http://cstheory.stackexchange.com/questions/1532/what-is-the-correct-definition-of-k-tree" rel="nofollow">partial $k$-tree</a>, i.e. has <a href="http://en.wikipedia.org/wiki/Treewidth" rel="nofollow">treewidth</a> $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.</p> http://mathoverflow.net/questions/59463/unbalancing-lights-in-higher-dimensions Unbalancing lights in higher dimensions Ashley Montanaro 2011-03-24T19:26:31Z 2012-09-01T22:30:42Z <p>In ''<a href="http://books.google.com/books?id=V8YgNioxF6AC&amp;printsec=frontcover&amp;dq=probabilistic+method&amp;hl=en&amp;src=bmrr&amp;ei=55eLTZ6YNM-WhQeE94yyDg&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CDAQ6AEwAA#v=onepage&amp;q&amp;f=false" rel="nofollow">The Probabilistic Method</a>'' by Alon and Spencer, the following <b>unbalancing lights</b> problem is discussed. Given an $n \times n$ matrix $A = (a_{ij})$, where $a_{ij} = \pm 1$, we want to maximise the quantity</p> <p>$x^T A y = \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i y_j$</p> <p>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.</p> <p>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 <code>$0&lt;C&lt;1$</code>. On the other hand, there is an explicit family of matrices $A$ such that $m(A) = n^{3/2}$.</p> <p>It is natural to generalise this problem to $n \times n \times \dots \times n$ arrays $A$ containing $\pm 1$ entries, writing</p> <p>$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}$</p> <p>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}$.</p> <p><b>My question is:</b> 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?</p> <p><b>Background</b></p> <p>Finding a lower bound on $m(A)$ in the more general case where $A$ is an arbitrary bilinear form was considered by <a href="http://qjmath.oxfordjournals.org/content/os-1/1/164.extract" rel="nofollow">Littlewood</a> 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 <a href="http://www.jstor.org/pss/1968255" rel="nofollow">Bohnenblust and Hille</a>. 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 <a href="http://books.google.com/books?id=QC_KALDZw5wC&amp;printsec=frontcover&amp;dq=analysis+blei&amp;hl=en&amp;ei=vJOLTZzXJMLAhAeyqZ2nDg&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CCgQ6AEwAA#v=onepage&amp;q&amp;f=false" rel="nofollow">Analysis in Integer and Fractional Dimensions</a> by Ron C. Blei. However, I could not find any information about whether the bounds can be improved.</p> http://mathoverflow.net/questions/59463/unbalancing-lights-in-higher-dimensions/106141#106141 Answer by Ashley Montanaro for Unbalancing lights in higher dimensions Ashley Montanaro 2012-09-01T22:30:42Z 2012-09-01T22:30:42Z <p>Belatedly answering my own question: Pellegrino and Seoane-Sepulveda have <a href="http://arxiv.org/pdf/1010.0461.pdf" rel="nofollow">shown</a> 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.</p> http://mathoverflow.net/questions/68367/are-almost-commuting-hermitian-matrices-close-to-commuting-matrices-in-the-2-nor/68379#68379 Answer by Ashley Montanaro for Are almost commuting hermitian matrices close to commuting matrices (in the 2-norm)? Ashley Montanaro 2011-06-21T13:45:48Z 2011-06-21T13:45:48Z <p>There is a <a href="http://arxiv.org/abs/1002.3082" rel="nofollow">recent paper</a> 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).</p> http://mathoverflow.net/questions/36642/binary-matrices-with-constant-row-and-column-sums Binary matrices with constant row and column sums Ashley Montanaro 2010-08-25T08:12:28Z 2010-12-24T09:07:02Z <p>My question is about $m \times n$ binary matrices (aka <code>$\{0,1\}$</code>-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).</p> <p>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.</p> <p>Second, are there any "interesting" constructions of families of such matrices, in particular that are connected to other combinatorial objects?</p> <p>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$ <a href="http://en.wikipedia.org/wiki/Hadamard_matrix#Sylvester.27s_construction" rel="nofollow">Sylvester-Hadamard</a> matrices with the first row and column removed.</p> <p>I did find a <a href="http://dx.doi.org/10.1016/0024-3795(80)90105-6" rel="nofollow">paper</a> 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.</p> http://mathoverflow.net/questions/38278/enumerative-algorithm-through-inclusion-exclusion/38458#38458 Answer by Ashley Montanaro for Enumerative algorithm through inclusion-exclusion Ashley Montanaro 2010-09-12T09:55:22Z 2010-09-12T09:55:22Z <p>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?</p> <p>Linial and Nisan have <a href="http://www.springerlink.com/content/f66m076t785578rx/" rel="nofollow">shown</a> 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 <a href="http://www.springerlink.com/content/e67392027641l025/" rel="nofollow">extended</a> 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).</p> http://mathoverflow.net/questions/33597/are-there-any-known-quantum-algorithms-that-clearly-fall-outside-a-few-narrow-cla/33639#33639 Answer by Ashley Montanaro for Are there any known quantum algorithms that clearly fall outside a few narrow classes? Ashley Montanaro 2010-07-28T10:11:59Z 2010-07-28T10:11:59Z <p>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.</p> <p>First, there's an <a href="http://arxiv.org/abs/quant-ph/0209131" rel="nofollow">algorithm</a> 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.</p> <p>Second, there are quantum algorithms for approximating the Jones polynomial and other graph invariants (see, for example, the <a href="http://arxiv.org/abs/quant-ph/0702008" rel="nofollow">paper</a> 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.</p> <p>Third, there is an <a href="http://arxiv.org/abs/0811.3171" rel="nofollow">algorithm</a> 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.</p> <p>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 <a href="http://arxiv.org/abs/quant-ph/0102078" rel="nofollow">algorithm</a> 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.</p> <p>Finally, there are algorithms for purely quantum information theoretic tasks, which are by their nature different again. In particular, the <a href="http://arxiv.org/abs/quant-ph/0601001" rel="nofollow">algorithm</a> 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).</p> http://mathoverflow.net/questions/108824/a-graph-parameter-possibly-related-to-treewidth/108879#108879 Comment by Ashley Montanaro Ashley Montanaro 2012-10-05T13:58:00Z 2012-10-05T13:58:00Z Thanks for those great pictures, which do follow the rules (unless I've made a mistake myself!). http://mathoverflow.net/questions/108824/a-graph-parameter-possibly-related-to-treewidth Comment by Ashley Montanaro Ashley Montanaro 2012-10-05T09:10:30Z 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. http://mathoverflow.net/questions/108824/a-graph-parameter-possibly-related-to-treewidth Comment by Ashley Montanaro Ashley Montanaro 2012-10-05T09:01:22Z 2012-10-05T09:01:22Z I think the case $k=2$ is equivalent to the following (possibly not useful) &quot;zig-zag ladder&quot; 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 &quot;left&quot; vertices and &quot;right&quot; vertices), then connecting all &quot;left&quot; vertices with a path from top to bottom, and all &quot;right&quot; 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. http://mathoverflow.net/questions/36642/binary-matrices-with-constant-row-and-column-sums/36668#36668 Comment by Ashley Montanaro Ashley Montanaro 2010-08-25T21:09:26Z 2010-08-25T21:09:26Z Thanks very much - that's very helpful. http://mathoverflow.net/questions/36642/binary-matrices-with-constant-row-and-column-sums/36648#36648 Comment by Ashley Montanaro Ashley Montanaro 2010-08-25T13:23:00Z 2010-08-25T13:23:00Z Thanks for the link; some of those references were useful. In particular, the term &quot;semi-regular bipartite graph&quot; seems to be yet another way of describing these matrices. http://mathoverflow.net/questions/36642/binary-matrices-with-constant-row-and-column-sums/36660#36660 Comment by Ashley Montanaro Ashley Montanaro 2010-08-25T12:59:29Z 2010-08-25T12:59:29Z Thanks; this connection to other types of object is indeed the sort of thing I was looking for. http://mathoverflow.net/questions/36642/binary-matrices-with-constant-row-and-column-sums/36646#36646 Comment by Ashley Montanaro Ashley Montanaro 2010-08-25T12:56:29Z 2010-08-25T12:56:29Z Thanks, this is a nice alternative way to look at these matrices.