Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
55works
0followers
31topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

55 published item(s)

preprint2026arXiv

High-Dimensional Noise to Low-Dimensional Manifolds: A Manifold-Space Diffusion Framework for Degraded Hyperspectral Image Classification

Recently, Hyperspectral Image (HSI) classification has attracted increasing attention in remote sensing. However, HSI data are inherently high-dimensional but low-rank, with discriminative information concentrated on a low-dimensional latent manifold. In real-world remote sensing scenarios, the superposition of multiple degradation factors disrupts this intrinsic manifold structure, driving samples away from their original low-dimensional distribution and introducing substantial redundant and non-discriminative variations. To better handle this challenge, this paper proposes a manifold-space diffusion framework (MSDiff) for robust hyperspectral classification under complex degradation conditions. Specifically, the proposed method first maps high-dimensional, degradation-affected HSI data into a compact low-dimensional manifold through a discriminative spectral-spatial reconstruction task, preserving class semantics and reducing redundant variations. A diffusion-based generative model is then applied to regularize the spectral-spatial distribution within the manifold, enabling progressive refinement and stabilization of latent features against residual degradations. The key advantage of the proposed framework lies in performing diffusion-based distribution modeling directly on the low-dimensional manifold, effectively decoupling degradation-induced disturbances from intrinsic discriminative structures and enhancing representation stability under complex degradations. Experimental results on multiple hyperspectral benchmarks demonstrate consistent performance improvements over state-of-the-art methods under diverse composite degradation settings. The code will be available at https://github.com/yangboxiang1207/MSDiff

preprint2024arXiv

GainNet: Coordinates the Odd Couple of Generative AI and 6G Networks

The rapid expansion of AI-generated content (AIGC) reflects the iteration from assistive AI towards generative AI (GAI) with creativity. Meanwhile, the 6G networks will also evolve from the Internet-of-everything to the Internet-of-intelligence with hybrid heterogeneous network architectures. In the future, the interplay between GAI and the 6G will lead to new opportunities, where GAI can learn the knowledge of personalized data from the massive connected 6G end devices, while GAI's powerful generation ability can provide advanced network solutions for 6G network and provide 6G end devices with various AIGC services. However, they seem to be an odd couple, due to the contradiction of data and resources. To achieve a better-coordinated interplay between GAI and 6G, the GAI-native networks (GainNet), a GAI-oriented collaborative cloud-edge-end intelligence framework, is proposed in this paper. By deeply integrating GAI with 6G network design, GainNet realizes the positive closed-loop knowledge flow and sustainable-evolution GAI model optimization. On this basis, the GAI-oriented generic resource orchestration mechanism with integrated sensing, communication, and computing (GaiRom-ISCC) is proposed to guarantee the efficient operation of GainNet. Two simple case studies demonstrate the effectiveness and robustness of the proposed schemes. Finally, we envision the key challenges and future directions concerning the interplay between GAI models and 6G networks.

preprint2024arXiv

Possible Meissner effect near room temperature in copper-substituted lead apatite

With copper-substituted lead apatite below room temperature, we observe diamagnetic dc magnetization under magnetic field of 25 Oe with remarkable bifurcation between zero-field-cooling and field-cooling measurements, and under 200 Oe it changes to be paramagnetism. A glassy memory effect is found during cooling. Typical hysteresis loops for superconductors are detected below 250 K, along with an asymmetry between forward and backward sweep of magnetic field. Our experiment suggests at room temperature the Meissner effect is possibly present in this material.

preprint2024arXiv

Towards Integrated Fine-tuning and Inference when Generative AI meets Edge Intelligence

The high-performance generative artificial intelligence (GAI) represents the latest evolution of computational intelligence, while the blessing of future 6G networks also makes edge intelligence (EI) full of development potential. The inevitable encounter between GAI and EI can unleash new opportunities, where GAI's pre-training based on massive computing resources and large-scale unlabeled corpora can provide strong foundational knowledge for EI, while EI can harness fragmented computing resources to aggregate personalized knowledge for GAI. However, the natural contradictory features pose significant challenges to direct knowledge sharing. To address this, in this paper, we propose the GAI-oriented synthetical network (GaisNet), a collaborative cloud-edge-end intelligence framework that buffers contradiction leveraging data-free knowledge relay, where the bidirectional knowledge flow enables GAI's virtuous-cycle model fine-tuning and task inference, achieving mutualism between GAI and EI with seamless fusion and collaborative evolution. Experimental results demonstrate the effectiveness of the proposed mechanisms. Finally, we discuss the future challenges and directions in the interplay between GAI and EI.

preprint2023arXiv

QoE-oriented Dependent Task Scheduling under Multi-dimensional QoS Constraints over Distributed Networks

Task scheduling as an effective strategy can improve application performance on computing resource-limited devices over distributed networks. However, existing evaluation mechanisms fail to depict the complexity of diverse applications, which involve dependencies among tasks, computing resource requirements, and multi-dimensional quality of service (QoS) constraints. Furthermore, traditional QoS-oriented task scheduling strategies struggle to meet the performance requirements without considering differences in satisfaction and acceptance of application, leading application failures and resource wastage. To tackle these issues, a quality of experience (QoE) cost model is designed to evaluate application completion, depicting the relationship among application satisfaction, communications, and computing resources in the distributed networks. Specifically, considering the sensitivity and preference of QoS, we model the different dimensional QoS degradation cost functions for dependent tasks, which are then integrated into the QoE cost model. Based on the QoE model, the dependent task scheduling problem is formulated as the minimization of overall QoE cost, aiming to improve the application performance in the distributed networks, which is proven Np-hard. Moreover, a heuristic Hierarchical Multi-queue Task Scheduling Algorithm (HMTSA) is proposed to address the QoE-oriented task scheduling problem among multiple dependent tasks, which utilizes hierarchical multiple queues to determine the optimal task execution order and location according to different dimensional QoS priorities. Finally, extensive experiments demonstrate that the proposed algorithm can significantly improve the satisfaction of applications.

preprint2022arXiv

A Comparative Study on Application of Class-Imbalance Learning for Severity Prediction of Adverse Events Following Immunization

In collaboration with the Liaoning CDC, China, we propose a prediction system to predict the subsequent hospitalization of children with adverse reactions based on data on adverse events following immunization. We extracted multiple features from the data, and selected "hospitalization or not" as the target for classification. Since the data are imbalanced, we used various class-imbalance learning methods for training and improved the RUSBoost algorithm. Experimental results show that the improved RUSBoost has the highest Area Under the ROC Curve on the target among these algorithms. Additionally, we compared these class-imbalance learning methods with some common machine learning algorithms. We combined the improved RUSBoost with dynamic web resource development techniques to build an evaluation system with information entry and vaccination response prediction capabilities for relevant medical practitioners.

preprint2022arXiv

High-quality grand unified theories with three generations

We extend the unitary groups beyond the ${\rm SU}(5)$ and ${\rm SU}(6)$ to look for possible grand unified theories that give rise to three-generational Standard Model fermions without the simple repetition. By demanding asymptotic free theories at short distances, we find gauge groups of ${\rm SU}(7)$, ${\rm SU}(8)$ and ${\rm SU}(9)$ together with their anomaly-free irreducible representations are such candidates. Two additional gauge groups of ${\rm SU}(10)$ and ${\rm SU}(11)$ can also achieve the generational structure without asymptotic freedom. We also find these models can solve the Peccei-Quinn (PQ) quality problem which is intrinsic in the axion models, with the leading PQ-breaking operators determined from the symmetry requirement.

