most recent 30 from http://mathoverflow.net 2013-05-21T11:17:39Z http://mathoverflow.net/feeds/user/2641 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17464/making-a-non-monotone-function-monotone/123437#123437 Grigory Yaroslavtsev 2013-03-02T18:33:29Z 2013-03-02T18:33:29Z

<p>A combinatorial proof was found last year by Chakrabarty and Seshadhri: <a href="http://eccc.hpi-web.de/report/2012/030/download" rel="nofollow">http://eccc.hpi-web.de/report/2012/030/download</a>. In Theorem 3 they show that indeed $E(f) = \Omega(M(f))$.</p>

http://mathoverflow.net/questions/17464/making-a-non-monotone-function-monotone Grigory Yaroslavtsev 2010-03-08T12:03:21Z 2013-03-02T18:33:29Z

<p>Consider a function <code>$f: \{0,1\}^n \rightarrow \{1..R\}$</code>. This function can be interpreted as a coloring $Color(v)$ of vertices in a unit n-dimensional hypercube in $R$ colors. </p> <p>We say there is a directed edge $(v1, v2)$ in the hypercube if $v1$ and $v2$ differ in only one coordinate in n-dimensional space and this coordinate is equal to $0$ for $v1$ and to $1$ for $v2$.</p> <p>Let's define $E(f)$ to be the number of non-monotone directed edges in this hypercube, i.e. edges $(v1, v2)$, such that $Color(v1) > Color(v2)$. Having a non-monotone function $f$ we want to make it monotone, changing its values in as few points of domain as possible. Let's denote $M(f)$ to be the minimal number of points where we need to change the values to make the function monotone.</p> <p>There is a hypothesis that $M(f) \le E(f)$ that I'm trying to prove.</p> <p>Known results:</p> <p>0) There exist such $f$ that $M(f) \ge E(f)$ (if $E(f)$ is not too large, say $E(f) \le 2^{n-1}$). This one is an easy exercise.</p> <p>1) For $R=2$ the hypothesis is true. The method I know is rather difficult to describe briefly. <strike>If necessary, I can give a link</strike> (see EDIT).</p> <p>2) For general $R$ it can be proved that $M(f) \le E(f) \log{R}$. The proof involves construction for $R=2$ and some range reduction technique.</p> <p>I am interested in what techniques can be applied to prove or disprove this hypothesis. Any result better than $M(f) \le E(f) \log{R}$ (like $M(f) = O(E(f))$) will be interesting.</p> <p>EDIT: Here is a <a href="http://www.cse.psu.edu/~sofya/masters.ps" rel="nofollow">link</a> to M.Sc. thesis by Sofya Raskhodnikova, where results 1) and 2) can be found in Chapters 3 and 5 respectively.</p> <p>EDIT: Here is a <a href="http://yaroslavtsev.wordpress.com/2010/03/10/monotonicity-testing/" rel="nofollow">link</a> to some informal description of motivation for this problem.</p>

http://mathoverflow.net/questions/119445/approximation-theory-under-l-1-error Grigory Yaroslavtsev 2013-01-21T06:04:49Z 2013-01-23T21:33:45Z

