Browsing Faculty/ Researcher Works by Genre "Preprint"
Now showing items 120 of 101

3coloring in time script O sign(1.3289<sup>n</sup>)We consider worst case time bounds for several NPcomplete problems, based on a constraint satisfaction (CSP) formulation of these problems: (a,b)CSP instances consist of a set of variables, each with up to a possible values, and constraints disallowing certain btuples of variable values; a problem is solved by assigning values to all variables satisfying all constraints, or by showing that no such assignment exist. 3SAT is equivalent to (2,3)CSP while 3coloring and various related problems are special cases of (3,2)CSP; there is also a natural duality transformation from (a,b)CSP to (b,a)CSP. We show that nvariable (3,2)CSP instances can be solved in time O(1.3645n), that satisfying assignments to (d,2)CSP instances can be found in randomized expected time O((0.4518d)n); that 3coloring of nvertex graphs can be solved in time O(1.3289n); that 3listcoloring of nvertex graphs can be solved in time O(1.3645n); that 3edgecoloring of nvertex graphs can be solved in time O(2n/2), and that 3satisfiability of a formula with t 3clauses can be solved in time O(nO(1)+1.3645t). © 2004 Elsevier Inc. All rights reserved.

A cantor set with hyperbolic complementWe construct a Cantor set in S3 whose complement admits a complete hyperbolic metric. © 2013 American Mathematical Society.

A comparative study of limiting strategies in discontinuous Galerkin schemes for the M<inf>1</inf> model of radiation transport© 2018 Elsevier B.V. The M1 minimum entropy moment system is a system of hyperbolic balance laws that approximates the radiation transport equation, and has many desirable properties. Among them are symmetric hyperbolicity, entropy decay, moment realizability, and correct behavior in the diffusion and freestreaming limits. However, numerical difficulties arise when approximating the solution of the M1 model by high order numerical schemes; namely maintaining the realizability of the numerical solution and controlling spurious oscillations. In this paper, we extend a previously constructed onedimensional realizability limiting strategy to 2D. In addition, we perform a numerical study of various combinations of the realizability limiter and the TVBM local slope limiter on a third order Discontinuous Galerkin (DG) scheme on both triangular and rectangular meshes. In several test cases, we demonstrate that in general, a combination of the realizability limiter and a TVBM limiter is necessary to obtain a robust and accurate numerical scheme. Our code is published so that all results can be reproduced by the reader.

A complex dynamic systems perspective on identity and its development: The dynamic systems model of role identityCurrent prominent models of identity face challenges in bridging across divergent perspectives and apparent dichotomies such as personal or socialcollective, conscious or unconscious, and epigenetic or discursiverelational, and affording pursuit of research questions that allows integrative answers. This article presents a coherent theoretical perspective on the integrative nature of identity and its developmental mechanisms. Adopting the contextual social role as a primary unit of analysis, the Dynamic Systems Model of Role Identity (DSMRI) conceptualizes role identity as a Complex Dynamic System (CDS) anchored in action that comprises the actor’s ontological and epistemological beliefs, purpose and goals, selfperceptions and selfdefinitions, and perceived action possibilities in the role. These system components are conceptualized as interdependent, and identity development is viewed as emergent, continuous, nonlinear, contextualized, and given to influences from within and without the system. The role identity itself constitutes an element within a multilevel hierarchy, which at the unit of analysis of the individual reflects a CDS of the multiple roles that constitute the person’s psychosocial identity. Identity development involves the formation and restructuring of relations within and among role identities through intra and interpersonal processes that are mediated by sociocognitive and cultural means, and framed by the context as well as by implicit dispositions. The DSMRI provides a framework to conceptualize and investigate the nature of the identity system, its development, and the relationship between identity development and psychological functioning at different units ofanalysis, across different developmental stages and contexts, and using quantitative and qualitative methodologies.

A Computation Offloading Incentive Mechanism with Delay and Cost Constraints under 5G SatelliteGround IoV Architecture© 20022012 IEEE. The 5G Internet of Vehicles has become a new paradigm alongside the growing popularity and variety of computationintensive applications with high requirements for computational resources and analysis capabilities. Existing network architectures and resource management mechanisms may not sufficiently guarantee satisfactory Quality of Experience and network efficiency, mainly suffering from the coverage limitation of road side units, unsatisfactory computational resources and capabilities of onboard equipment, frequently changing network topologies, and ineffective resource management schemes. To meet the demands of such applications, in this article we first establish a novel architecture by integrating the satellite network with the 5G cloudenabled Internet of Vehicles to efficiently support seamless coverage and efficient resource management. An incentive mechanism based joint optimization problem of opportunistic computation offloading under delay and cost constraints is formulated under the proposed 5G integrated satelliteground framework, where a vehicular user can either be a service requestor allowed to offload workload to nearby vehicles via vehicletovehicle channels while effectively controlling the cost, or a service provider who provides computing services while protecting profits. As the optimization problem is nonconvex and NPhard, simulated annealing based on the Markov Chain Monte Carlo as well as the metropolis algorithm is applied which can efficaciously obtain both highquality and costeffective approximations of global optimal solutions. The effectiveness of the proposed mechanism is corroborated through simulation results.