preprint2022arXiv

Multi-Domain Virtual Network Embedding Algorithm based on Horizontal Federated Learning

Network Virtualization (NV) is an emerging network dynamic planning technique to overcome network rigidity. As its necessary challenge, Virtual Network Embedding (VNE) enhances the scalability and flexibility of the network by decoupling the resources and services of the underlying physical network. For the future multi-domain physical network modeling with the characteristics of dynamics, heterogeneity, privacy, and real-time, the existing related works perform satisfactorily. Federated learning (FL) jointly optimizes the network by sharing parameters among multiple parties and is widely employed in disputes over data privacy and data silos. Aiming at the NV challenge of multi-domain physical networks, this work is the first to propose using FL to model VNE, and presents a VNE architecture based on Horizontal Federated Learning (HFL) (HFL-VNE). Specifically, combined with the distributed training paradigm of FL, we deploy local servers in each physical domain, which can effectively focus on local features and reduce resource fragmentation. A global server is deployed to aggregate and share training parameters, which enhances local data privacy and significantly improves learning efficiency. Furthermore, we deploy the Deep Reinforcement Learning (DRL) model in each server to dynamically adjust and optimize the resource allocation of the multi-domain physical network. In DRL-assisted FL, HFL-VNE jointly optimizes decision-making through specific local and federated reward mechanisms and loss functions. Finally, the superiority of HFL-VNE is proved by combining simulation experiments and comparing it with related works.

preprint2022arXiv

Observation of fractal topological states in acoustic metamaterials

Topological phases of matter have been extensively investigated in solid state materials and classical wave systems with integer dimensions. However, topological states in non-integer dimensions remain largely unexplored. Fractals, being nearly the same at different scales, are one of the intriguing complex geometries with non-integer dimensions. Here, we demonstrate acoustic Sierpiński fractal topological insulators with unconventional higher-order topological phenomena via consistent theory and experiments. We discover abundant topological edge and corner states emerging in our acoustic systems due to the rich edge and corner boundaries inside the fractals. Interestingly, the numbers of the edge and corner states scale the same as the bulk states with the system size and the exponents coincide with the Hausdorff fractal dimension of the Sierpiński carpet. Furthermore, the emergent corner states exhibit unconventional spectrum and wave patterns. Our study opens a pathway toward topological states in fractal geometries.

preprint2021arXiv

The collider tests of a leptophilic scalar for the anomalous magnetic moments

We study the anomalous muon and electron magnetic moments by introducing a scalar with CP-violating Yukawa couplings to the lepton sector. By fitting these two magnetic moments with the recent experimental measurements, we find that such a leptophilic scalar in the mass range of $\mathcal{O}(10)- \mathcal{O}(1000 )\,\rm GeV$ can be a possible source for the current experimental deviations from the Standard Model (SM) predictions, with $\mathcal{O}(0.1) - \mathcal{O}(1)$ Yukawa couplings. The current electron and muon EDM constraints to the general CP-violating Yukawa couplings are discussed. We propose to search such a leptophilic scalar mediated at the future high-luminosity LHC (HL-LHC) runs, as well as the high-energy lepton colliders, including the CEPC and the muon collider. Our results show that the leptophilic scalar in the mass range of $\mathcal{O}(10)- \mathcal{O}(1000 )\,\rm GeV$ can be fully probed by the future experimental searches at the HL-LHC and the lepton colliders at their early stages.

preprint2020arXiv

Complementarity of the future $e^+ e^-$ colliders and gravitational waves in the probe of complex singlet extension to the Standard Model

In this work, we study the future probes of the complex singlet extension to the Standard Model (cxSM). This model is possible to realize a strongly first-order electroweak phase transition (SFOEWPT). The cxSM naturally provides dark matter (DM) candidate, with or without an exact $\mathbb{Z}_2$ symmetry in the scalar sector. The benchmark models which can realize the SFOEWPT are selected, and passed to the current observational constraints to the DM candidates, including the relic densities and the direct detection limits set by the latest XENON1T results. We then calculate the one-loop corrections to the SM-like Higgs boson decays and the precision electroweak parameters due to the cxSM scalar sector. We perform a global fit to the benchmark models and study the extent to which they can be probed by the future high-energy $e^+ e^-$ colliders, such as CEPC and FCC-ee. Besides, the gravitational wave (GW) signals generated by the benchmark models are also evaluated. We further find that the future GW detector, such as LISA, is complementary in probing the benchmark models that are beyond the sensitivity of the future precision tests at the $e^+ e^-$ colliders.

preprint2020arXiv

Learning-Based Joint User-AP Association and Resource Allocation in Ultra Dense Network

With the advantages of Millimeter wave in wireless communication network, the coverage radius and inter-site distance can be further reduced, the ultra dense network (UDN) becomes the mainstream of future networks. The main challenge faced by UDN is the serious inter-site interference, which needs to be carefully addressed by joint user association and resource allocation methods. In this paper, we propose a multi-agent Q-learning based method to jointly optimize the user association and resource allocation in UDN. The deep Q-network is applied to guarantee the convergence of the proposed method. Simulation results reveal the effectiveness of the proposed method and different performances under different simulation parameters are evaluated.

preprint2020arXiv

Novel Superstructure-Phase Two-Dimensional Material 1$\textit{T}$-VSe$_2$ at High Pressure

A superstructure can elicit versatile new properties of materials by breaking their original geometrical symmetries. It is an important topic in the layered graphene-like two-dimensional transition-metal dichalcogenides (TMDs), but its origin remains unclear. Using diamond-anvil cell techniques, synchrotron x-ray diffraction, x-ray absorption, and the first-principles calculations, we show that the evolution from the weak Van der Waals bonding to the Heisenberg covalent bonding between layers induces an isostructural transition in quasi-two-dimensional 1$\textit{T}$-type VSe$_2$ at high pressure. Furthermore, our results show that high-pressure induce a novel superstructure at 15.5 GPa, rather than suppress as it would normally, which is unexpected. It is driven by the Fermi surface nesting, enhanced by the pressure-induced distortion. The results suggest that the superstructure not only appears in the two-dimensional structure but also can emerge in the pressure-tuned three-dimensional structure with new symmetry and develop superconductivity.

preprint2020arXiv

Rethinking Softmax Cross-Entropy Loss for Adversarial Robustness

Previous work shows that adversarially robust generalization requires larger sample complexity, and the same dataset, e.g., CIFAR-10, which enables good standard accuracy may not suffice to train robust models. Since collecting new training data could be costly, we focus on better utilizing the given data by inducing the regions with high sample density in the feature space, which could lead to locally sufficient samples for robust learning. We first formally show that the softmax cross-entropy (SCE) loss and its variants convey inappropriate supervisory signals, which encourage the learned feature points to spread over the space sparsely in training. This inspires us to propose the Max-Mahalanobis center (MMC) loss to explicitly induce dense feature regions in order to benefit robustness. Namely, the MMC loss encourages the model to concentrate on learning ordered and compact representations, which gather around the preset optimal centers for different classes. We empirically demonstrate that applying the MMC loss can significantly improve robustness even under strong adaptive attacks, while keeping state-of-the-art accuracy on clean inputs with little extra computation compared to the SCE loss.

preprint2020arXiv

The gravitational waves from the collapsing domain walls in the complex singlet model

