User john watrous - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T15:32:53Z http://mathoverflow.net/feeds/user/7641 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32986/how-fast-are-a-ruler-and-compass How fast are a ruler and compass? John Watrous 2010-07-22T18:06:18Z 2013-04-25T20:41:12Z <p>This may be more of a recreational mathematics question than a research question, but I have wondered about it for a while. I hope it is not inappropriate for MO.</p> <p>Consider the standard assumptions for ruler and compass constructions: We have an infinitely large sheet of paper, which we associate with the complex plane, that is initially blank aside from the points 0 and 1 being marked. In addition we have an infinite ruler and a compass that can be stretched to an arbitrary length.</p> <p>Let us define a <em>move</em> to be one of the two actions normally associated with a ruler and compass:</p> <ol> <li>Use the ruler to draw the line defined by any two distinct points already marked on the paper.</li> <li>Stretch the compass from any one marked point to another and draw the resulting circle.</li> </ol> <p>Assume that all intersection points among lines and circles drawn by these operations are automatically marked on the paper. </p> <p>Now define $D(n)$ to be the maximum distance between any two marked points that can be constructed in this way with $n$ moves.</p> <p>Questions:</p> <ol> <li>Is anyone aware of results about the function $D(n)$ or something equivalent?</li> <li>It is not difficult to prove $D(n) > 2^{2^{cn}}$ for some positive constant $c$ for sufficiently large $n$. Can one do better? If so, can one prove an upper bound on $D(n)$?</li> </ol> http://mathoverflow.net/questions/36903/where-does-the-game-theoretic-characterization-of-ph-come-from/36911#36911 Answer by John Watrous for Where does the game-theoretic characterization of PH come from? John Watrous 2010-08-27T18:06:44Z 2010-08-27T18:06:44Z <p>The answer to part (a) of your question is this reference:</p> <blockquote> <p>A. Meyer and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In <em>Proceedings of the 13th IEEE Symposium on Switching and Automata Theory</em>, pages 125-129, 1972. <a href="http://people.csail.mit.edu/meyer/rsq.pdf" rel="nofollow">[pdf]</a></p> </blockquote> <p>What an amazing paper this was! Two later papers that discuss refinements of the result include these:</p> <blockquote> <p>C. Wrathall. Complete sets and the polynomial-time hierarchy. <em>Theoretical Computer Science</em> 3:23-33, 1977.</p> <p>A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. <em>Journal of the ACM</em> 28(1):114-133, 1981.</p> </blockquote> http://mathoverflow.net/questions/15204/space-bounded-communication-complexity-of-identity/33912#33912 Answer by John Watrous for Space Bounded Communication Complexity of Identity John Watrous 2010-07-30T14:01:59Z 2010-07-30T14:01:59Z <p>Here's an argument that I believe shows that $\log n - \omega(1)$ is impossible. (This argument came out of a discussion I had with Steve Fenner.)</p> <p>Let Alice's input be <code>$x\in\{0,1\}^n$</code> and let Bob's input be <code>$y\in\{0,1\}^n$</code>. Assume the shared memory stores states in <code>$\{0,1\}^m$</code>, and its initial state is $0^m$. We are interested in lower-bounding $m$ for any protocol that computes EQ$(x,y)$.</p> <p>A given protocol is defined by two collections of functions <code>$\{f_x\}$</code> and <code>$\{g_y\}$</code>, representing the functions applied to the shared memory by Alice on each input $x$ and Bob on each input $y$, respectively, along with some answering criterion. To be more specific, let us assume that if the shared memory ever contains the string $1^{m-1}b$ then the output of the protocol is $b$ (for each <code>$b\in\{0,1\}$</code>). For convenience, let us also assume that $f_x(1^{m-1}b) = 1^{m-1}b\:$ and <code>$g_y(1^{m-1}b) = 1^{m-1}b\:$</code> for every <code>$x,y\in\{0,1\}^n$</code> and <code>$b\in\{0,1\}$</code>. In other words, Alice and Bob don't change the shared memory once they know the answer.</p> <p>Now, for each <code>$x,y\in\{0,1\}^n$</code>, consider what happens when Alice and Bob run the protocol on the input $(x,y)$. Define <code>$A_{x,y}\subseteq\{0,1\}^m$</code> to be the set of all states of the shared memory that Alice receives at any point in the protocol, and likewise define <code>$B_{x,y}\subseteq\{0,1\}^m$</code> to be the states of the shared memory that Bob receives. Also define <code>$S_{x,y} = \{0w\,:\,w\in A_{x,y}\} \cup \{1w\,:\,w\in B_{x,y}\}.$</code> We will assume Alice goes first, so <code>$0^m \in A_{x,y}$</code> for all $x,y$. Let us also make the following observations:</p> <ol> <li><p>By the definition of $A_{x,y}$ and $B_{x,y}$, it holds that $f_x(A_{x,y}) \subseteq B_{x,y}$ and $g_y(B_{x,y}) \subseteq A_{x,y}$ for all $x,y$.</p></li> <li><p>For every $x,y$ with $x\not=y$ it holds that $1^{m-1}0\in A_{x,y} \cup B_{x,y}$, because Alice and Bob output 0 when their strings disagree.</p></li> <li><p>For every $x$ it holds that $1^{m-1}0\not\in A_{x,x} \cup B_{x,x}$, because Alice and Bob do not output 0 when their strings agree.</p></li> </ol> <p>Now let us prove that $S_{x,x}\not=S_{y,y}$ whenever $x\not=y$. To do this, let us assume toward contradiction that $x\not=y$ but $S_{x,x} = S_{y,y}$ (i.e., $A_{x,x} = A_{y,y}$ and $B_{x,x} = B_{y,y}$), and consider the behavior of the protocol on the input $(x,y)$.</p> <p>Let $w_t$ be the contents of the shared memory after $t$ turns have passed in the protocol, so we have $w_0 = 0^m$, $w_1 = f_x(w_0)$, $w_2 = g_y(w_1)$, and so on. It holds that <code>$\begin{array}{c} w_0 = 0^m \in A_{x,x}\\ w_1 = f_x(w_0) \in f_x(A_{x,x}) \subseteq B_{x,x} = B_{y,y},\\ w_2 = g_y(w_1) \in g_y(B_{y,y}) \subseteq A_{y,y} = A_{x,x}, \end{array}$</code> and in general <code>$\begin{array}{c} w_{2t + 1} = f_x(w_{2t}) \in f_x(A_{x,x}) \subseteq B_{x,x} = B_{y,y}\\ w_{2t+2} = g_y(w_{2t+1}) \in g_y(B_{y,y}) \subseteq A_{y,y} = A_{x,x} \end{array}$</code> for each $t\in\mathbb{N}$. It follows that $A_{x,y} \subseteq A_{x,x}$ and $B_{x,y} \subseteq B_{y,y}$.</p> <p>But now we have our contradiction, assuming the protocol is correct: given that $A_{x,y}\subseteq A_{x,x}$ and $B_{x,y} \subseteq B_{y,y}$, it follows that $1^{m-1}0 \in A_{x,x}\cup B_{y,y}$, so Alice and Bob output the incorrect answer 0 on either $(x,x)$ or $(y,y)$.</p> <p>Each $S_{x,x}$ is a subset of <code>$\{0,1\}^{m+1}$</code>, so there are at most $2^{2^{m+1}}$ choices for $S_{x,x}$. Given that the sets $S_{x,x}$ must be distinct for distinct choices of $x$, it follows that <code>$2^{2^{m+1}} \geq 2^n$</code>, so $m \geq \log n - 1$.</p> http://mathoverflow.net/questions/25843/minimize-the-k-th-largest-element-under-linear-constraints/32085#32085 Answer by John Watrous for Minimize The k-th Largest Element under Linear Constraints John Watrous 2010-07-15T23:16:36Z 2010-07-15T23:16:36Z <p>The problem is NP-hard, unless there is more to it than what is stated, and one cannot hope for an efficient approximation to any reasonable degree unless P = NP.</p> <p>One way to show this is by a reduction from vertex cover, which may be established as follows. For any undirected graph $G = (V,E)$, let $M\in\mathbb{R}^{E\times V}$ be the incidence matrix of $G$, and let $K$ be the cone of vectors $x\in\mathbb{R}^V$ such that $Mx \geq 0$ (or $-Mx \leq 0$, as the question statement would prefer). If $G$ has a vertex cover of size $k$, then $\inf_{x\in K} F_{k+1}(x) = -\infty$. If not, $\inf_{x\in K} F_{k+1}(x) = 0$. Without further assumptions, this would seem to rule out the existence of an efficient approximation algorithm of any sort.</p> <p>The same general idea, with simple modifications, will establish a reduction if $x$ is constrained to the nonnegative orthant.</p> <p>It should also be noted that the problem does <em>not</em> become easier under the assumption $x\in\mathbb{Z}^n$, counter to what the question suggests.</p> http://mathoverflow.net/questions/33597/are-there-any-known-quantum-algorithms-that-clearly-fall-outside-a-few-narrow-cla Comment by John Watrous John Watrous 2010-07-28T11:08:27Z 2010-07-28T11:08:27Z Stephen Jordan's Quantum Algorithm Zoo (<a href="http://www.its.caltech.edu/~sjordan/zoo.html" rel="nofollow">its.caltech.edu/~sjordan/zoo.html</a>) lists many known quantum algorithms. It might be helpful for identifying gaps in your classification scheme. http://mathoverflow.net/questions/32986/how-fast-are-a-ruler-and-compass/33013#33013 Comment by John Watrous John Watrous 2010-07-23T01:09:00Z 2010-07-23T01:09:00Z Thanks, Igor, that reference is a good lead. It doesn't necessarily answer the question because the maximum distance between marked points will not generally be an integer, but it is a start. About the title of the question, by &quot;fast&quot; I am referring to how fast constructed points can move away from one another as a function of the number of moves. My apologies if that caused confusion.