Abstract:
The traditional lower bound estimation method for powerlaw distributions based on the Kolmogorov-Smirnov distance proved to perform better than other competing methods. However, if applied to very large collections of data, such a method can be computationally demanding. In this paper, we propose two alternative methods with the aim to reduce the time required by the estimation procedure. We apply the traditional method and the two proposed methods to large collections of data ($N = 500,000$) with varying values of the true lower bound. Both the proposed methods yield a significantly better performance and accuracy than the traditional method.

Abstract:
In 1971, McMullen and Walkup posed the following conjecture, which is called the generalized lower bound conjecture: If $P$ is a simplicial $d$-polytope then its $h$-vector $(h_0,h_1,...,h_d)$ satisfies $h_0 \leq h_1 \leq ... \leq h_{\lfloor \frac d 2 \rfloor}$. Moreover, if $h_{r-1}=h_r$ for some $r \leq \frac d 2$ then $P$ can be triangulated without introducing simplices of dimension $\leq d-r$. The first part of the conjecture was solved by Stanley in 1980 using the hard Lefschetz theorem for projective toric varieties. In this paper, we give a proof of the remaining part of the conjecture. In addition, we generalize this property to a certain class of simplicial spheres, namely those admitting the weak Lefschetz property.

Abstract:
We obtain a query lower bound for quantum algorithms solving the phase estimation problem. Our analysis generalizes existing lower bound approaches to the case where the oracle Q is given by controlled powers Q^p of Q, as it is for example in Shor's order finding algorithm. In this setting we will prove a log (1/epsilon) lower bound for the number of applications of Q^p1, Q^p2, ... This bound is tight due to a matching upper bound. We obtain the lower bound using a new technique based on frequency analysis.

Abstract:
For any positive integer r, let pi_{2r}(x) denote the number of prime pairs (p, p+2r) with p not exceeding (large) x. According to the prime-pair conjecture of Hardy and Littlewood, pi_{2r}(x) should be asymptotic to 2C_{2r}li_2(x) with an explicit positive constant C_{2r}. A heuristic argument indicates that the remainder e_{2r}(x) in this approximation cannot be of lower order than x^beta, where beta is the supremum of the real parts of zeta's zeros. The argument also suggests an approximation for pi_{2r}(x) similar to one of Riemann for pi(x).

Abstract:
A $(d-1)$-dimensional simplicial complex is called balanced if its underlying graph admits a proper $d$-coloring. We show that many well-known face enumeration results have natural balanced analogs (or at least conjectural analogs). Specifically, we prove the balanced analog of the celebrated Lower Bound Theorem for pseudomanifolds and characterize the case of equality; we introduce and characterize the balanced analog of the Walkup class; we propose the balanced analog of the Generalized Lower Bound Conjecture and establish some related results. We close with constructions of balanced manifolds with few vertices.

Abstract:
We show that any quantum algorithm searching an ordered list of n elements needs to examine at least 1/12 log n-O(1) of them. Classically, log n queries are both necessary and sufficient. This shows that quantum algorithms can achieve only a constant speedup for this problem. Our result improves lower bounds of Buhrman and de Wolf(quant-ph/9811046) and Farhi, Goldstone, Gutmann and Sipser (quant-ph/9812057).

Abstract:
A fundamental problem in signal processing is to estimate signal from noisy observations. This is usually formulated as an optimization problem. Optimizations based on variational lower bound and minorization-maximization have been widely used in machine learning research, signal processing, and statistics. In this paper, we study iterative algorithms based on the conjugate function lower bound (CFLB) and minorization-maximization (MM) for a class of objective functions. We propose a generalized version of these two algorithms and show that they are equivalent when the objective function is convex and differentiable. We then develop a CFLB/MM algorithm for solving the MAP estimation problems under a linear Gaussian observation model. We modify this algorithm for wavelet-domain image denoising. Experimental results show that using a single wavelet representation the performance of the proposed algorithms makes better than that of the bishrinkage algorithm which is arguably one of the best in recent publications. Using complex wavelet representations, the performance of the proposed algorithm is very competitive with that of the state-of-the-art algorithms.