We study the CP domain walls and the consequent gravitational waves induced by the spontaneous breaking of the CP symmetry in the complex singlet extension to the Standard Model. We impose the constraints from the unitarity, stability and the global minimal of the vacuum solutions on the model parameter space. The CP domain wall profiles and tensions are obtained by numerically solving the relevant field equations. The explicit CP violation terms are then introduced to the potential as biased terms to make the domain walls unstable and collapse, The BBN bound on the magnitude of the energy bias is taken into account. To achieve sufficiently strong gravitational wave signals, the domain wall tension $σ$ is required to be at least $σ/{\rm TeV}^3 \sim \mathcal{O}(10^3)$. We find that the gravitational wave spectrum can be probed in the future SKA and/or DECIGO programs, when the typical mass scale is at least $\sim \mathcal{O}(10)$ TeV and the explicit CP violation terms are as small as $\mathcal{O}(10^{-29}) - \mathcal{O}(10^{-27}) $. The gravitational waves from collapsing domain walls thus provide a complementarity to the probe of extremely small CP violation at high-energy scale.

preprint2016arXiv

A hidden confining world on the 750 GeV diphoton excess

We explain the recent diphoton excesses around $750$ GeV by both ATLAS and CMS as a singlet scalar $Φ$ which couples to SM gluon and neutral gauge bosons only through higher dimensional operators. A natural explanation is that $Φ$ is a pseudo-Nambu-Goldstone boson (pNGB) which receives parity violation through anomaly if there exists a hidden strong dynamics. The singlet and other light pNGBs will decay into two SM gauge bosons and even serves as the meta-stable coloured states which can be probed in the future. By accurately measuring their relative decay and the total production rate in the future, we will learn the underlying strong dynamics parameter. The lightest baryon in this confining theory could serve as a viable dark matter candidate.

preprint2016arXiv

Degenerate Higgs bosons: hiding a second Higgs at 125 GeV

More than one Higgs boson may be present near the currently discovered Higgs mass, which can not be properly resolved due to the limitations in the intrinsic energy resolution at the Large Hadron Collider. We investigated the scenarios where two $CP$-even Higgs bosons are degenerate in mass. To correctly predict the Higgs signatures, quantum interference effects between the two Higgs bosons must be taken into account, which, however, has been often neglected in the literature. We carried out a global analysis including the interference effects for a variety of Higgs searching channels at the Large Hadron Collider, which suggests that the existence of two degenerate Higgs bosons near 125 GeV is highly likely. Prospects of distinguishing the degenerate Higgs case from the single Higgs case are discussed.

preprint2016arXiv

Higgs pair productions in the CP-violating two-Higgs-doublet model

In this work, we study the SM-like Higgs pair productions in the framework of the general CP-violating two-Higgs-doublet model. Several constraints are imposed to the model sequentially, including the SM-like Higgs boson signal fits, the precise measurements of the electric dipole moments, the perturbative unitarity and stability bounds to the Higgs potential, and the most recent LHC searches for the heavy Higgs bosons. We show how are the CP-violating mixing angles related to the Higgs cubic self couplings in this setup. Afterwards, we estimate the cross sections of the future LHC/SppC searches for the Higgs pair productions, as well as other possible decay modes for the heavy Higgs bosons.

preprint2016arXiv

LHC searches for heavy neutral Higgs bosons with a top jet substructure analysis

We study the LHC searches for the heavy $CP$-odd Higgs boson $A$ and $CP$-even Higgs boson $H$ in the context of general two-Higgs-doublet model. Specifically, we consider the decay mode of $A/H\to t \bar t $ through the $b \bar b$ or $t \bar t $ associated production channels. In the so-called "alignment limit" of the two-Higgs-doublet model, this decay mode can be the most dominant one. By employing the HEPTopTagger and the multi-variable-analysis method, we present the search sensitivities for both $CP$-odd Higgs boson $A$ and $CP$-even Higgs boson $H$ via these channels at the high-luminosity LHC runs.

preprint2015arXiv

Discriminative Nonparametric Latent Feature Relational Models with Data Augmentation

We present a discriminative nonparametric latent feature relational model (LFRM) for link prediction to automatically infer the dimensionality of latent features. Under the generic RegBayes (regularized Bayesian inference) framework, we handily incorporate the prediction loss with probabilistic inference of a Bayesian model; set distinct regularization parameters for different types of links to handle the imbalance issue in real networks; and unify the analysis of both the smooth logistic log-loss and the piecewise linear hinge loss. For the nonconjugate posterior inference, we present a simple Gibbs sampler via data augmentation, without making restricting assumptions as done in variational methods. We further develop an approximate sampler using stochastic gradient Langevin dynamics to handle large networks with hundreds of thousands of entities and millions of links, orders of magnitude larger than what existing LFRM models can process. Extensive studies on various real networks show promising performance.

preprint2015arXiv

Dropout Training for SVMs with Data Augmentation

Dropout and other feature noising schemes have shown promising results in controlling over-fitting by artificially corrupting the training data. Though extensive theoretical and empirical studies have been performed for generalized linear models, little work has been done for support vector machines (SVMs), one of the most successful approaches for supervised learning. This paper presents dropout training for both linear SVMs and the nonlinear extension with latent representation learning. For linear SVMs, to deal with the intractable expectation of the non-smooth hinge loss under corrupting distributions, we develop an iteratively re-weighted least square (IRLS) algorithm by exploring data augmentation techniques. Our algorithm iteratively minimizes the expectation of a re-weighted least square problem, where the re-weights are analytically updated. For nonlinear latent SVMs, we consider learning one layer of latent representations in SVMs and extend the data augmentation technique in conjunction with first-order Taylor-expansion to deal with the intractable expected non-smooth hinge loss and the nonlinearity of latent representations. Finally, we apply the similar data augmentation ideas to develop a new IRLS algorithm for the expected logistic loss under corrupting distributions, and we further develop a non-linear extension of logistic regression by incorporating one layer of latent representations. Our algorithms offer insights on the connection and difference between the hinge loss and logistic loss in dropout training. Empirical results on several real datasets demonstrate the effectiveness of dropout training on significantly boosting the classification accuracy of both linear and nonlinear SVMs. In addition, the nonlinear SVMs further improve the prediction performance on several image datasets.

preprint2015arXiv

The leptophilic dark matter with $Z'$ interaction: from indirect searches to future $e^+ e^-$ collider searches

We investigate the scenario where the dark matter only interacts with the charged leptons in the standard model via a neutral vector mediator $Z'$. Such a scenario with a 430 GeV dark matter can fit the recent positron fluxes observed by the AMS-02 Collaborations, with the reasonable boost factors. We study the possibility of searching such leptophilic $Z'$ via its lepton final states and invisible decay modes at the future electron-positron colliders, such as the International Linear Collider (ILC) and the Compact Linear Collider (CLIC). We find that for the benchmark models with $Z'$ mass from 1.0 TeV to 1.5 TeV, the searches for the invisible decays of $Z'\to \bar χχ$ is easily achieved at the CLIC 1.5 TeV runs via the mono-photon process. However, lighter $Z'$ with mass from 0.5 TeV to 0.8 TeV are challenging to see. The di-lepton plus single photon channel can reveal the $Z'$ mass at the ILC and CLIC with moderate luminosities.

preprint2014arXiv

3.5 keV Galactic Emission Line as a Signal from the Hidden Sector

