most recent 30 from http://mathoverflow.net 2013-05-22T05:02:05Z http://mathoverflow.net/feeds/user/8239 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70357/lower-bounding-the-maximum-size-of-sets-in-a-set-family-with-union-promise Artem Kaznatcheev 2011-07-14T17:33:55Z 2011-07-15T18:22:55Z

<p>The following problem has come up while working on the relationship between certificate and randomized decision tree complexities of boolean functions. However, I think it is of interest by itself and some variants of it might have already been studied:</p> <p>Given $k$ finite sets $C_1, ..., C_k$, such that $|C_j| \geq c$ for every $1 \leq j \leq k$. Let $\mathcal{F}$ be a family of sets $S_1, ..., S_m \subseteq \{1,...,n\}$ with $s = \max_{1 \leq j \leq m} |S_j|$ such that for any $\epsilon m$ distinct indexes $i_1 ... i_{\epsilon m}$ there exists a $1 \leq j \leq k$ such that $C_j \subseteq S_{i_1} \cup ... \cup S_{i_{\epsilon m}}$. </p> <blockquote> <p>What is the minimal $s$ as a function of $c,k,m\;\text{and}\;n$?</p> </blockquote> <p>Some further (optional or obvious constraints)</p> <ul> <li>$c \leq n$ and in general $c$ is a function of $n$. </li> <li>$k$ can be anything and is a function of $n$ and $c$. Usually $k$ is greater than $n$ and $c$, although even the case of $k = 2$ is interesting.</li> <li>$m$ can be anything, but the more interesting case is when $m >> n$.</li> <li>$\epsilon$ can be assumed to be any constant strictly less than $1/2$. Although non-trivial results for $\epsilon = l/m$ with some constant integer $l$ are also interesting.</li> </ul> <p>If $k = 1$ then $s \geq (1 - \epsilon)|C_1|$ by a simple pigeon hole argument. I don't know any non-trivial bound for $k = 2$, but obviously we are interested in the case of $C_1 \cap C_2 = 0$.</p> <p>Alternatively, if $C_1, ..., C_k$ are all the $(\lfloor n/2 \rfloor + 1)$-element subsets then there exists an $\mathcal{F}$ such that $s = 3$. What happens if $C_1,...,C_k$ are all the $r$-element subsets?</p> <p>This seems like a relatively natural question, and I would be surprised if something similar has not been asked before. Any pointers to the literature or partial results are appreciated. If this has not been studied, then can you recommend any tools or approaches with which to answer this question?</p> <hr> <p>As per request, a more formal statement:</p> <p>Let $n,m$ be positive integers, and $0 \leq \epsilon &lt; 1/2$ -- a constant.</p> <p>Fix $C_1, ..., C_k \subseteq \{1,...,n\}$.</p> <p>Solve:</p> <p>$s = \min_{S_1, ..., S_m \subseteq \{1,...,n\}} \max_{1 \leq j \leq m} |S_j|$</p> <p>such that:</p> <p>$\forall I \subseteq \{1,...,m\} \; \exists j \in \{1,..,k\} \quad (|I| \geq \epsilon m) \Rightarrow (C_j \subseteq \bigcup_{i \in I} S_i)$</p> <hr> <p>The question also works if we replace $\max_j |S_j|$ by $\mathbb{E}_j[|S_j|]$ or by assuming that $|S_i| = |S_j|$ for any $1\leq i &lt; j \leq m$, but I am not sure how that helps.</p>

http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38259#38259 Artem Kaznatcheev 2010-09-10T01:48:59Z 2011-05-03T15:03:46Z

<p>If you are willing to sacrifice the non-trivial deterministic requirement, then I would suggest the <a href="http://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm" rel="nofollow">Deutsch-Jozsa problem</a>. To summarize: you are given a black-box $f: {0,1}^n \rightarrow {0,1}$ it is promised that either $f$ is constant or balanced (i.e. $|f^{-1}(0)| = |f^{-1}(1)|$). You have to tell me which it is. The randomized algorithm works exponentially faster than the deterministic one, and has small error.</p> <p>The best feature is that if you want to continue and mention quantum algorithms, you can do so to recover an error-less algorithm.</p>

