Dima Pasechnik
|
Registered User
|
|
|
May 14 |
revised |
What is the “fundamental theorem of invariant theory” ? fixing double _ typos |
|
May 13 |
answered | Usage of complex moments in complex plane |
|
May 8 |
revised |
Orders in number fields fixed the link |
|
Apr 22 |
comment |
What are the most important open problems in algebraic combinatorics? algebraic combinatorics is a wide subject (Stanley naturally, only treats problems from "his" area) and what really is "biggest" is a very subjective question. |
|
Apr 4 |
comment |
Two questions about combinatorics journals 1. The list contains a number of highly questionable entries... |
|
Apr 3 |
comment |
Inversion of complex matrix does $AB=BA$ hold, by any chance? |
|
Apr 1 |
comment |
Strassen’s algorithm What exactly do you mean by "any algorithm"? IMHO any procedure performing a sequence of arithmetic operations can be expressed by the tensor formalism, but beyond that one cannot say anything. |
|
Mar 31 |
comment |
On mentioning recommenders' names in cover letter for postdoctoral applications It seems that he's interested in postdoc in Europe, and not many places in Europe use mathjobs. In fact, the postdoc market in Europe is quite different from the one in USA, as there are lots of grant-funded postdocs, tied up to particular topics, and relatively few equivalents to USA instructorships. |
|
Mar 27 |
comment |
Polyhedra Classification I wonder if anyone looked at the non-convex case. |
|
Mar 26 |
comment |
automorphisms of graphs and finite permutation groups regarding dessin d'enfant, I liked this book by S.Lando and A.Zvonkin: springer.com/mathematics/geometry/book/… Other than that, I can't help noticing that our answers have virtually empty intersection. :–) |
|
Mar 26 |
answered | automorphisms of graphs and finite permutation groups |
|
Mar 25 |
comment |
Conditions for a graph to be the 1- skeleton of a Surface I guess it should be 3-connected, and this is the only condition. (But I might be off by a lot :–)) |
|
Mar 25 |
comment |
Vector chromatic number and Lovasz theta For the graph in question, computing $\theta$ and $\theta'$ reduces to linear programming, as it comes from a commutative association scheme. |
|
Mar 24 |
comment |
Cyclically symmetric functions There is an example with the cyclic group of order 5 in B.Sturmfels' "Algorithms in invariant theory", Sect. 2.7. The latter section has a general treatment of finite abelian groups, too. It actually looks as if the number of generators of the ring grows quite fast as n increases, e.g. in the case of n=5 you need 11 generators. Counting/finding generators amounts to dealing with certain integer points in a lattice... B.Sturmfels' "Algorithms in invariant theory" (2nd edition) ISBN 978-3-211-77416-8 Springer 2008, Wien New-York |
|
Mar 23 |
answered | Extremely messy proofs |
|
Mar 19 |
answered | What is the dual of an semidefinitely representable (SDR) cone? |
|
Mar 19 |
comment |
Rigorous numerics for maxima and minima (one variable) it might not come to quantifier elimination. Generically, $f'(x)=0$ together with the equations for extra variables needed for getting rid of square roots and the denominator will give you a 0-dimensional ideal. Then you're almost done... |
|
Mar 19 |
answered | Rigorous numerics for maxima and minima (one variable) |
|
Mar 17 |
comment |
Is that true all the convex optimization problems can be solved in polynomial time using interior-point algorithms (1) as an SDP can have a non-0 duality gap, the primal and the dual problems are not equivalent. They are really different and hard to compare, IMHO. |
|
Mar 17 |
comment |
Is that true all the convex optimization problems can be solved in polynomial time using interior-point algorithms (2) - but note that it will remain an approximation, with arbitrary precision, just by nature of the ellipsoid method, and the fact that, unlike in LP, there are no rational vertex solutions, in general. If you want an exact (algebraic numbers!) solution, then the only known algorithms would be exponential-time w.r.t. the dimension or w.r.t. the number of constraints. |
|
Mar 17 |
comment |
Is that true all the convex optimization problems can be solved in polynomial time using interior-point algorithms Tim: (2) in short, the ellipsoid method seems to me the only one for which the complexity is known to be polynomial-time in the classical model of computation, assuming that the diameter of a Euclidean ball containing the feasible set is a part of the input. And the latter might be doubly exponential in the rest of the problem size, as examples of Khachiyan and Porkolab show. In some cases this diameter is small, and so it's not an issue, e.g. this is so for the MAXCUT SDP relaxation by Goemans and Williamson. |
|
Mar 15 |
comment |
Looking for a maximum convert to an integral, note that erf is an integral too, change the order of integration... |
|
Mar 13 |
comment |
Simple groups analogous to fields The main motivation is to decompose complicated objects into simpler ones, using natural maps. In different categories the complexity of objects might be totally different. E.g. finite groups vs finite abelian groups. More interesting is perhaps the relationship between commutative algebra and algebraic geometry. There the correspondence between well-chosen "simple objects" is often 1-to-1. |
|
Mar 13 |
awarded | ● Citizen Patrol |
|
Mar 12 |
comment |
Bessel identities what is "*" in your notation? Too much MATLAB recently ? :-) |
|
Mar 9 |
comment |
Integer factorization with LP/ILP While I could imagine that you might have an ILP reformulation, an LP reformulation would be quite a feat... |
|
Mar 9 |
comment |
Does the cubic planar graph with 6 3-faces and 6 7-faces have a name? This is a bit of a hack, but you can do something like this: sage: import inspect sage: g=inspect.getmembers(graphs, predicate=inspect.isfunction) will give you a correspondence between graph names and functions to create these named graphs (not all of entries of g would correspond to actual named graphs, so you'd need to be a bit careful) |
|
Mar 9 |
answered | Does the cubic planar graph with 6 3-faces and 6 7-faces have a name? |
|
Mar 9 |
comment |
The existential theory of the reals in practice, exact symbolic algorithms for ETR are quite slow; in particular, the running time is exponential in the number of variables, with a largish constant. Algorithms based on sums of squares relaxations are faster, although the computations they perform are only approximate, implying all sorts of theoretical nastiness. |
|
Mar 8 |
comment |
From reducible polynomial to an irreducible one the poster did not ask for a ring... |
|
Mar 7 |
comment |
Algebraic Independence of Polynomials in n Variables with Real Coefficients hmm, what do you mean by dependency of algebraic equations, as opposed to polynomials? |
|
Mar 6 |
comment |
Permutation character of the symmetric group on subsets of certain size As you read arXiv:0903.2864, I expected that you know some representation theory of $S_n$. It is not something one can explain in one mathoverflow answer, IMHO. |
|
Mar 6 |
accepted | Permutation character of the symmetric group on subsets of certain size |
|
Mar 6 |
comment |
Permutation character of the symmetric group on subsets of certain size See the PS I just added to my answer. |
|
Mar 6 |
revised |
Permutation character of the symmetric group on subsets of certain size added an explicit references; added 11 characters in body |
|
Mar 6 |
comment |
Permutation character of the symmetric group on subsets of certain size Stanley mostly does the corresponding character theory, in terms of symmetric functions. |
|
Mar 6 |
comment |
Permutation character of the symmetric group on subsets of certain size No, not in Stanley's book. Any book on the representation theory of $S_n$ will have it, or you can look in these notes, Sect 4.12: ocw.mit.edu/courses/mathematics/… Or Sect.1 of my old lecture notes: www1.spms.ntu.edu.sg/~dima/mas722/2011/notes/… |
|
Mar 6 |
answered | Permutation character of the symmetric group on subsets of certain size |
|
Mar 5 |
accepted | What kind is this optimization problem |
|
Mar 5 |
revised |
What kind is this optimization problem added a shorter derivation |
|
Mar 4 |
comment |
What kind is this optimization problem surely, as we are in the univariate case, the positivity of $f$ is equivalent to it being a sum of squares, which boils down to that matrix being positive semi-definitene. |
|
Mar 4 |
revised |
What kind is this optimization problem edited tags |
|
Mar 4 |
answered | What kind is this optimization problem |
|
Feb 16 |
comment |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another if the chip $i$ must go the final vertex $v_i$, it's completely different story, for which Gunter's procedure certainly doesn't work. |
|
Feb 16 |
comment |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another Right, I gave up too quickly. Now, at least I know why these motion planning problems on graphs need a "pusher" to make them hard! |
|
Feb 16 |
revised |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another mild editing for clarity |
|
Feb 16 |
revised |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another added 58 characters in body |
|
Feb 16 |
revised |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another fixed the 2nd reference |
|
Feb 16 |
comment |
Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another I'll blame my wife - I never played Sokoban myself ;) |
|
Feb 15 |
answered | Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another |
