bio | website | logic.pdmi.ras.ru/~grigory |
---|---|---|
location | United States | |
age | 26 | |
visits | member for | 4 years, 4 months |
seen | Dec 23 '13 at 12:14 | |
stats | profile views | 631 |
Jun 25 |
awarded | Revival |
Jun 25 |
awarded | Promoter |
Mar 13 |
accepted | Making a non-monotone function monotone |
Mar 2 |
answered | Making a non-monotone function monotone |
Feb 27 |
awarded | Popular Question |
Jan 21 |
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. |
Jan 21 |
revised |
Approximation theory under $L_1$-error
added 56 characters in body; added 17 characters in body |
Jan 21 |
asked | Approximation theory under $L_1$-error |
Nov 9 |
accepted | Volume change under linear transformation |
Nov 9 |
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. |
Nov 9 |
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? |
Nov 9 |
asked | Volume change under linear transformation |
Dec 18 |
awarded | Yearling |
Jul 22 |
comment |
Cycles of length 1(mod 3) in regular graphs
Do you mean simple cycle? |
May 21 |
comment |
Is every input gate of a Boolean Circuit (to decide a language) on a path to the output gate?
@Niall: Thank you |
May 20 |
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? |
May 18 |
revised |
Time complexity of finding the GCD of a set S as a function of sum(S)
deleted 202 characters in body |
May 17 |
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. |
May 17 |
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. |
May 17 |
answered | Time complexity of finding the GCD of a set S as a function of sum(S) |