http://mathoverflow.net/questions/55415/syntactically-capturing-complexity-classes/55421#55421 Artem Kaznatcheev 2011-02-14T16:14:07Z 2011-02-15T10:57:00Z

<p>Many of the famous complexity classes are syntactic, for example P, NP, PP, PSPACE etc. For these classes (say syntactic class $X$) there exists a Turing Machine $MC$ that accepts/constructs the machines $M$ such that the languages accepted by each $M$ are in the complexity class $X$ and for every language $L \in X$ there is some $M$ constructed by $MC$ that accepts that language. </p> <p>For example, if we want to capture PSPACE, simple enumerate all pairs of Turing Machines $M'$ and polynomials $p(n)$, to construct your machine $M$ that takes input $x$, simple calculate the size $n = |x|$ and let $m = p(n)$. Simulate $M'$ on $x$, If it uses more than $m$ space or enters the same state in the $2^m$ possible states, then reject, else output the same as $M'$ does. </p> <p>This is in contrast to semantic classes like BPP, BQP, etc, for which we do not know such a syntactic classification. The following 3 questions deal with this issue:</p> <p><a href="http://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma" rel="nofollow">http://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma</a></p> <p><a href="http://cstheory.stackexchange.com/questions/4792/benefits-for-syntactic-and-semantic-classes" rel="nofollow">http://cstheory.stackexchange.com/questions/4792/benefits-for-syntactic-and-semantic-classes</a></p> <p><a href="http://cstheory.stackexchange.com/questions/1233/semantic-vs-syntactic-complexity-classes" rel="nofollow">http://cstheory.stackexchange.com/questions/1233/semantic-vs-syntactic-complexity-classes</a></p> <p>The background section of the first question (from which I adapted an example of a syntactic class) might shed more light on your question.</p>

http://mathoverflow.net/questions/43474/symmetric-subspace-of-linear-operators Artem Kaznatcheev 2010-10-25T04:33:09Z 2010-12-16T16:59:14Z

<p>This is a question that stemmed from <a href="http://www.cs.mcgill.ca/~akazna/kaznatcheev20100509.pdf" rel="nofollow">fooling around</a> with unitary t-designs.</p> <p>Let </p> <p>\begin{equation} \mathbb{V} = \mathrm{span} \{\; U^{\otimes t}\; |\; U \in \mathrm{U}(d)\} \end{equation}</p> <p>Where $\mathrm{U}(d)$ is the unitary group acting on $\mathbb{C}^d$.</p> <p>What can we say about $\dim \mathbb{V}$? What tools can I use to figure out the dimension or good lower bounds for it?</p> <p>I've <a href="http://www.cs.uwaterloo.ca/~watrous/quant-info/lecture-notes/all-lectures.pdf" rel="nofollow">read</a> (p. 162) about the analogous question for $\mathbb{U} = \mathrm{span}\{|\psi\rangle^{\otimes t}\;|\; |\psi\rangle \in \mathbb{C}^d\}$. In particular, we can show that $\dim \;\mathbb{U} = {d + t - 1 \choose t - 1}$. To use that approach, we need to change $\mathrm{U}(d)$. </p> <p>If we change $\mathrm{U}(d)$ to $\mathbb{C}^{d\times d}$ (i.e. all the matrices on $\mathbb{C}^d$) then is it obvious that the resulting space is the same as $\mathbb{V}$? If they are the same, then the question becomes easier, since then we have the space of all linear operators that are invariant under permutations of the $t$ registers and we can just use the formulate for $\dim \mathbb{U}$ thinking of the operators as row vectors.</p> <p>(I am not sure of the tags for this, so feel free to change them)</p>

http://mathoverflow.net/questions/44519/grovers-quantum-search-algorithm/44520#44520 Artem Kaznatcheev 2010-11-02T05:36:30Z 2010-11-02T05:36:30Z

