Spectral Sparsification of Random-Walk Matrix Polynomials

We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial $$L_alpha(G)=D-sum_{r=1}^dalpha_rD(D^{-1}A)^r$$ where $A$ is the adjacency matrix of a weighted, undirected graph, $D$ is the diagonal matrix of weighted degrees, and $alpha=(alpha_1...alpha_d)$ are nonnegative coefficients with $sum_{r=1}^dalpha_r=1$. Recall that $D^{-1}A$ is the transition matrix of random walks on the graph. The sparsification of $L_alpha(G)$ appears to be algorithmically challenging as the matrix power $(D^{-1}A)^r$ is defined by all paths of length $r$, whose precise calculation would be prohibitively expensive. In this paper, we develop the first nearly linear time algorithm for this sparsification problem: For any $G$ with $n$ vertices and $m$ edges, $d$ coefficients $alpha$, and $epsilon > 0$, our algorithm runs in time $O(d^2mlog^2n/epsilon^{2})$ to construct a Laplacian matrix $tilde{L}=D-tilde{A}$ with $O(nlog n/epsilon^{2})$ non-zeros such that $tilde{L}approx_{epsilon}L_alpha(G)$. Matrix polynomials arise in mathematical analysis of matrix functions as well as numerical solutions of matrix equations. Our work is particularly motivated by the algorithmic problems for speeding up the classic Newtons method in applications such as computing the inverse square-root of the precision matrix of a Gaussian random field, as well as computing the $q$th-root transition (for $qgeq1$) in a time-reversible Markov model. The key algorithmic step for both applications is the construction of a spectral sparsifier of a constant degree random-walk matrix-polynomials introduced by Newtons method. Our algorithm can also be used to build efficient data structures for effective resistances for multi-step time-reversible Markov models, and we anticipate that it could be useful for other tasks in network analysis.

Signaling in Quasipolynomial time

Strategic interactions often take place in an environment rife with uncertainty. As a result, the equilibrium of a game is intimately related to the information available to its players. The emph{signaling problem} abstracts the task faced by an informed market maker, who must choose how to reveal information in order to effect a desirable equilibrium. In this paper, we consider two fundamental signaling problems: one for abstract normal form games, and the other for single item auctions. For the former, we consider an abstract class of objective functions which includes the social welfare and weighted combinations of players utilities, and for the latter we restrict our attention to the social welfare objective and to signaling schemes which are constrained in the number of signals used. For both problems, we design approximation algorithms for the signaling problem which run in quasi-polynomial time under various conditions, extending and complementing the results of various recent works on the topic. Underlying each of our results is a meshing scheme which effectively overcomes the curse of dimensionality and discretizes the space of essentially different posterior beliefs -- in the sense of inducing essentially different equilibria. This is combined with an algorithm for optimally assembling a signaling scheme as a convex combination of such beliefs. For the normal form game setting, the meshing scheme leads to a convex partition of the space of posterior beliefs and this assembly procedure is reduced to a linear program, and in the auction setting the assembly procedure is reduced to submodular function maximization.

Measurement of Cosmic Ray Flux in China JinPing underground Laboratory

China JinPing underground Laboratory (CJPL) is the deepest underground laboratory presently running in the world. In such a deep underground laboratory, the cosmic ray flux is a very important and necessary parameter for rare event experiments. A plastic scintillator telescope system has been set up to measure the cosmic ray flux. The performance of the telescope system has been studied using the cosmic ray on the ground laboratory near CJPL. Based on the underground experimental data taken from November 2010 to December 2011 in CJPL, which has effective live time of 171 days, the cosmic ray muon flux in CJPL is measured to be (2.0+-0.4)*10^(-10)/(cm^2)/(s). The ultra-low cosmic ray background guarantees CJPLs ideal environment for dark matter experiment.

The CDEX-1 1 kg Point-Contact Germanium Detector for Low Mass Dark Matter Searches

The CDEX Collaboration has been established for direct detection of light dark matter particles, using ultra-low energy threshold p-type point-contact germanium detectors, in China JinPing underground Laboratory (CJPL). The first 1 kg point-contact germanium detector with a sub-keV energy threshold has been tested in a passive shielding system located in CJPL. The outputs from both the point-contact p+ electrode and the outside n+ electrode make it possible to scan the lower energy range of less than 1 keV and at the same time to detect the higher energy range up to 3 MeV. The outputs from both p+ and n+ electrode may also provide a more powerful method for signal discrimination for dark matter experiment. Some key parameters, including energy resolution, dead time, decay times of internal X-rays, and system stability, have been tested and measured. The results show that the 1 kg point-contact germanium detector, together with its shielding system and electronics, can run smoothly with good performances. This detector system will be deployed for dark matter search experiments.