# Tag Info

1

Grobner bases are used for the fastest list decoding algorithms for Reed-Solomon codes: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.320.1170&rep=rep1&type=pdf

5

I think you're unlikely to get a good answer, because this is tied up in difficult and unsolved algebraic problems. The issue is that Euclidean path lengths (for points with integer coordinates) can be expressed as sums of square roots, but we don't know how small the difference between two distinct sums of square roots can be. Because of this, we also don't ...

0

I finally managed to ask the person that originally told me about this approach. It appears to be closely related to maximum variance unfolding (MVU), see also https://en.wikipedia.org/wiki/Semidefinite_embedding. The paper introducing this approach is "Learning a kernel matrix for nonlinear dimensionality reduction" by Weinberger, Sha, and Saul if I am not ...

5

This question has been resolved! A few days ago Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs uploaded a preprint showing the existence of a total function $f$ which satisfies $R_0(f) = \tilde{\Omega}(R_2(f)^{3/2})$ and even $R_0(f) = \tilde{\Omega}(R_1(f)^{3/2})$, where $R_1(f)$ denotes 1-sided ...

7

Assume as given that $m=\omega(\sqrt{n})$. Fix any $\epsilon>0$. We will consider $r\in[1,n]$ with $r<(1-\epsilon)n$. The aim is to show that with high probability as $n\to\infty$, $r$ is included in the set of differences. First consider the set $A=\{a_i:i<m/2\}\cap[1,\epsilon n]$. The number of $i$ with $i<m/2$ such that $a_i<\epsilon n$ ...

10

This question is related to the so called insertion systems. An insertion system is a special type of rewriting system whose rules are of the form $1 \rightarrow r$ for all $r$ in a given language $R$. Let us write $u \rightarrow_R v$ if $u = u'u''$ and $v = u'ru''$ for some $r \in R$. Let us denote by $\buildrel{*}\over\rightarrow_R$ the reflexive ...

7

The classic reference for complexity of computation of real functions is: Ker-I Ko, Computational Complexity of Real Functions, 1991 Also have a look at chapter 7 in Weirauch's book.

Top 50 recent answers are included