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.     

关于凸体覆盖的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提出的一个猜想做出了实质性进展.     

On Destabilization via Active Stiffness

Corless and Leitmann [2] have shown that a damped simple oscillator can be destabilized by varying the spring stiffness. The present note establishes that this result is closely related to the variational approach to absolute stability theory [1,6] both in substance and in method of proof. In particular, several key ideas employed in [2] appear in the work of Brockett [1].