An emission line with energy of $E\sim 3.5$ keV has been observed in galaxy clusters by two experiments. The emission line is consistent with the decay of a dark matter particle with a mass of $\sim 7$ keV. In this work we discuss the possibility that the dark particle responsible for the emission is a real scalar ($ρ$) which arises naturally in a $U(1)_X$ Stueckelberg of MSSM. In the MSSM Stueckelberg extension $ρ$ couples only to other scalars carrying a $U(1)_X$ quantum number. Under the assumption that there exists a vectorlike leptonic generation carrying both $SU(2)_L\times U(1)_Y$ and $U(1)_X$ quantum numbers, we compute the decay of the $ρ$ into two photons via a triangle loop involving scalars. The relic density of the $ρ$ arises via the decay $H^0\to h^0+ ρ$ at the loop level involving scalars, and via the annihilation processes of the vectorlike scalars into $ρ+ h^0$. It is shown that the galactic data can be explained within a multicomponent dark matter model where the 7 keV dark matter is a subdominant component constituting only $(1-10)$\% of the matter relic density with the rest being supersymmetric dark matter such as the neutralino. Thus the direct detection experiments remain viable searches for WIMPs. The fact that the dark scalar $ρ$ with no interactions with the standard model particles arises from a Stueckelberg extension of a hidden $U(1)_X$ implies that the 3.5 KeV galactic line emission is a signal from the hidden sector.

preprint2014arXiv

Bayesian Inference with Posterior Regularization and applications to Infinite Latent SVMs

Existing Bayesian models, especially nonparametric Bayesian methods, rely on specially conceived priors to incorporate domain knowledge for discovering improved latent representations. While priors can affect posterior distributions through Bayes' rule, imposing posterior regularization is arguably more direct and in some cases more natural and general. In this paper, we present regularized Bayesian inference (RegBayes), a novel computational framework that performs posterior inference with a regularization term on the desired post-data posterior distribution under an information theoretical formulation. RegBayes is more flexible than the procedure that elicits expert knowledge via priors, and it covers both directed Bayesian networks and undirected Markov networks whose Bayesian formulation results in hybrid chain graph models. When the regularization is induced from a linear operator on the posterior distributions, such as the expectation operator, we present a general convex-analysis theorem to characterize the solution of RegBayes. Furthermore, we present two concrete examples of RegBayes, infinite latent support vector machines (iLSVM) and multi-task infinite latent support vector machines (MT-iLSVM), which explore the large-margin idea in combination with a nonparametric Bayesian model for discovering predictive latent features for classification and multi-task learning, respectively. We present efficient inference methods and report empirical studies on several benchmark datasets, which appear to demonstrate the merits inherited from both large-margin learning and Bayesian nonparametrics. Such results were not available until now, and contribute to push forward the interface between these two important subfields, which have been largely treated as isolated in the community.

preprint2014arXiv

Competitive analysis via benchmark decomposition

We propose a uniform approach for the design and analysis of prior-free competitive auctions and online auctions. Our philosophy is to view the benchmark function as a variable parameter of the model and study a broad class of functions instead of a individual target benchmark. We consider a multitude of well-studied auction settings, and improve upon a few previous results. (1) Multi-unit auctions. Given a $β$-competitive unlimited supply auction, the best previously known multi-unit auction is $2β$-competitive. We design a $(1+β)$-competitive auction reducing the ratio from $4.84$ to $3.24$. These results carry over to matroid and position auctions. (2) General downward-closed environments. We design a $6.5$-competitive auction improving upon the ratio of $7.5$. Our auction is noticeably simpler than the previous best one. (3) Unlimited supply online auctions. Our analysis yields an auction with a competitive ratio of $4.12$, which significantly narrows the margin of $[4,4.84]$ previously known for this problem. A particularly important tool in our analysis is a simple decomposition lemma, which allows us to bound the competitive ratio against a sum of benchmark functions. We use this lemma in a "divide and conquer" fashion by dividing the target benchmark into the sum of simpler functions.

preprint2014arXiv

Dropout Training for Support Vector Machines

Dropout and other feature noising schemes have shown promising results in controlling over-fitting by artificially corrupting the training data. Though extensive theoretical and empirical studies have been performed for generalized linear models, little work has been done for support vector machines (SVMs), one of the most successful approaches for supervised learning. This paper presents dropout training for linear SVMs. To deal with the intractable expectation of the non-smooth hinge loss under corrupting distributions, we develop an iteratively re-weighted least square (IRLS) algorithm by exploring data augmentation techniques. Our algorithm iteratively minimizes the expectation of a re-weighted least square problem, where the re-weights have closed-form solutions. The similar ideas are applied to develop a new IRLS algorithm for the expected logistic loss under corrupting distributions. Our algorithms offer insights on the connection and difference between the hinge loss and logistic loss in dropout training. Empirical results on several real datasets demonstrate the effectiveness of dropout training on significantly boosting the classification accuracy of linear SVMs.

preprint2014arXiv

LHC searches for the CP-odd Higgs by the jet substructure analysis

The LHC searches for the CP-odd Higgs boson is studied (with masses from 300 GeV to 1 TeV) in the context of the general two-Higgs-doublet model. With the discovery of the 125 GeV Higgs boson at the LHC, we highlight one promising discovery channel of the hZ. This channel can become significant after the global signal fitting to the 125 GeV Higgs boson in the general two-Higgs-doublet model. It is particularly important in the scenario where two CP-even Higgs bosons in the two-Higgs-doublet model have the common mass of 125 GeV. Since the final states involve a Standard-Model-like Higgs boson, we apply the jet substructure analysis of the fat Higgs jet in order to eliminate the Standard Model background sufficiently. After performing the kinematic cuts, we present the LHC search sensitivities for the CP-odd Higgs boson with mass up to 1 TeV via this channel.

preprint2014arXiv

LHC Searches for The Heavy Higgs Boson via Two B Jets plus Diphoton

Extra scalar fields are common in beyond Standard Model (SM) new physics, and they may mix with the 125 GeV SM-like Higgs boson discovered at the LHC. This fact suggests possible discovery channels for these new scalar fields with their decay modes involving the 125 GeV Higgs boson. In this work, we explore the LHC search potential of the heavy CP-even Higgs boson H in the two-Higgs-doublet model. We focus on the channel of H decaying to a pair of light CP-even Higgs bosons h, with two h's decaying to two b jets and diphoton sequentially. This channel is particularly involved when the relevant cubic coupling is enhanced. We find such enhancement to be possible when taking a large CP-odd Higgs mass input for the two-Higgs-doublet model spectrum. Analogous to the SM Higgs self-coupling measurement, the two b jets plus diphoton final states are of particular interest due to the manageable SM background. After performing a cut-based analysis of both signal and background processes, we demonstrate the LHC search sensitivities for the heavy CP-even Higgs boson in a broad mass range via the two b jets plus diphoton final states.

preprint2014arXiv

On Revenue Maximization with Sharp Multi-Unit Demands

We consider markets consisting of a set of indivisible items, and buyers that have {\em sharp} multi-unit demand. This means that each buyer $i$ wants a specific number $d_i$ of items; a bundle of size less than $d_i$ has no value, while a bundle of size greater than $d_i$ is worth no more than the most valued $d_i$ items (valuations being additive). We consider the objective of setting prices and allocations in order to maximize the total revenue of the market maker. The pricing problem with sharp multi-unit demand buyers has a number of properties that the unit-demand model does not possess, and is an important question in algorithmic pricing. We consider the problem of computing a revenue maximizing solution for two solution concepts: competitive equilibrium and envy-free pricing. For unrestricted valuations, these problems are NP-complete; we focus on a realistic special case of "correlated values" where each buyer $i$ has a valuation $v_i\qual_j$ for item $j$, where $v_i$ and $\qual_j$ are positive quantities associated with buyer $i$ and item $j$ respectively. We present a polynomial time algorithm to solve the revenue-maximizing competitive equilibrium problem. For envy-free pricing, if the demand of each buyer is bounded by a constant, a revenue maximizing solution can be found efficiently; the general demand case is shown to be NP-hard.

