User grigory yaroslavtsev - MathOverflow 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 Answer by Grigory Yaroslavtsev for Making a non-monotone function monotone 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 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 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 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 Answer by Grigory Yaroslavtsev for Time complexity of finding the GCD of a set S as a function of sum(S) 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 Answer by Grigory Yaroslavtsev for Emptiness and determinization of NFAs 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 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 Answer by Grigory Yaroslavtsev for Prove a function is primitive recursive 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> 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 Inverse for a permutation over GF(2) 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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 Comment by Grigory Yaroslavtsev 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.