A dense hierarchy of sublinear time approximation schemes for bin packingThe bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes a 1,..., a n in (0,1]. Using uniform sampling, which selects a random element from the input list each time, we develop a randomized (Formula Presented) time (1 + ε) approximation scheme for the bin packing problem. We show that every randomized algorithm with uniform random sampling needs (Formula Presented) time to give an (1 + ε)approximation. For each function s(n): N → N, define Σ(s(n)) to be the set of all bin packing problems with the sum of item sizes equal to s(n). We show that Σ(n b) is NPhard for every b ∈ (0,1]. This implies a dense sublinear time hierarchy of approximation schemes for a class of NPhard problems, which are derived from the bin packing problem. We also show a randomized streaming approximation scheme for the bin packing problem such that it needs only constant updating time and constant space, and outputs an (1 + ε)approximation in time. Let S(δ)bin packing be the class of bin packing problems with each input item of size at least δ. This research also gives a natural example of NPhard problem (S(δ)bin packing) that has a constant time approximation scheme, and a constant time and space sliding window streaming approximation scheme, where δ is a positive constant. © 2012 SpringerVerlag.

A direct computation of the cohomology of the braces operad© 2017 by De Gruyter. We give a selfcontained and purely combinatorial proof of the wellknown fact that the cohomology of the braces operad is the operad Ger governing Gerstenhaber algebras.

A formality theorem for Hochschild chainsWe prove Tsygan's formality conjecture for Hochschild chains of the algebra of functions on an arbitrary smooth manifold M using the Fedosov resolutions proposed in math.QA/0307212 and the formality quasiisomorphism for Hochschild chains of ℝ[[y1,..., yd]] proposed in paper math.QA/0010321 by Shoikhet. This result allows us to describe traces on the quantum algebra of functions on an arbitrary Poisson manifold. © 2004 Elsevier Inc. All rights reserved.

A gradientaugmented level set method with an optimally local, coherent advection schemeThe level set approach represents surfaces implicitly, and advects them by evolving a level set function, which is numerically defined on an Eulerian grid. Here we present an approach that augments the level set function values by gradient information, and evolves both quantities in a fully coupled fashion. This maintains the coherence between function values and derivatives, while exploiting the extra information carried by the derivatives. The method is of comparable quality to WENO schemes, but with optimally local stencils (performing updates in time by using information from only a single adjacent grid cell). In addition, structures smaller than the grid size can be located and tracked, and the extra derivative information can be employed to obtain simple and accurate approximations to the curvature. We analyze the accuracy and the stability of the new scheme, and perform benchmark tests. © 2010 Elsevier Inc. All rights reserved.

A high phasespacedensity gas of polar moleculesA quantum gas of ultracold polar molecules, with longrange and anisotropic interactions, not only would enable explorations of a large class of manybody physics phenomena but also could be used for quantum information processing. We report on the creation of an ultracold dense gas of potassiumrubidium ( 40K87Rb) polar molecules. Using a single step of STIRAP (stimulated Raman adiabatic passage) with twofrequency laser irradiation, we coherently transfer extremely weakly bound KRb molecules to the rovibrational ground state of either the triplet or the singlet electronic ground molecular potential. The polar molecular gas has a peak density of 1012 per cubic centimeter and an expansiondetermined translational temperature of 350 nanokelvin. The polar molecules have a permanent electric dipole moment, which we measure with Stark spectroscopy to be 0.052(2) Debye (1 Debye = 3.336 × 1030 coulombmeters) for the triplet rovibrational ground state and 0.566(17) Debye for the singlet rovibrational ground state.