preprint2014arXiv

Optimal Competitive Auctions

We study the design of truthful auctions for selling identical items in unlimited supply (e.g., digital goods) to n unit demand buyers. This classic problem stands out from profit-maximizing auction design literature as it requires no probabilistic assumptions on buyers' valuations and employs the framework of competitive analysis. Our objective is to optimize the worst-case performance of an auction, measured by the ratio between a given benchmark and revenue generated by the auction. We establish a sufficient and necessary condition that characterizes competitive ratios for all monotone benchmarks. The characterization identifies the worst-case distribution of instances and reveals intrinsic relations between competitive ratios and benchmarks in the competitive analysis. With the characterization at hand, we show optimal competitive auctions for two natural benchmarks. The most well-studied benchmark $\mathcal{F}^{(2)}(\cdot)$ measures the envy-free optimal revenue where at least two buyers win. Goldberg et al. [13] showed a sequence of lower bounds on the competitive ratio for each number of buyers n. They conjectured that all these bounds are tight. We show that optimal competitive auctions match these bounds. Thus, we confirm the conjecture and settle a central open problem in the design of digital goods auctions. As one more application we examine another economically meaningful benchmark, which measures the optimal revenue across all limited-supply Vickrey auctions. We identify the optimal competitive ratios to be $(\frac{n}{n-1})^{n-1}-1$ for each number of buyers n, that is $e-1$ as $n$ approaches infinity.

preprint2014arXiv

Study of the material photon and electron background and the liquid argon detector veto efficiency of the CDEX-10 experiment

The China Dark Matter Experiment (CDEX) is located at the China Jinping underground laboratory (CJPL) and aims to directly detect the WIMP flux with high sensitivity in the low mass region. Here we present a study of the predicted photon and electron backgrounds including the background contribution of the structure materials of the germanium detector, the passive shielding materials, and the intrinsic radioactivity of the liquid argon that serves as an anti-Compton active shielding detector. A detailed geometry is modeled and the background contribution has been simulated based on the measured radioactivities of all possible components within the GEANT4 program. Then the photon and electron background level in the energy region of interest (<10^-2 events kg-1 day-1 keV-1 (cpkkd)) is predicted based on Monte Carlo simulations. The simulated result is consistent with the design goal of CDEX-10 experiment, 0.1 cpkkd, which shows that the active and passive shield design of CDEX-10 is effective and feasible.

preprint2013arXiv

Discriminative Relational Topic Models

Many scientific and engineering fields involve analyzing network data. For document networks, relational topic models (RTMs) provide a probabilistic generative process to describe both the link structure and document contents, and they have shown promise on predicting network structures and discovering latent topic representations. However, existing RTMs have limitations in both the restricted model expressiveness and incapability of dealing with imbalanced network data. To expand the scope and improve the inference accuracy of RTMs, this paper presents three extensions: 1) unlike the common link likelihood with a diagonal weight matrix that allows the-same-topic interactions only, we generalize it to use a full weight matrix that captures all pairwise topic interactions and is applicable to asymmetric networks; 2) instead of doing standard Bayesian inference, we perform regularized Bayesian inference (RegBayes) with a regularization parameter to deal with the imbalanced link structure issue in common real networks and improve the discriminative ability of learned latent representations; and 3) instead of doing variational approximation with strict mean-field assumptions, we present collapsed Gibbs sampling algorithms for the generalized relational topic models by exploring data augmentation without making restricting assumptions. Under the generic RegBayes framework, we carefully investigate two popular discriminative loss functions, namely, the logistic log-loss and the max-margin hinge loss. Experimental results on several real network datasets demonstrate the significance of these extensions on improving the prediction performance, and the time efficiency can be dramatically improved with a simple fast approximation method.

preprint2013arXiv

Gibbs Max-margin Topic Models with Data Augmentation

Max-margin learning is a powerful approach to building classifiers and structured output predictors. Recent work on max-margin supervised topic models has successfully integrated it with Bayesian topic models to discover discriminative latent semantic structures and make accurate predictions for unseen testing data. However, the resulting learning problems are usually hard to solve because of the non-smoothness of the margin loss. Existing approaches to building max-margin supervised topic models rely on an iterative procedure to solve multiple latent SVM subproblems with additional mean-field assumptions on the desired posterior distributions. This paper presents an alternative approach by defining a new max-margin loss. Namely, we present Gibbs max-margin supervised topic models, a latent variable Gibbs classifier to discover hidden topic representations for various tasks, including classification, regression and multi-task learning. Gibbs max-margin supervised topic models minimize an expected margin loss, which is an upper bound of the existing margin loss derived from an expected prediction rule. By introducing augmented variables and integrating out the Dirichlet variables analytically by conjugacy, we develop simple Gibbs sampling algorithms with no restricting assumptions and no need to solve SVM subproblems. Furthermore, each step of the &#34;augment-and-collapse&#34; Gibbs sampling algorithms has an analytical conditional distribution, from which samples can be easily drawn. Experimental results demonstrate significant improvements on time efficiency. The classification performance is also significantly improved over competitors on binary, multi-class and multi-label classification tasks.

preprint2013arXiv

Introduction of the CDEX experiment

Weakly Interacting Massive Particles (WIMPs) are the candidates of dark matter in our universe. Up to now any direct interaction of WIMP with nuclei has not been observed yet. The exclusion limits of the spin-independent cross section of WIMP-nucleon which have been experimentally obtained is about 10^{-7}pb at high mass region and only 10^{-5}pb} at low mass region. China Jin-Ping underground laboratory CJPL is the deepest underground lab in the world and provides a very promising environment for direct observation of dark matter. The China Dark Matter Experiment (CDEX) experiment is going to directly detect the WIMP flux with high sensitivity in the low mass region. Both CJPL and CDEX have achieved a remarkable progress in recent two years. The CDEX employs a point-contact germanium semi-conductor detector PCGe whose detection threshold is less than 300 eV. We report the measurement results of Muon flux, monitoring of radioactivity and Radon concentration carried out in CJPL, as well describe the structure and performance of the 1 kg PCGe detector CDEX-1 and 10kg detector array CDEX-10 including the detectors, electronics, shielding and cooling systems. Finally we discuss the physics goals of the CDEX-1, CDEX-10 and the future CDEX-1T detectors.

preprint2013arXiv

Mining Crash Fix Patterns

During the life cycle of software development, developers have to fix different kinds of bugs reported by testers or end users. The efficiency and effectiveness of fixing bugs have a huge impact on the reliability of the software as well as the productivity of the development team. Software companies usually spend a large amount of money and human resources on the testing and bug fixing departments. As a result, a better and more reliable way to fix bugs is highly desired by them. In order to achieve such goal, in depth studies on the characteristics of bug fixes from well maintained, highly popular software projects are necessary. In this paper, we study the bug fixing histories extracted from the Eclipse project, a well maintained, highly popular open source project. After analyzing more than 36,000 bugs that belongs to three major kinds of exception types, we are able to reveal some common fix types that are frequently used to fix certain kinds of program exceptions. Our analysis shows that almost all of the exceptions that belong to a certain exception can be fixed by less than ten fix types. Our result implies that most of the bugs in software projects can be and should be fixed by only a few common fix patterns.