<p>When talking about the complexity of an algorithm (classical or quantum) you usually talk about complexity with regards to a specific model of computation. In the case of the circuit model of quantum computing a specific model corresponds to a universal finite set of gates (4.5 of Nielsen and Chuang has more info). Alternatively, in query models of computation, the complexity corresponds to the number of calls made to the special 'query' operator or oracle. In this case, the rotation towards $|E\rangle$ is implicit in the call to the oracle that specifies the input. Classically, you would need to make $N$ calls to such an oracle, but in the case of a quantum computer you only need on the order of $\sqrt{N}$. Thus, Grover's search provides a great example of a quantum speed-up... or more technically of the power of quantum queries over classical queries.</p>

http://mathoverflow.net/questions/12342/reductio-ad-absurdum-or-the-contrapositive/43102#43102 Artem Kaznatcheev 2010-10-21T21:58:01Z 2010-10-21T21:58:01Z

<p>It often feels like a proof by contradiction is like making your point through a witty joke and the contrapositive is sitting down and explaining why the joke is funny. </p> <p>Since the two approaches are logically equivalent, and since it is usually easy for the average journal reader to convert between the two --- the distinction for me comes down to style. Most of the arguments I have seen by contradiction are usually shorter, more intuitive, and elegant. Hence, I would usually favor proof by contradiction (it is usually the first proof I come up with...) unless the steps in the contrapositive are particularly insightful.</p>

http://mathoverflow.net/questions/38119/where-to-publish-a-paper-on-the-mafia-game/38200#38200 Artem Kaznatcheev 2010-09-09T17:06:41Z 2010-09-09T17:06:41Z

<p>If you want to reach psychologists with a mathematical background, then you should try the <a href="http://www.elsevier.com/wps/find/journaldescription.cws_home/622887/description#description" rel="nofollow">Journal of the Mathematical Psychology</a>. This is the official journal for the Society of Mathematical Psychology. It publishes theoretical work with a decent amount of math usually of the probability/statistics variety. However, you will have to be careful with language (i.e. avoid physics jargon and more sophisticated math jargon) to better appeal to the audience.</p>

http://mathoverflow.net/questions/35989/applications-of-banach-tarski-paradox-to-probability-theory/35994#35994 Artem Kaznatcheev 2010-08-18T17:42:15Z 2010-08-18T17:42:15Z

<p>I thought the whole point of having a $\sigma$-algebra for your probability space was to avoid non-measurable sets like the ones used in the proof of BT. Hence, it would seem that the BT paradox would be impossible to state in probability theory on account of the sets you need not being present in your algebra... but I might be mistaken, can someone else comment more?</p>

http://mathoverflow.net/questions/35742/picking-collections-to-get-over-half-the-number-of-each-type-of-object/35849#35849 Artem Kaznatcheev 2010-08-17T07:15:12Z 2010-08-17T07:15:12Z

<p>I think Gerry's answer is correct. </p> <p>If there are any empty boxes, they can be ignored. Say we have $k$ types of items with $n_1, ..., n_k$ items of each time. Suppose we need less than $M$ boxes for this distribution. Consider adding $n_{k+1}$ items of a new type $k + 1$. At worst, these items can be placed in new boxes, with one item per box. In that case, we will need $\lceil \frac{n_{k + 1}}{2} \rceil$ new boxes. Thus, by induction the most boxes we will need, assuming each box contains one item is:</p> <p>$$\lceil \frac{n_1}{2} \rceil + ... + \lceil \frac{n_{k+1}}{2} \rceil \leq \frac{n_1 + ... + n_{k + 1}}{2} + \frac{k}{2} \leq \frac{n + k}{2}$$</p> <p>If more than one item is placed per box, then the number of boxes we need will not increase. Hence the upper bound is solid and by Gerry's argument tight.</p>

http://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma/35284#35284 Artem Kaznatcheev 2010-08-11T22:21:39Z 2010-08-11T22:21:39Z