A highperformance virtual machine filesystem monitor in cloudassisted cognitive IoT© 2018 Elsevier B.V. Cloudassisted Cognitive Internet of Things has powerful data analytics abilities based on the computing and data storage capabilities of cloud virtual machines, which makes protecting virtual machine filesystem very important for the whole system security. Agentless periodic filesystem monitors are optimal solutions to protect cloud virtual machines because of the secure and lowoverhead features. However, most of the periodic monitors usually scan all of the virtual machine filesystem or protected files in every scanning poll, so lots of secure files are scanned again and again even though they are not corrupted. In this paper, we propose a novel agentless periodic filesystem monitor framework for virtual machines with different image formats to improve the performance of agentless periodic monitors. Our core idea is to minimize the scope of the scanning files in both file integrity checking and virus detection. In our monitor, if a file is considered secure, it will not be scanned when it has not been modified. Since our monitor only scans the newly created and modified files, it can check fewer files than other filesystem monitors. To that end, we propose two monitor methods for different types of virtual machine disks to reduce the number of scanning files. For virtual machine with single disk image, we hook the backend driver to capture the disk modification information. For virtual machine with multiple copyonwrite images, we leverage the copyonwrite feature of QCOW2 images to achieve the disk modification analysis. In addition, our system can restore and remove the corrupted files. The experimental results show that our system is effective for both Windows and Linux virtual machines with different image formats and can reduce the number of scanning files and scanning time.

A largescale concurrent data anonymous batch verification scheme for mobile healthcare crowd sensing© 2014 IEEE. Recently, with the rapid development of big data, Internet of Things (IoT) brings more and more intelligent and convenient services to people's daily lives. Mobile healthcare crowd sensing (MHCS), as a typical application of IoT, is becoming an effective approach to provide various medical and healthcare services to individual or organizations. However, MHCS still have to face to different security challenges in practice. For example, how to quickly and effectively authenticate masses of bioinformation uploaded by IoT terminals without revealing the owners' sensitive information. Therefore, we propose a largescale concurrent data anonymous batch verification scheme for MHCS based on an improved certificateless aggregate signature. The proposed scheme can authenticate all sensing bioinformation at once in a privacy preserving way. The individual data generated by different users can be verified in batch, while the actual identity of participants is hidden. Moreover, assuming the intractability of computational DiffieHellman problem, our scheme is proved to be secure. Finally, the performance evaluation shows that the proposed scheme is suitable for MHCS, due to its high efficiency.

A MaximumCaliber Approach to Predicting Perturbed Folding Kinetics Due to Mutations© 2016 American Chemical Society. We present a maximumcaliber method for inferring transition rates of a Markov state model (MSM) with perturbed equilibrium populations given estimates of state populations and rates for an unperturbed MSM. It is similar in spirit to previous approaches, but given the inclusion of prior information, it is more robust and simple to implement. We examine its performance in simple biased diffusion models of kinetics and then apply the method to predicting changes in folding rates for several highly nontrivial protein folding systems for which nonnative interactions play a significant role, including (1) tryptophan variants of the GB1 hairpin, (2) saltbridge mutations of the Fs peptide helix, and (3) MSMs built from ultralong folding trajectories of FiP35 and GTT variants of the WW domain. In all cases, the method correctly predicts changes in folding rates, suggesting the wide applicability of maximumcaliber approaches to efficiently predict how mutations perturb protein conformational dynamics.

A step in the direction of resolving the paradox of PerdewZunger selfinteraction correction. II. Gauge consistency of the energy density at three levels of approximationThe PerdewZunger (PZ) selfinteraction correction (SIC) was designed to correct the oneelectron limit of any approximate density functional for the exchangecorrelation (xc) energy, while yielding no correction to the exact functional. Unfortunately, it spoils the slowly varying (in space) limits of the uncorrected approximate functionals, where those functionals are right by construction. The right limits can be restored by locally scaling down the energy density of the PZ SIC in manyelectron regions, but then a spurious correction to the exact functional would be found unless the selfHartree and exact selfxc terms of the PZ SIC energy density were expressed in the same gauge. Only the local density approximation satisfies the samegauge condition for the energy density, which explains why the recent localscaling SIC is found here to work excellently for atoms and molecules only with this basic approximation and not with the more advanced generalized gradient approximations (GGAs) and metaGGAs, which lose the Hartree gauge via simplifying integrations by parts. The transformation of energy density that achieves the Hartree gauge for the exact xc functional can also be applied to approximate functionals. Doing so leads to a simple scaleddown selfinteraction correction that is typically much more accurate than PZ SIC in tests for many molecular properties (including equilibrium bond lengths). The present work unambiguously shows that the largest errors of PZ SIC applied to standard functionals at three levels of approximation can be removed by restoring their correct slowly varying density limits. It also confirms the relevance of these limits to atoms and molecules.