Abstract:
In high-level synthesis of VLSI circuits, good lower bound prediction can efficiently narrow down the large space of possible designs. Previous approaches predict the lower bound by relaxing or even ignoring the precedence constraints of the data flow graph (DFG), and result in inaccuracy of the lower bound. The loop folding and conditional branch were also not considered. In this paper, a new stepwise refinement algorithm is proposed, which takes consideration of precedence constraints of the DFG to estimate the lower bound of hardware resources under time constraints. Processing techniques to handle multi-cycle, chaining, pipelining, as well as loop folding and mutual exclusion among conditional branches are also incorporated in the algorithm. Experimental results show that the algorithm can produce a very tight and close to optimal lower bound in reasonable computation time. Shen Zhaoxuan received the B.Sc. degree in computer science from Zhejiang University, China and the M.Eng. degree in electrical and electronic engineering from Nanyang Technological University, Singapore. From August 1987 to January 1994, he was a research associate at Laboratory of CAD & Graphics, Institute of Computing Technologies, Chinese Academy of Sciences, Beijing, China. During 1996–1999, he was a senior engineer at Institute of High Performance Computing Singapore, developing parallel optimization algorithm for VLSI floorplanning, placement and synthesis, etc. He was a senior software engineer at Arcadia Design Systems, Inc. San Jose, CA, USA from March. 1999 to November 2000 and a senior engineer at Synopsys Inc. Mountain View, CA, USA from December 2000 to January 2002. He is now with Cadence Design Systems Inc. San Jose, CA, USA, developing new generation of P&R tools for SOC VLSI design. Dr. Shen received the 1991 First Class Science & technology Progressing Award from Chinese Academy of Sciences for the contribution to the EDCADS tool development. He has been an IEEE member since 1996. Jong Ching Chuen received the BSc (Eng) degree in electronics with computer science and the PhD degree in electronic engineering from Queen Mary College, University of London, U.K., in 1983 and 1988 respectively. From July 1987 to October 1990, he worked in the area of high-level synthesis of digital systems first in University of Southampton, U.K. and then in Racal Research Limited, U.K. In 1991, he joined the Nanyang Technological University, Singapore, as a faculty member. He is now an associate professor in the Division of Circuits and Systems, School of Electrical and Electronic Engineering. Dr. Jong is a chartered engineer, a member of IEE and a member of BCS. His technical interests include high-level synthesis, ASIC design and fast-prototyping of digital designs.

Abstract:
Computational technique for lower bound on Two-dimensional Diamond-1 constrained channel capacity is presented in this paper. It is basically an amalgamation of Matrix Fractal Grow Method (MFGM) and a new Matrix Fractal Reduction Method both applicable to state transition matrices of the corresponding constrained channels and Rayleigh Quotient Iteration method. Also other programming tricks are presented which improve its implementation. Estimation of lower bound values on the mentioned capacity is made using it. The results are in good alignment with known exact results, which is a verification of the new method. The method could be generalized for other constraints which are restricted only on one neighbor symbol in 2D constrained channel such as for example Square-1 and Hexagonal-1.

Abstract:
In this paper we use the Cramer-Rao lower uncertainty bound to estimate the maximum precision that could be achieved on the joint simultaneous (or 2D) estimation of photometry and astrometry of a point source measured by a linear CCD detector array. We develop exact expressions for the Fisher matrix elements required to compute the Cramer-Rao bound in the case of a source with a Gaussian light profile. From these expressions we predict the behavior of the Cramer-Rao astrometric and photometric precision as a function of the signal and the noise of the observations, and compare them to actual observations - finding a good correspondence between them. We show that the astrometric Cramer-Rao bound goes as $(S/N)^{-1}$ (similar to the photometric bound) but, additionally, we find that this bound is quite sensitive to the value of the background - suppressing the background can greatly enhance the astrometric accuracy. We present a systematic analysis of the elements of the Fisher matrix in the case when the detector adequately samples the source (oversampling regime), leading to closed-form analytical expressions for the Cramer-Rao bound. We show that, in this regime, the joint parametric determination of photometry and astrometry for the source become decoupled from each other, and furthermore, it is possible to write down expressions (approximate to first order in the small quantities F/B or B/F) for the expected minimum uncertainty in flux and position. These expressions are shown to be quite resilient to the oversampling condition, and become thus very valuable benchmark tools to estimate the approximate behavior of the maximum photometric and astrometric precision attainable under pre-specified observing conditions and detector properties.