<p>This is more a comment than an answer (since I can't leave comments, yet):</p> <p>I've looked into this question briefly this past winter. As far as I know there is no syntactic definitions of BPP, BQP, or QMA. If you introduce post selection to BQP then you have a syntactic definition, but that is only because PostBQP = PP and PP is syntactic.</p> <p>@Henry Yuen I also don't understand why a syntactic definition of anything would imply derandomization... of course if BPP was also FOL + LFP then we would have derandomization but if BPP was FOL + other gadget then we would not know that without proving that LFP and the other gadget do the same things.</p>

http://mathoverflow.net/questions/35151/what-impact-would-pnp-have-on-the-characterization-of-bqp/35189#35189 Artem Kaznatcheev 2010-08-11T03:25:55Z 2010-08-11T03:25:55Z

<p>To your second question. It is unlikely that the current under-review proof of P != NP will allow you to seperate BQP and QMA (or BQP and P, or BQP and NP, or even BPP and NP...). Deolalikar's proof uses descriptive complexity, in particular it uses a correspondence between statements expressible in certain logics and the complexity classes P and NP. As far as I know there is no such nice one-to-one correspondences between BPP, BQP, or QMA and nice logics.</p>

http://mathoverflow.net/questions/32409/examples-of-folk-theorems/34906#34906 Artem Kaznatcheev 2010-08-08T08:51:58Z 2010-08-08T08:51:58Z

<p>Another nice type of 'folk theorems' I have seen is of a sort where some relatively straight forward generalization of a well established theorem is assumed and then used for its heuristic or explanatory value. I find this is often used in fields where mathematicians interact with non-mathematicians and although it is completely non-rigorous (and sometimes even misleading!) most often it helps in exposition and for building intuition.</p> <p>An example would be the "folk theorem of evolutionary game theory" (as used by Hofbauer and Sigmund, BAMS 2003) on certain kinds of correspondences of Nash equilibrium and dynamic approaches.</p>

http://mathoverflow.net/questions/73526/how-to-use-arxiv Artem Kaznatcheev 2011-08-25T07:27:20Z 2011-08-25T07:27:20Z

there is some good advice here: <a href="http://cstheory.stackexchange.com/q/7574/1037" rel="nofollow">cstheory.stackexchange.com/q/7574/1037</a>

http://mathoverflow.net/questions/73526/how-to-use-arxiv/73632#73632 Artem Kaznatcheev 2011-08-25T07:25:47Z 2011-08-25T07:25:47Z

I asked a similar question on putting up things that don't go to journal of the theoretical CompSci version of MO: <a href="http://cstheory.stackexchange.com/q/7574/1037" rel="nofollow">cstheory.stackexchange.com/q/7574/1037</a> and the consensus seemed to be that its fine as long as its not something you plan to extend and make into a future article (to avoid redundancy and confusion).

http://mathoverflow.net/questions/70357/lower-bounding-the-maximum-size-of-sets-in-a-set-family-with-union-promise Artem Kaznatcheev 2011-07-15T05:45:14Z 2011-07-15T05:45:14Z

Added a more formal statement, hopefully it is clear. Paseman's more informal restatement also works.

http://mathoverflow.net/questions/3044/tools-for-collaborative-paper-writing/53837#53837 Artem Kaznatcheev 2011-01-31T00:00:14Z 2011-01-31T00:00:14Z

whoops, there is a already a post like this. Will delete.

http://mathoverflow.net/questions/43474/symmetric-subspace-of-linear-operators/49650#49650 Artem Kaznatcheev 2010-12-17T10:21:54Z 2010-12-17T10:21:54Z

thank you for this proof! I think I understand the basic idea, but I will have to look at the argument more closely to really understand it, since it uses some technology that I am not familiar with. I will accept this answer since it was the first one to answer the question I had.

http://mathoverflow.net/questions/48181/formal-languages-what-does-r-trivial-mean Artem Kaznatcheev 2010-12-03T16:11:06Z 2010-12-03T16:11:06Z

duplicate: <a href="http://cstheory.stackexchange.com/questions/3503/formal-languages-what-does-r-trivial-mean" rel="nofollow" title="formal languages what does r trivial mean">cstheory.stackexchange.com/questions/3503/&hellip;</a> and <a href="http://math.stackexchange.com/questions/12921/formal-languages-what-does-r-trivial-mean" rel="nofollow" title="formal languages what does r trivial mean">math.stackexchange.com/questions/12921/&hellip;</a>

http://mathoverflow.net/questions/44519/grovers-quantum-search-algorithm/44520#44520 Artem Kaznatcheev 2010-11-02T18:07:53Z 2010-11-02T18:07:53Z

The U depends on the oracle... i.e. it depends on which item(s) are marked. Thus it does differ over various instances of Grover's algorithm....

http://mathoverflow.net/questions/44244/what-recent-discoveries-have-amateur-mathematicians-made/44437#44437 Artem Kaznatcheev 2010-11-02T00:27:00Z 2010-11-02T00:27:00Z

a link: <a href="http://en.wikipedia.org/wiki/Scott_Draves" rel="nofollow">en.wikipedia.org/wiki/Scott_Draves</a>

http://mathoverflow.net/questions/1243/how-to-write-math-well/1257#1257 Artem Kaznatcheev 2010-10-28T03:51:18Z 2010-10-28T03:51:18Z

reading a text out loud is some of the best advice for improving writing. Marginally related: <a href="http://xkcd.com/481/" rel="nofollow">xkcd.com/481</a>

http://mathoverflow.net/questions/43474/symmetric-subspace-of-linear-operators/43495#43495 Artem Kaznatcheev 2010-10-25T22:25:36Z 2010-10-25T22:25:36Z

I agree that any matrix can be written as a linear combination of unitaries (in fact as each matrix can be written as a linear combination of just two unitaries). This definitely solves the question for the case of $t = 1$, but that is not really the difficult case. Just because the unitaries span $\mathbb{C}^{d \times d}$ does not mean we can replace $U \in mathrm{U}(d)$ by $U \in \mathbb{C}^{d \times d}$ on the condition side of the definition of our spanning set --- at least not without proof because it is not obvious that the tensor will behave nicely.

http://mathoverflow.net/questions/43474/symmetric-subspace-of-linear-operators Artem Kaznatcheev 2010-10-25T06:30:07Z 2010-10-25T06:30:07Z

@Mariano I am not sure if I understand your question exactly. The field I have in mind is $\mathbb{C}$ and $\mathbb{V}$ is a subspace of $(C^{d \times d})^{\otimes t}$. So the span is taken there.

http://mathoverflow.net/questions/1785/how-do-you-keep-your-research-notes-organized/1795#1795 Artem Kaznatcheev 2010-09-01T04:37:42Z 2010-09-01T04:37:42Z

I think TiddlyWiki is relatively popular for this: <a href="http://www.tiddlywiki.com/" rel="nofollow">tiddlywiki.com</a> an example of how TiddlyWiki looks with physics/math on it is Lisi's notebook: <a href="http://deferentialgeometry.org/" rel="nofollow">deferentialgeometry.org</a> One of the advantages of tiddly is that it is just one file and hence easy to move around.

http://mathoverflow.net/questions/12638/taking-lecture-notes-in-lectures/12671#12671 Artem Kaznatcheev 2010-09-01T02:17:09Z 2010-09-01T02:17:09Z

I think it is a great idea to retype the notes after the course or lecture is over in order to review the material and sometimes ask further questions. I usually take quick notes by hand (I like having margins to try out my own ideas, tangents, etc) and then if I am really excited about the course I take the time to covert the notes to TeX which really helps reinforce and further explore the ideas.

http://mathoverflow.net/questions/37276/fairest-way-to-choose-gifts Artem Kaznatcheev 2010-09-01T02:13:30Z 2010-09-01T02:13:30Z

since coins are allowed couldn't we just pick a number uniformly at random from $0...2^{2n} - 1$ and then use it's binary representation as the sequence of choices with 0 = Alice and 1 = Bobby? or are we restricted in the number of coin flips we are allowed to make?

http://mathoverflow.net/questions/33796/existence-of-a-pseudo-polynomial-time-algorithm-for-a-counting-problem Artem Kaznatcheev 2010-08-27T13:00:54Z 2010-08-27T13:00:54Z

Should the RHS read $d_{\pi(k)}$ instead of $d_{\pi(i)}$? I also agree with Daniel, it seems inappropriate to ask an open question (especially such a recent one) on MO.