preprint2013arXiv

On the Complexity of Trial and Error

Motivated by certain applications from physics, biochemistry, economics, and computer science, in which the objects under investigation are not accessible because of various limitations, we propose a trial-and-error model to examine algorithmic issues in such situations. Given a search problem with a hidden input, we are asked to find a valid solution, to find which we can propose candidate solutions (trials), and use observed violations (errors), to prepare future proposals. In accordance with our motivating applications, we consider the fairly broad class of constraint satisfaction problems, and assume that errors are signaled by a verification oracle in the format of the index of a violated constraint (with the content of the constraint still hidden). Our discoveries are summarized as follows. On one hand, despite the seemingly very little information provided by the verification oracle, efficient algorithms do exist for a number of important problems. For the Nash, Core, Stable Matching, and SAT problems, the unknown-input versions are as hard as the corresponding known-input versions, up to a factor of polynomial. We further give almost tight bounds on the latter two problems&#39; trial complexities. On the other hand, there are problems whose complexities are substantially increased in the unknown-input model. In particular, no time-efficient algorithms exist (under standard hardness assumptions) for Graph Isomorphism and Group Isomorphism problems. The tools used to achieve these results include order theory, strong ellipsoid method, and some non-standard reductions. Our model investigates the value of information, and our results demonstrate that the lack of input information can introduce various levels of extra difficulty. The model exhibits intimate connections with (and we hope can also serve as a useful supplement to) certain existing learning and complexity theories.

preprint2013arXiv

Probing LHC Higgs Signals from Extended Electroweak Gauge Group

