Complementarity and Additivity for Covariant Channels

This paper contains several new results concerning covariant quantum channels in d ≥ 2 dimensions. The first part, Sec. 3, based on [4], is devoted to unitarily covariant channels, namely depolarizing and transpose-depolarizing channels. The second part, Sec. 4, based on [10], studies Weyl-covariant channels. These results are preceded by Sec. 2 in which we discuss various representations of general completely positive maps and channels. In the first part of the paper we compute complementary channels for depolarizing and transpose-depolarizing channels. This method easily yields minimal Kraus representations from non-minimal ones. We also study properties of the output purity of the tensor product of a channel and its complementary. In the second part, the formalism of discrete noncommutative Fourier transform is developed and applied to the study of Weyl-covariant maps and channels. We then extend a result in [16] concerning a bound for the maximal output 2-norm of a Weyl-covariant channel. A class of maps which attain the bound is introduced, for which the multiplicativity of the maximal output 2-norm is proven. The complementary channels are described which have the same multiplicativity properties as the Weyl-covariant channels.     

An introduction to Wu's method for mechanical theorem proving in geometry

Wu's algebraic method for mechanically proving geometry theorems is presented at a level as elementary as possible with sufficient examples for further understanding the complete method.The work reported here was supported by NSF Grant DCR-8503498.     

How to find Steiner minimal trees in euclideand-space

This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connectingN sites ind-space,d >- 2. We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for finding Steiner minimal trees ind-space ford > 2, and also the first one which fits naturally into the framework of backtracking and branch-and-bound. Finding SMTs of up toN = 12 general sites ind-space (for anyd) now appears feasible.We tabulate Steiner minimal trees for many point sets, including the vertices of most of the regular and Archimedeand-polytopes with <- 16 vertices. As a consequence of these tables, the Gilbert-Pollak conjecture is shown to be false in dimensions 3–9. (The conjecture remains open in other dimensions; it is probably false in all dimensionsd withd 3, but it is probably true whend = 2.)The second purpose is to present some new theoretical results regarding the asymptotic computational complexity of finding SMTs to precision .We show that in two-dimensions, Steiner minimum trees may be found exactly in exponential time O(C ^N ) on a real RAM. (All previous provable time bounds were superexponential.) If the tree is only wanted to precision , then there is an (N/)^O(N)-time algorithm, which is subexponential if 1/ grows only polynomially withN. Also, therectilinear Steiner minimal tree ofN points in the plane may be found inN ^O(N) time.J. S. Provan devised an O(N ⁶/⁴)-time algorithm for finding the SMT of a convexN-point set in the plane. (Also the rectilinear SMT of such a set may be found in O(N ⁶) time.) One therefore suspects that this problem may be solved exactly in polynomial time. We show that this suspicion is in fact true—if a certain conjecture about the size of Steiner sensitivity diagrams is correct.All of these algorithms are for a real RAM model of computation allowing infinite precision arithmetic. They make no probabilistic or other assumptions about the input; the time bounds are valid in the worst case; and all our algorithms may be implemented with a polynomial amount of space. Only algorithms yielding theexact optimum SMT, or trees with lengths (1 + ) × optimum, where is arbitrarily small, are considered here.     

关于凸体覆盖的Hadwiger猜想

针对Hadwiger猜想这一凸和离散几何中持续了近60年的著名难题,回顾了这一猜想的提出,它的若干等价形式,以及前人在尝试解决这一猜想的过程中取得的阶段性进展.介绍了该猜想相关的若干研究问题及相应结果.结果表明:一方面,Hadwiger猜想仍是一个远未解决的公开难题;另一方面,围绕着Hadwiger猜想及其相关问题还有大量亟待完成的基础性研究工作。     

Partition arguments in multiparty communication complexity

Consider the “Number in Hand” multiparty communication complexity model, where k players holding inputs x₁,…,x_k∈{0,1}ⁿ communicate to compute the value f(x₁,…,x_k) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem.In this paper, we study the power of partition arguments. Our two main results are very different in nature:

(i)

For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function f whose communication complexity is Ω(n), while partition arguments can only yield an Ω(logn) lower bound. The same holds for nondeterministiccommunication complexity.

(ii)

For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the “log-rank conjecture” in communication complexity. We also observe that, in the case of computing relations (search problems), very large gaps do exist.

We conclude with two results on the multiparty “fooling set technique”, another method for obtaining communication complexity lower bounds.     

A Parametric Texture Model Based on Joint Statistics of Complex Wavelet Coefficients

We present a universal statistical model for texture images in the context of an overcomplete complex wavelet transform. The model is parameterized by a set of statistics computed on pairs of coefficients corresponding to basis functions at adjacent spatial locations, orientations, and scales. We develop an efficient algorithm for synthesizing random images subject to these constraints, by iteratively projecting onto the set of images satisfying each constraint, and we use this to test the perceptual validity of the model. In particular, we demonstrate the necessity of subgroups of the parameter set by showing examples of texture synthesis that fail when those parameters are removed from the set. We also demonstrate the power of our model by successfully synthesizing examples drawn from a diverse collection of artificial and natural textures.     

关于Smarandache可求和因数对问题

对任意正整数n,设d（n）表示n的Dirichlet除数函数,即就是n的所有不同正因数的个数.著名的Smarandache可求和因数对问题是指：是否存在无穷多个正整数m及n,使得d（m）＋d（n）=d（m＋n）,其中（m,n）=1.利用初等方法以及著名的陈景润定理研究这一问题,即证明存在无穷多个正整数m及n且（m,n）≤2,使得d（m）＋d（n）=d（m＋n）,其中（m,n）表示m和n的最大公约数.从而将AmarnathMurthy及Charles Ashbacher提出的一个猜想做出了实质性进展.