Possible Exotic Phases in the One-Dimensional Extended Hubbard Model

We investigate numerically the ground state phase diagram of the one-dimensional extended Hubbard model, including an on--site interaction U and a nearest--neighbor interaction V. We focus on the ground state phases of the model in the V >> U region, where previous studies have suggested the possibility of dominant superconducting pairing fluctuations before the system phase separates at a critical value V=V_PS. Using quantum Monte Carlo methods on lattices much larger than in previous Lanczos diagonalization studies, we determine the boundary of phase separation, the Luttinger Liquid correlation exponent K_rho, and other correlation functions in this region. We find that phase separation occurs for V significantly smaller than previously reported. In addition, for negative U, we find that a uniform state re-enters from phase separation as the electron density is increased towards half filling. For V < V_PS, our results show that superconducting fluctuations are not dominant. The system behaves asymptotically as a Luttinger Liquid with K_rho < 1, but we also find strong low-energy (but gapped) charge-density fluctuations at a momentum not expected for a standard Luttinger Liquid.

Approximately Uniform Random Sampling in Sensor Networks

Recent work in sensor databases has focused extensively on distributed query problems, notably distributed computation of aggregates. Existing methods for computing aggregates broadcast queries to all sensors and use in-network aggregation of responses to minimize messaging costs. In this work, we focus on uniform random sampling across nodes, which can serve both as an alternative building block for aggregation and as an integral component of many other useful randomized algorithms. Prior to our work, the best existing proposals for uniform random sampling of sensors involve contacting all nodes in the network. We propose a practical method which is only approximately uniform, but contacts a number of sensors proportional to the diameter of the network instead of its size. The approximation achieved is tunably close to exact uniform sampling, and only relies on well-known existing primitives, namely geographic routing, distributed computation of Voronoi regions and von Neumann's rejection method. Ultimately, our sampling algorithm has the same worst-case asymptotic cost as routing a point-to-point message, and thus it is asymptotically optimal among request/reply-based sampling methods. We provide experimental results demonstrating the effectiveness of our algorithm on both synthetic and real sensor topologies.

Subset Warping: Rubber Sheeting with Cuts

Image warping, often referred to as "rubber sheeting" represents the deformation of a domain image space into a range image space. In this paper, a technique is described which extends the definition of a rubber-sheet transformation to allow a polygonal region to be warped into one or more subsets of itself, where the subsets may be multiply connected. To do this, it constructs a set of "slits" in the domain image, which correspond to discontinuities in the range image, using a technique based on generalized Voronoi diagrams. The concept of medial axis is extended to describe inner and outer medial contours of a polygon. Polygonal regions are decomposed into annular subregions, and path homotopies are introduced to describe the annular subregions. These constructions motivate the definition of a ladder, which guides the construction of grid point pairs necessary to effect the warp itself.