Skip to main content
Grigory Yaroslavtsev's user avatar
Grigory Yaroslavtsev's user avatar
Grigory Yaroslavtsev's user avatar
Grigory Yaroslavtsev
  • Member for 15 years
  • Last seen more than 1 year ago
awarded
awarded
awarded
accepted
answered
Loading…
awarded
comment
Approximation theory under $L_1$-error
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.
revised
Approximation theory under $L_1$-error
added 56 characters in body; added 17 characters in body
Loading…
asked
Loading…
accepted
comment
Volume change under linear transformation
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.
comment
Volume change under linear transformation
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?
asked
Loading…
awarded
comment
comment
Is every input gate of a Boolean Circuit (to decide a language) on a path to the output gate?
Boolean circuit is an acyclic graph, are you sure that accessibility problem for acyclic graphs is still $NLOGSPACE$-complete?
revised
Loading…
comment
Time complexity of finding the GCD of a set S as a function of sum(S)
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.
comment
Time complexity of finding the GCD of a set S as a function of sum(S)
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.
Loading…