We study the effects of the extended electroweak gauge sector on the signal strengths of the Higgs boson at the LHC. Extension of the Higgs sector associate with the extension of the electroweak gauge symmetry. In our setup, there are two neutral Higgs states ($h$, $H$) and three new gauge bosons ($W&#39;^{\pm}$, $Z&#39;$). We assume the lightest scalar, $h$, is what LHC found and its mass is 125 GeV. We find the enhancement of $μ(gg \to h \to γγ)$. On the other hand, other decay processes are same as or smaller than the SM expectation.

preprint2013arXiv

Solving Linear Programming with Constraints Unknown

What is the value of input information in solving linear programming? The celebrated ellipsoid algorithm tells us that the full information of input constraints is not necessary; the algorithm works as long as there exists an oracle that, on a proposed candidate solution, returns a violation in the format of a separating hyperplane. Can linear programming still be efficiently solved if the returned violation is in other formats? We study this question in a trial-and-error framework: there is an oracle that, upon a proposed solution, returns the index of a violated constraint (with the content of the constraint still hidden). When more than one constraint is violated, two variants in the model are investigated. (1) The oracle returns the index of a &#34;most violated&#34; constraint, measured by the Euclidean distance of the proposed solution and the half-spaces defined by the constraints. In this case, the LP can be efficiently solved. (2) The oracle returns the index of an arbitrary (i.e., worst-case) violated constraint. In this case, we give an algorithm with running time exponential in the number of variables. We then show that the exponential dependence on n is unfortunately necessary even for the query complexity. These results put together shed light on the amount of information that one needs in order to solve a linear program efficiently. The proofs of the results employ a variety of geometric techniques, including McMullen&#39;s Upper Bound Theorem, the weighted spherical Voronoi diagram, and the furthest Voronoi diagram. In addition, we give an alternative proof to a conjecture of László Fejes Tóth on bounding the number of disconnected components formed by the union of m convex bodies in R^n. Our proof, inspired by the Gauss-Bonnet Theorem in global differential geometry, is independent of the known and reveals more clear insights into the problem and the bound.

preprint2013arXiv

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.

preprint2012arXiv

Budget Feasible Mechanism Design via Random Sampling

Budget feasible mechanism considers algorithmic mechanism design questions where there is a budget constraint on the total payment of the mechanism. An important question in the field is that under which valuation domains there exist budget feasible mechanisms that admit `small&#39; approximations (compared to a socially optimal solution). Singer \cite{PS10} showed that additive and submodular functions admit a constant approximation mechanism. Recently, Dobzinski, Papadimitriou, and Singer \cite{DPS11} gave an $O(\log^2n)$ approximation mechanism for subadditive functions and remarked that: &#34;A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive function.&#34; In this paper, we give the first attempt to this question. We give a polynomial time $O(\frac{\log n}{\log\log n})$ sub-logarithmic approximation ratio mechanism for subadditive functions, improving the best known ratio $O(\log^2 n)$. Further, we connect budget feasible mechanism design to the concept of approximate core in cooperative game theory, and show that there is a mechanism for subadditive functions whose approximation is, via a characterization of the integrality gap of a linear program, linear to the largest value to which an approximate core exists. Our result implies in particular that the class of XOS functions, which is a superclass of submodular functions, admits a constant approximation mechanism. We believe that our work could be a solid step towards solving the above fundamental problem eventually, and possibly, with an affirmative answer.

preprint2012arXiv

Budget Feasible Mechanism Design: From Prior-Free to Bayesian

Budget feasible mechanism design studies procurement combinatorial auctions where the sellers have private costs to produce items, and the buyer(auctioneer) aims to maximize a social valuation function on subsets of items, under the budget constraint on the total payment. One of the most important questions in the field is &#34;which valuation domains admit truthful budget feasible mechanisms with `small&#39; approximations (compared to the social optimum)?&#34; Singer showed that additive and submodular functions have such constant approximations. Recently, Dobzinski, Papadimitriou, and Singer gave an O(log^2 n)-approximation mechanism for subadditive functions; they also remarked that: &#34;A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions.&#34; We address this question from two viewpoints: prior-free worst case analysis and Bayesian analysis. For the prior-free framework, we use an LP that describes the fractional cover of the valuation function; it is also connected to the concept of approximate core in cooperative game theory. We provide an O(I)-approximation mechanism for subadditive functions, via the worst case integrality gap I of LP. This implies an O(log n)-approximation for subadditive valuations, O(1)-approximation for XOS valuations, and for valuations with a constant I. XOS valuations are an important class of functions that lie between submodular and subadditive classes. We give another polynomial time O(log n/loglog n) sub-logarithmic approximation mechanism for subadditive valuations. For the Bayesian framework, we provide a constant approximation mechanism for all subadditive functions, using the above prior-free mechanism for XOS valuations as a subroutine. Our mechanism allows correlations in the distribution of private information and is universally truthful.

preprint2012arXiv

LHC Higgs Signatures from Extended Electroweak Gauge Symmetry

We study LHC Higgs signatures from the extended electroweak gauge symmetry SU(2) x SU(2) x U(1). Under this gauge structure, we present an effective UV completion of the 3-site moose model with ideal fermion delocalization, which contains two neutral Higgs states (h, H) and three new gauge bosons (W&#39;, Z&#39;). We study the unitarity, and reveal that the exact E^2 cancellation in the longitudinal WW scattering amplitudes is achieved by the joint role of exchanging both spin-1 new gauge bosons and spin-0 Higgs bosons. We identify the lighter Higgs state h with mass 125GeV, and derive the unitarity bound on the mass of heavier Higgs boson H. The parameter space of this model is highly predictive. We study the production and decay signals of this 125GeV Higgs boson h at the LHC. We demonstrate that the h Higgs boson can naturally have enhanced signals in the diphoton channel $gg \to h \toγγ$, while the events rates in the reactions $gg \to h \to WW^*$ and $gg \to h \to ZZ^*$ are generally suppressed relative to the SM expectation. Searching the h Higgs boson via associated productions and vector boson fusions are also discussed for our model. We further analyze the LHC signals of the heavier Higgs boson H as a distinctive new physics discriminator from the SM. For wide mass-ranges of H, we derive constraints from the existing LHC searches, and study the discovery potential of H at the LHC(8TeV) and LHC(14TeV).

preprint2012arXiv

LHC Signatures of Two-Higgs-Doublets with Fourth Family

On-going Higgs searches in the light mass window are of vital importance for testing the Higgs mechanism and probing new physics beyond the standard model (SM). The latest ATLAS and CMS searches for the SM Higgs boson at the LHC (7TeV) found some intriguing excesses of events in the γγ/VV^* channels (V=Z,W) around the mass-range of 124-126 GeV. We explore a possible explanation of the γγand VV^* signals from the light CP-odd Higgs A^0 or CP-even Higgs h^0 from the general two-Higgs-doublet model with fourth-family fermions. We demonstrate that by including invisible decays of the Higgs boson A^0 or h^0 to fourth-family neutrinos, the predicted γγand VV^* signals can explain the observed new signatures at the LHC, and will be further probed by the forthcoming LHC runs in 2012.

preprint2011arXiv

Dynamics of Profit-Sharing Games

An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study the dynamics of coalition formation under bounded rationality. We consider settings where each team&#39;s profit is given by a convex function, and propose three profit-sharing schemes, each of which is based on the concept of marginal utility. The agents are assumed to be myopic, i.e., they keep changing teams as long as they can increase their payoff by doing so. We study the properties (such as closeness to Nash equilibrium or total profit) of the states that result after a polynomial number of such moves, and prove bounds on the price of anarchy and the price of stability of the corresponding games.

preprint2011arXiv

Higgsino dark matter model consistent with galactic cosmic ray data and possibility of discovery at LHC-7

A solution to the PAMELA positron excess with Higgsino dark matter within extended supergravity grand unified (SUGRA) models is proposed. The models are compliant with the photon constraints recently set by Fermi-LAT and produce positron as well as antiproton fluxes consistent with the PAMELA experiment. The SUGRA models considered have an extended hidden sector with extra degrees of freedom which allow for a satisfaction of relic density consistent with WMAP. The Higgsino models are also consistent with the CDMS-II and XENON100 data and are discoverable at LHC-7 with 1 fb^(-1) of luminosity. The models are testable on several fronts.

preprint2011arXiv

Interpreting the First CMS and ATLAS SUSY Results

The CMS and the ATLAS Collaborations have recently reported on the search for supersymmetry with 35 pb$^{-1}$ of data and have put independent limits on the parameter space of the supergravity unified model with universal boundary conditions at the GUT scale for soft breaking, i.e., the mSUGRA model. We extend this study by examining other regions of the mSUGRA parameter space in $A_0$ and $\tanβ$. Further, we contrast the reach of CMS and ATLAS with 35 pb$^{-1}$ of data with the indirect constraints, i.e., the constraints from the Higgs boson mass limits, from flavor physics and from the dark matter limits from WMAP. Specifically it is found that a significant part of the parameter space excluded by CMS and ATLAS is essentially already excluded by the indirect constraints and the fertile region of parameter space has yet to be explored. We also emphasize that gluino masses as low as 400 GeV but for squark masses much larger than the gluino mass remain unconstrained and further that much of the hyperbolic branch of radiative electroweak symmetry breaking, with low values of the Higgs mixing parameter $μ$, is essentially untouched by the recent LHC analysis.

preprint2011arXiv

Low Mass Gluino within the Sparticle Landscape, Implications for Dark Matter, and Early Discovery Prospects at LHC-7

We analyze supergravity models that predict a low mass gluino within the landscape of sparticle mass hierarchies. The analysis includes a broad class of models that arise in minimal and in non-minimal supergravity unified frameworks and in extended models with additional $U(1)^n_X$ hidden sector gauge symmetries. Gluino masses in the range $(350-700)$ GeV are investigated. Masses in this range are promising for early discovery at the LHC at $\sqrt s =7$ TeV (LHC-7). The models exhibit a wide dispersion in the gaugino-Higgsino eigencontent of their LSPs and in their associated sparticle mass spectra. A signature analysis is carried out and the prominent discovery channels for the models are identified with most models needing only $\sim 1 \rm fb^{-1}$ for discovery at LHC-7. In addition, significant variations in the discovery capability of the low mass gluino models are observed for models in which the gluino masses are of comparable size due to the mass splittings in different models and the relative position of the light gluino within the various sparticle mass hierarchies. The models are consistent with the current stringent bounds from the Fermi-LAT, CDMS-II, XENON100, and EDELWEISS-2 experiments. A subclass of these models, which include a mixed-wino LSP and a Higgsino LSP, are also shown to accommodate the positron excess seen in the PAMELA satellite experiment.

preprint2011arXiv

Mechanism Design without Money via Stable Matching

Mechanism design without money has a rich history in social choice literature. Due to the strong impossibility theorem by Gibbard and Satterthwaite, exploring domains in which there exist dominant strategy mechanisms is one of the central questions in the field. We propose a general framework, called the generalized packing problem (\gpp), to study the mechanism design questions without payment. The \gpp\ possesses a rich structure and comprises a number of well-studied models as special cases, including, e.g., matroid, matching, knapsack, independent set, and the generalized assignment problem. We adopt the agenda of approximate mechanism design where the objective is to design a truthful (or strategyproof) mechanism without money that can be implemented in polynomial time and yields a good approximation to the socially optimal solution. We study several special cases of \gpp, and give constant approximation mechanisms for matroid, matching, knapsack, and the generalized assignment problem. Our result for generalized assignment problem solves an open problem proposed in \cite{DG10}. Our main technical contribution is in exploitation of the approaches from stable matching, which is a fundamental solution concept in the context of matching marketplaces, in application to mechanism design. Stable matching, while conceptually simple, provides a set of powerful tools to manage and analyze self-interested behaviors of participating agents. Our mechanism uses a stable matching algorithm as a critical component and adopts other approaches like random sampling and online mechanisms. Our work also enriches the stable matching theory with a new knapsack constrained matching model.

preprint2011arXiv

On Nash Dynamics of Matching Market Equilibria

In this paper, we study the Nash dynamics of strategic interplays of n buyers in a matching market setup by a seller, the market maker. Taking the standard market equilibrium approach, upon receiving submitted bid vectors from the buyers, the market maker will decide on a price vector to clear the market in such a way that each buyer is allocated an item for which he desires the most (a.k.a., a market equilibrium solution). While such equilibrium outcomes are not unique, the market maker chooses one (maxeq) that optimizes its own objective --- revenue maximization. The buyers in turn change bids to their best interests in order to obtain higher utilities in the next round&#39;s market equilibrium solution. This is an (n+1)-person game where buyers place strategic bids to gain the most from the market maker&#39;s equilibrium mechanism. The incentives of buyers in deciding their bids and the market maker&#39;s choice of using the maxeq mechanism create a wave of Nash dynamics involved in the market. We characterize Nash equilibria in the dynamics in terms of the relationship between maxeq and mineq (i.e., minimum revenue equilibrium), and develop convergence results for Nash dynamics from the maxeq policy to a mineq solution, resulting an outcome equivalent to the truthful VCG mechanism. Our results imply revenue equivalence between maxeq and mineq, and address the question that why short-term revenue maximization is a poor long run strategy, in a deterministic and dynamic setting.

preprint2010arXiv

Competitive Equilibria in Matching Markets with Budgets

We study competitive equilibria in the classic Shapley-Shubik assignment model with indivisible goods and unit-demand buyers, with budget constraints: buyers can specify a maximum price they are willing to pay for each item, beyond which they cannot afford the item. This single discontinuity introduced by the budget constraint fundamentally changes the properties of equilibria: in the assignment model without budget constraints, a competitive equilibrium always exists, and corresponds exactly to a stable matching. With budgets, a competitive equilibrium need not always exist. In addition, there are now two distinct notions of stability, depending on whether both or only one of the buyer and seller can strictly benefit in a blocking pair, that no longer coincide due to the budget-induced discontinuity. We define weak and strong stability for the assignment model with transferable utilities, and show that competitive equilibria correspond exactly to strongly stable matchings. We consider the algorithmic question of efficiently computing competitive equilibria in an extension of the assignment model with budgets, where each buyer specifies his preferences over items using utility functions $u_{ij}$, where $u_{ij}(p_j)$ is the utility of buyer $i$ for item $j$ when its price is $p_j$. Our main result is a strongly polynomial time algorithm that decides whether or not a competitive equilibrium exists and if yes, computes a minimum one, for a general class of utility functions $u_{ij}$. This class of utility functions includes the standard quasi-linear utility model with a budget constraint, and in addition, allows modeling marketplaces where, for example, buyers only have a preference ranking amongst items subject to a maximum payment limit for each item, or where buyers want to optimize return on investment (ROI) instead of a quasi-linear utility and only know items&#39; relative values.

preprint2010arXiv

Frugal Mechanism Design via Spectral Techniques

We study the design of truthful mechanisms for set systems, i.e., scenarios where a customer needs to hire a team of agents to perform a complex task. In this setting, frugality [Archer&Tardos&#39;02] provides a measure to evaluate the &#34;cost of truthfulness&#34;, that is, the overpayment of a truthful mechanism relative to the &#34;fair&#34; payment. We propose a uniform scheme for designing frugal truthful mechanisms for general set systems. Our scheme is based on scaling the agents&#39; bids using the eigenvector of a matrix that encodes the interdependencies between the agents. We demonstrate that the r-out-of-k-system mechanism and the \sqrt-mechanism for buying a path in a graph [Karlin et. al&#39;05] can be viewed as instantiations of our scheme. We then apply our scheme to two other classes of set systems, namely, vertex cover systems and k-path systems, in which a customer needs to purchase k edge-disjoint source-sink paths. For both settings, we bound the frugality of our mechanism in terms of the largest eigenvalue of the respective interdependency matrix. We show that our mechanism is optimal for a large subclass of vertex cover systems satisfying a simple local sparsity condition. For k-path systems, while our mechanism is within a factor of k + 1 from optimal, we show that it is, in fact, optimal, when one uses a modified definition of frugality proposed in [Elkind et al.&#39;07]. Our lower bound argument combines spectral techniques and Young&#39;s inequality, and is applicable to all set systems. As both r-out-of-k systems and single path systems can be viewed as special cases of k-path systems, our result improves the lower bounds of [Karlin et al.&#39;05] and answers several open questions proposed in that paper.

preprint2010arXiv

On the Approximability of Budget Feasible Mechanisms

Budget feasible mechanisms, recently initiated by Singer (FOCS 2010), extend algorithmic mechanism design problems to a realistic setting with a budget constraint. We consider the problem of designing truthful budget feasible mechanisms for general submodular functions: we give a randomized mechanism with approximation ratio $7.91$ (improving the previous best-known result 112), and a deterministic mechanism with approximation ratio $8.34$. Further we study the knapsack problem, which is special submodular function, give a $2+\sqrt{2}$ approximation deterministic mechanism (improving the previous best-known result 6), and a 3 approximation randomized mechanism. We provide a similar result for an extended knapsack problem with heterogeneous items, where items are divided into groups and one can pick at most one item from each group. Finally we show a lower bound of approximation ratio of $1+\sqrt{2}$ for deterministic mechanisms and 2 for randomized mechanisms for knapsack, as well as the general submodular functions. Our lower bounds are unconditional, which do not rely on any computational or complexity assumptions.

preprint2010arXiv

Patterns of Dynamical Gauge Symmetry Breaking

We construct and analyze theories with a gauge symmetry in the ultraviolet of the form $G \otimes G_b$, in which the vectorial, asymptotically free $G_b$ gauge interaction becomes strongly coupled at a scale where the $G$ interaction is weakly coupled and produces bilinear fermion condensates that dynamically break the $G$ symmetry. Comparisons are given between Higgs and dynamical symmetry breaking mechanisms for various models.

preprint2010arXiv

Prime Factor Cyclotomic Fourier Transforms with Reduced Complexity over Finite Fields

Discrete Fourier transforms~(DFTs) over finite fields have widespread applications in error correction coding. Hence, reducing the computational complexities of DFTs is of great significance, especially for long DFTs as increasingly longer error control codes are chosen for digital communication and storage systems. Since DFTs involve both multiplications and additions over finite fields and multiplications are much more complex than additions, recently proposed cyclotomic fast Fourier transforms (CFFTs) are promising due to their low multiplicative complexity. Unfortunately, they have very high additive complexity. Techniques such as common subexpression elimination (CSE) can be used to reduce the additive complexity of CFFTs, but their effectiveness for long DFTs is limited by their complexity. In this paper, we propose prime factor cyclotomic Fourier transforms (PFCFTs), which use CFFTs as sub-DFTs via the prime factor algorithm. When the length of DFTs is prime, our PFCFTs reduce to CFFTs. When the length has co-prime factors, since the sub-DFTs have much shorter lengths, this allows us to use CSE to significantly reduce their additive complexity. In comparison to previously proposed fast Fourier transforms, our PFCFTs achieve reduced overall complexity when the length of DFTs is at least 255, and the improvement significantly increases as the length grows. This approach also enables us to propose efficient DFTs with very long length (e.g., 4095-point), first efficient DFTs of such lengths in the literature. Finally, our PFCFTs are also advantageous for hardware implementation due to their regular structure.

preprint2010arXiv

SUSY and Higgs Signatures Implied by Cancellations in $b\to sγ$

Recent re-evaluations of the Standard Model (SM) contribution to ${\mathcal Br(b\to sγ)$ hint at a positive correction from new physics. Since a charged Higgs boson exchange always gives a positive contribution to this branching ratio, the constraint points to the possibility of a relatively light charged Higgs. It is found that under the HFAG constraints and with re-evaluated SM results large cancellations between the charged Higgs and the chargino contributions in supersymmetric models occur. Such cancellations then correlate the charged Higgs and the chargino masses often implying both are light. Inclusion of the more recent evaluation of $g_μ-2$ is also considered. The combined constraints imply the existence of several light sparticles. Signatures arising from these light sparticles are investigated and the analysis indicates the possibility of their early discovery at the LHC in a significant part of the parameter space. We also show that for certain restricted regions of the parameter space, such as for very large $\tanβ$ under the $1σ$ HFAG constraints, the signatures from Higgs production supersede those from sparticle production and may become the primary signatures for the discovery of supersymmetry.