<p>Is there a reference for results in approximation theory of bounded functions of one (and multiple) variables under $L_1$-error?</p> <p>Formal definitions for functions of one variable are below.</p> <p>Let $C$ be a class of functions $f \colon [0,1] \rightarrow [0,1]$. For $n > 0$ and $f \in C$ let $A_n$ be a class of all deterministic (or randomized) rules $r_n$ which map $n$ values of $f$ (possibly chosen adaptively, i.e. $f(x_1), f(x_2(f(x_1))), \dots, f(x_n(f(x_{n - 1}(\dots f(x_1))))$) to a function $r_n(f) \colon [0,1] \rightarrow [0,1]$. For $p \ge 1$ let $\epsilon_p(n)$ be the best worst-case $L_p$-error of a rule $r_n \in A_n$ taken over all functions $f \in C$, i.e. $\epsilon_p(n) = \min_{r_n \in A_n} \sup_{f \in C} ||f - r_n(f)||_p$.</p> <p>Under which conditions on $C$ non-trivial bounds on $\epsilon_1(n)$ exist? Same question for functions of multiple variables. E.g., one can derive such bounds for functions with bounded $n$-th derivative as discussed below from bounds on $\epsilon_\infty(n)$. How to find literature specifically on bounds on $\epsilon_{1}(n)$, if it exists?</p> <p>For $L_\infty$-error $\epsilon_{\infty}(n)$ non-trivial such bounds can be achieved for the class of functions with bounded $n$-th derivative by using Chebyshev polynomials.</p> <p>P.S. Similar results in theoretical computer science are known as ``learning of $C$ under $L_1$-error'', but the focus there is mostly on discrete domains.</p>

http://mathoverflow.net/questions/80508/volume-change-under-linear-transformation Grigory Yaroslavtsev 2011-11-09T19:17:05Z 2011-11-09T22:40:36Z

<p>It is well-known, that given a linear transformation $f \colon \mathbb R^n \rightarrow \mathbb R^m$, where $m \ge n$, the $m$-dimensional volume of an image of any measurable subset $S \subseteq \mathbb R^n$ under the transformation can be expressed as: $$Volume(f(S)) = \sqrt{\det(A^TA)} Volume(S),$$ where $A \in \mathbb R^{m \times n}$ is a matrix of the linear transform.</p> <p>If $m &lt; n$, then this relation no longer holds (the mapping is not invertible and $\det(A^TA) = 0$). Is there any characterization of a volume change under linear transformation in this case? I am specifically interested in the case, when $S$ is a unit $L_1$-ball in $\mathbb R^n$.</p>

http://mathoverflow.net/questions/25055/time-complexity-of-finding-the-gcd-of-a-set-s-as-a-function-of-sums/25068#25068 Grigory Yaroslavtsev 2010-05-17T22:32:54Z 2010-05-18T15:05:57Z

<p>Finding greatest common divisor ($gcd$) of two numbers of length $k$ takes $O(k)$ time. Suppose that all the numbers have equal length $k$, then complexity will be $O(nk)$, which is $O(n \log(\frac{S}{n}))$. This is in fact the case of maximum complexity for a fixed $n$ and $S$. Because in general case the time complexity be something like $O(\sum_i \log x_i)$ and from convexity of the $\log$ function it follows that maximum is achieved when all $\log x_i$ are equal.</p>

http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24422#24422 Grigory Yaroslavtsev 2010-05-12T18:37:49Z 2010-05-13T15:12:33Z

<p>What you are asking about is known as the universality problem. In the slides by Jeffrey Shallit (http://www.cs.uwaterloo.ca/~shallit/Talks/open10r.pdf, slide 36) it is mentioned that this problem is PSPACE-complete for NFA. So it is highly unlikely that a polynomial algorithm exists for it. <strike>Please, let me know if you need an exact reference to the proof of the PSPACE-completeness</strike> (see edit2).</p> <p>edit. I forgot to mention that because the universality problem for DFA is simply solved in polynomial time the existence of a poly(n, d) algorithm in your second question also implies PSPACE=P and is very unlikely.</p> <p>edit2. The proof of PSPACE-completeness can be found in the lecture notes here: <a href="http://www.wisdom.weizmann.ac.il/~vardi/av/notes/" rel="nofollow">http://www.wisdom.weizmann.ac.il/~vardi/av/notes/</a> (the proof itself is in lecture 4).</p>

http://mathoverflow.net/questions/21641/maximum-number-of-perfect-matchings-in-a-graph Grigory Yaroslavtsev 2010-04-17T02:40:45Z 2010-04-17T06:43:04Z

<p>What is the maximal number of perfect matchings a graph $G(V,E)$ can have if $|V|$ and $|E|$ are fixed? I am particularly interested in a case when $|E| = c|V|^2$. </p>

http://mathoverflow.net/questions/16913/prove-a-function-is-primitive-recursive/16932#16932 Grigory Yaroslavtsev 2010-03-02T22:41:55Z 2010-03-02T22:58:22Z

<p>There is a theorem that says that any function computable on a Turing machine in time that is a primitive recursive function of the length of the input is primitively recursive.</p> <p>This theorem you can find here: <a href="http://en.wikipedia.org/wiki/Primitive_recursive_function" rel="nofollow">http://en.wikipedia.org/wiki/Primitive_recursive_function</a></p> <p>Your function is primitively recursive because it can be computed in $O(n^2)$ time (here $n$ is the length of the input) on a computer using some programming language like C++. The difference between the time needed to implement this algorithm in C++ and on a Turing machine is polynomial in the length of the input so the resulting time needed for implementation on a Turing machine is polynomial in $n$.</p> <p>[edit] Proving that function is not primitive recursive is harder. There is a proof with diagonalization method that shows that there exists some not primitively recursive function. To construct some explicit function it can be noted that if function grows too fast than it is not primitively recursive. Ackerman's function has the right growth rate for this. </p>

http://mathoverflow.net/questions/16762/inverse-for-a-permutation-over-gf2 Grigory Yaroslavtsev 2010-03-01T16:52:12Z 2010-03-02T15:18:46Z

<p>Given a permutation <code>$f: \{0,1\}^n \rightarrow \{0,1\}^n$</code> as $n$ polynomials over $GF(2)$ how to get formulas for the inverse permutation $f^{-1}$?</p> <p>I am interested in the answer to the previous question, although I would really like to know an answer to a more specific question. Let's consider a restricted permutation <code>$g: \{0,1\}^{n-1} \rightarrow \{0,1\}^{n-1}$</code> that is obtained from $f(x_1, \ldots, x_n)$ if we fix any of its arguments to some constant (for example, $x_1 = 0$). How does $deg(g^{-1})$ depend on $deg(f^{-1})$ (here $deg(f)$ is a maximum over degrees of polynomials, corresponding to $f$)? My hypothesis is that $deg(g^{-1}) \ge deg(f^{-1}) - 1$ for at least one of the two values we can assign to $x_1$.</p>

http://mathoverflow.net/questions/119445/approximation-theory-under-l-1-error/119487#119487 Grigory Yaroslavtsev 2013-01-21T19:19:26Z 2013-01-21T19:19:26Z

Thank you, did you have a chance to look at these sources? Unfortunately, I can't find any preview online and my university library doesn't have them as well.

http://mathoverflow.net/questions/80508/volume-change-under-linear-transformation/80530#80530 Grigory Yaroslavtsev 2011-11-09T23:49:26Z 2011-11-09T23:49:26Z

Thank you, Sergei! There is a specific reason, why the $L_1$-balls are important, rather than $L_\infty$-balls. However, because I am ultimately interested in some specific class of linear mappings, the combinatorial type is fixed and one can get a closed formula.

http://mathoverflow.net/questions/80508/volume-change-under-linear-transformation/80511#80511 Grigory Yaroslavtsev 2011-11-09T21:33:32Z 2011-11-09T21:33:32Z

Thank you, but I am not sure I understand how can this be used to compute the $\mathcal{L}^m(f(S))$, which I am interested in. Also, shouldn't the formula have $\mathcal{H}^{n - m}$, rather than $\mathcal{H}^{m - n}$ on the left-hand side?

http://mathoverflow.net/questions/32894/cycles-of-length-1mod-3-in-regular-graphs Grigory Yaroslavtsev 2010-07-22T13:39:52Z 2010-07-22T13:39:52Z

Do you mean simple cycle?

http://mathoverflow.net/questions/25399/is-every-input-gate-of-a-boolean-circuit-to-decide-a-language-on-a-path-to-the/25412#25412 Grigory Yaroslavtsev 2010-05-21T05:59:21Z 2010-05-21T05:59:21Z

@Niall: Thank you

http://mathoverflow.net/questions/25399/is-every-input-gate-of-a-boolean-circuit-to-decide-a-language-on-a-path-to-the/25412#25412 Grigory Yaroslavtsev 2010-05-20T21:29:00Z 2010-05-20T21:29:00Z

Boolean circuit is an acyclic graph, are you sure that accessibility problem for acyclic graphs is still $NLOGSPACE$-complete?

http://mathoverflow.net/questions/25055/time-complexity-of-finding-the-gcd-of-a-set-s-as-a-function-of-sums Grigory Yaroslavtsev 2010-05-17T23:55:40Z 2010-05-17T23:55:40Z

You can modify it like this: keep the set of numbers $S$ and then $n - 1$ times extract two minimal elements from the set, calculate their $lcm$ and then put it back into the set.

http://mathoverflow.net/questions/25055/time-complexity-of-finding-the-gcd-of-a-set-s-as-a-function-of-sums/25068#25068 Grigory Yaroslavtsev 2010-05-17T23:39:54Z 2010-05-17T23:39:54Z

Well, the big-O notation gives us an upper bound on the complexity, so the bounds I gave hold, but probably can be further improved.

http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24476#24476 Grigory Yaroslavtsev 2010-05-14T15:47:05Z 2010-05-14T15:47:05Z

Please, let me know if anything is unclear or accept the answer, if it is ok.

http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24476#24476 Grigory Yaroslavtsev 2010-05-13T13:53:05Z 2010-05-13T13:53:05Z

Please, see my second edit with a link.

http://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24422#24422 Grigory Yaroslavtsev 2010-05-13T08:51:13Z 2010-05-13T08:51:13Z

Suppose someone has developed a $poly(n,d)$-time algorithm $A(x)$ for the problem and we know this $poly(n,d)$, which is equal to some $p(n,d)$. Because for the minimal DFA that accepts all strings $d=1$, then the running time of the algorithm A is equal to some polynomial $q(n)$ if the given NFA is universal. If the given NFA is not universal than we just let A make $q(n)$ steps and terminate it if it hasn't terminated: either we found the DFA and can check directly or terminated and we know that the resulting DFA cannot be universal.

http://mathoverflow.net/questions/21641/maximum-number-of-perfect-matchings-in-a-graph/21648#21648 Grigory Yaroslavtsev 2010-04-17T21:42:23Z 2010-04-17T21:42:23Z

Thank you, this paper really gives the answer. In fact, it seems that the main result was obtained by Alon and Friedland in this paper: <a href="http://www.emis.ams.org/journals/EJC/Volume_15/PDF/v15i1n13.pdf" rel="nofollow">emis.ams.org/journals/EJC/Volume_15/PDF/&hellip;</a>. There they show that graphs which are union of complete bipartite graphs have the maximum number of perfect matchings among all graphs with the same degree sequence.

http://mathoverflow.net/questions/18608/counting-eulerian-orientation-in-a-4-regular-undirected-graph Grigory Yaroslavtsev 2010-03-18T23:48:36Z 2010-03-18T23:48:36Z

It can probably help somebody to answer you question if you give a link to the proof of #P-completeness for general case.

http://mathoverflow.net/questions/18479/maximum-bipartite-graph-1-n-matching/18510#18510 Grigory Yaroslavtsev 2010-03-17T19:22:04Z 2010-03-17T19:22:04Z

This is surely equivalent to maximum-clique, because you should just construct a graph, in which vertices correspond to $N(a)$ for each $a$ and connect two vertices with an edge iff the corresponding subsets intersect. Now you need to solve maximum-clique in the complement graph.

http://mathoverflow.net/questions/18277/what-is-the-square-root-of-42 Grigory Yaroslavtsev 2010-03-15T15:27:58Z 2010-03-15T15:27:58Z

This site is for questions that are &lt;b&gt;research level&lt;/b&gt;, not for school-level ones. Please, consider reading article on Wikipedia about square roots: <a href="http://en.wikipedia.org/wiki/Square_root" rel="nofollow">en.wikipedia.org/wiki/Square_root</a>. I suggest this question should be closed.