A Survey of Hyperbolic Knot Theory© Springer Nature Switzerland AG 2019. We survey some tools and techniques for determining geometric properties of a link complement from a link diagram. In particular, we survey the tools used to estimate geometric invariants in terms of basic diagrammatic link invariants. We focus on determining when a link is hyperbolic, estimating its volume, and bounding its cusp shape and cusp area. We give sample applications and state some open questions and conjectures.

Accurate and Numerically Efficient r<sup>2</sup>SCAN MetaGeneralized Gradient ApproximationCopyright © 2020 American Chemical Society. The recently proposed rSCAN functional [ J. Chem. Phys. 2019 150, 161101 ] is a regularized form of the SCAN functional [ Phys. Rev. Lett. 2015 115, 036402 ] that improves SCAN's numerical performance at the expense of breaking constraints known from the exact exchangecorrelation functional. We construct a new metageneralized gradient approximation by restoring exact constraint adherence to rSCAN. The resulting functional maintains rSCAN's numerical performance while restoring the transferable accuracy of SCAN.

Achieving differential privacy against nonintrusive load monitoring in smart grid: A fog computing approach© 2018 John Wiley & Sons, Ltd. Fog computing, a nontrivial extension of cloud computing to the edge of the network, has great advantage in providing services with a lower latency. In smart grid, the application of fog computing can greatly facilitate the collection of consumer's finegrained energy consumption data, which can then be used to draw the load curve and develop a plan or model for power generation. However, such data may also reveal customer's daily activities. Nonintrusive load monitoring (NILM) can monitor an electrical circuit that powers a number of appliances switching on and off independently. If an adversary analyzes the meter readings together with the data measured by an NILM device, the customer's privacy will be disclosed. In this paper, we propose an effective privacypreserving scheme for electric load monitoring, which can guarantee differential privacy of data disclosure in smart grid. In the proposed scheme, an energy consumption behavior model based on Factorial Hidden Markov Model (FHMM) is established. In addition, noise is added to the behavior parameter, which is different from the traditional methods that usually add noise to the energy consumption data. The analysis shows that the proposed scheme can get a better tradeoff between utility and privacy compared with other popular methods.

Adaptive Markov state model estimation using short reseeding trajectories© 2020 Author(s). In the last decade, advances in molecular dynamics (MD) and Markov State Model (MSM) methodologies have made possible accurate and efficient estimation of kinetic rates and reactive pathways for complex biomolecular dynamics occurring on slow time scales. A promising approach to enhanced sampling of MSMs is to use "adaptive" methods, in which new MD trajectories are "seeded" preferentially from previously identified states. Here, we investigate the performance of various MSM estimators applied to reseeding trajectory data, for both a simple 1D free energy landscape and miniprotein folding MSMs of WW domain and NTL9(139). Our results reveal the practical challenges of reseeding simulations and suggest a simple way to reweight seeding trajectory data to better estimate both thermodynamic and kinetic quantities.

An efficient privacypreserving algorithm based on randomized response in IoTbased smart grid© 2018 IEEE. In this paper, we propose a new randomized response algorithm that can achieve differentialprivacy and utility guarantees for consumer's behaviors, and process a batch of data at each time. Firstly, differing from traditional differential private approaches, we add randomized response noise into the behavior signatures matrix to achieve an acceptable utilityprivacy tradeoff. Secondly, a behavior signature modeling method based on sparse coding is proposed. After some lightweight trainings using the energy consumption data, the dictionary will be associated with the behavior characteristics of the electric appliances. At last, through the experimental results verification, we find that our Algorithm can preserve consumer's privacy without comprising utility.

Assured Data Deletion with FineGrained Access Control for FogBased Industrial Applications© 20052012 IEEE. The advances of cloud computing, fog computing, and Internet of things (IoT) make industries more prosperous than ever. A wide range of industrial systems such as transportation and manufacturing systems have been developed by integrating cloud computing, fog computing, and IoT infrastructure successfully. However, in this sophisticated system, security and privacy issues are major concerns that hinder the widespread adoptions of these novel techniques. In this paper, we focus on assured data deletion, an issue that is important but received less attention in academia and industry. We first propose a framework to integrate the cloud, the fog, and the things together to manage stored data from industries or individuals. We then focus on secure data deletion in this framework by proposing an assured data deletion scheme that fulfills verifiable data deletion as well as flexible access control over sensitive data. Only data owners and fog devices are involved when deleting cloud data and validating the deletion of these data, which makes the protocol practical due to the features of low latency as well as realTime interaction with fog. The proposed protocol takes advantage of the attributebased encryption, whose security can be proved under the standard model. The theoretical analysis shows good performance and functionality requirements while the implementation results demonstrate the feasibility of our proposal.