caozhu

Beijing, China

Age: 24

I'm a fourth year undergraduate student in Tsinghua University.

Apr
1
awarded Commentator
Apr
1
comment Exactly solvable but non-trivial integrality gap
I'm afraid the answer would probably be no. Any familiar problems with non-trivial integrality gap are NP, such as vertex cover. In fact, for polynomial time solvable problems, one can manually construct an LP that gives the answer while having no integrality gaps.
Apr
1
awarded Informed
Apr
1
awarded Editor
Nov
20
comment Why is HAMILTONIAN CYCLE so different from PERMANENT?
I have a question a bit off the topic. May I ask why PERMANENT is in P over the boolean semiring? I'm not aware of such an algorithm.
Sep
24
awarded Autobiographer
Sep
24
awarded Autobiographer
Sep
24
awarded Autobiographer
Sep
24
awarded Autobiographer
Sep
24
awarded Autobiographer
Sep
24
awarded Autobiographer
Sep
24
awarded Autobiographer
Apr
22
awarded Popular Question
Mar
23
comment Extensions of Sylvester's inertia law?
The problem description is not at all clear. How is $n$ defined for example. And is all the coordinate of $M$ belongs to the same space so that $F$ can be well defined. A more precise formulation of the problem would be adding the condition that $M:R^n \times \dots \times R^n \to R$.
Feb
21
comment $NP$-completeness of recognizing the difference of two permutations
Why not ask Peter directly? @Peter
Feb
20
comment Crown Rule Reduction In Parameterized Complexity - Vertex Cover - Notion Question
From your description, I don't see any errors.
Feb
20
comment Sorting using read-only stacks
I don't think it's possible to print the sorted list given the allowed operations. According to the register machine model, the first entry printed must be one of the first element of some register. Thus if the smallest element is at the end of one register, we can't possibly print it out firstly as it should be.
Nov
19
awarded Popular Question
Jun
15
awarded Supporter
Jun
15
awarded Student
1 2 3 4