In this paper, based on a discrete spectral problem and the corresponding zero curvature representation,the isospectral and nonisospectral lattice hierarchies are proposed. An algebraic structure of discrete zero curv...In this paper, based on a discrete spectral problem and the corresponding zero curvature representation,the isospectral and nonisospectral lattice hierarchies are proposed. An algebraic structure of discrete zero curvature equations is then established for such integrable systems. the commutation relations of Lax operators corresponding to the isospectral and non-isospectral lattice flows are worked out, the master symmetries of each lattice equation in the isospectral hierarchyand are generated, thus a τ-symmetry algebra for the lattice integrable systems is engendered from this theory.展开更多
It is well known that almost all subset sum problems with density less than 0.9408… can be solved in polynomial time with an SVP oracle that can find a shortest vector in a special lattice.In this paper,the authors s...It is well known that almost all subset sum problems with density less than 0.9408… can be solved in polynomial time with an SVP oracle that can find a shortest vector in a special lattice.In this paper,the authors show that a similar result holds for the k-multiple subset sum problem which has k subset sum problems with exactly the same solution.Specially,for the single subset sum problem(k=1),a modified lattice is introduced to make the proposed analysis much simpler and the bound for the success probability tighter than before.Moreover,some extended versions of the multiple subset sum problem are also considered.展开更多
We briefly survey a number of important recent uchievements in Theoretical Computer Science （TCS）, especially Computational Complexity Theory. We will discuss the PCP Theorem, its implications to inapproximability o...We briefly survey a number of important recent uchievements in Theoretical Computer Science （TCS）, especially Computational Complexity Theory. We will discuss the PCP Theorem, its implications to inapproximability on combinatorial optimization problems; space bounded computations, especially deterministic logspace algorithm for undirected graph connectivity problem; deterministic polynomial-time primality test; lattice complexity, worst-case to average-case reductions; pseudorandomness and extractor constructions; and Valiant＇s new theory of holographic algorithms and reductions.展开更多
基金Supported by the National Science Foundation of China under Grant No.11371244the Applied Mathematical Subject of SSPU under Grant No.XXKPY1604
文摘In this paper, based on a discrete spectral problem and the corresponding zero curvature representation,the isospectral and nonisospectral lattice hierarchies are proposed. An algebraic structure of discrete zero curvature equations is then established for such integrable systems. the commutation relations of Lax operators corresponding to the isospectral and non-isospectral lattice flows are worked out, the master symmetries of each lattice equation in the isospectral hierarchyand are generated, thus a τ-symmetry algebra for the lattice integrable systems is engendered from this theory.
基金supported by the National Natural Science Foundation of China under Grant Nos.11201458,11471314in part by 973 Project under Grant No.2011CB302401in part by the National Center for Mathematics and Interdisciplinary Sciences,Chinese Academy of Sciences
文摘It is well known that almost all subset sum problems with density less than 0.9408… can be solved in polynomial time with an SVP oracle that can find a shortest vector in a special lattice.In this paper,the authors show that a similar result holds for the k-multiple subset sum problem which has k subset sum problems with exactly the same solution.Specially,for the single subset sum problem(k=1),a modified lattice is introduced to make the proposed analysis much simpler and the bound for the success probability tighter than before.Moreover,some extended versions of the multiple subset sum problem are also considered.
文摘We briefly survey a number of important recent uchievements in Theoretical Computer Science （TCS）, especially Computational Complexity Theory. We will discuss the PCP Theorem, its implications to inapproximability on combinatorial optimization problems; space bounded computations, especially deterministic logspace algorithm for undirected graph connectivity problem; deterministic polynomial-time primality test; lattice complexity, worst-case to average-case reductions; pseudorandomness and extractor constructions; and Valiant＇s new theory of holographic algorithms and reductions.
