• 3-coloring in time script O sign(1.3289<sup>n</sup>)

      Beigel, R; Eppstein, D (2005-02-01)
      We consider worst case time bounds for several NP-complete 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 b-tuples of variable values; a problem is solved by assigning values to all variables satisfying all constraints, or by showing that no such assignment exist. 3-SAT is equivalent to (2,3)-CSP while 3-coloring 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 n-variable (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 3-coloring of n-vertex graphs can be solved in time O(1.3289n); that 3-list-coloring of n-vertex graphs can be solved in time O(1.3645n); that 3-edge-coloring of n-vertex graphs can be solved in time O(2n/2), and that 3-satisfiability of a formula with t 3-clauses can be solved in time O(nO(1)+1.3645t). © 2004 Elsevier Inc. All rights reserved.
    • A cantor set with hyperbolic complement

      Souto, J; Stover, M (2013-04-22)
      We 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

      Chidyagwai, P; Frank, M; Schneider, F; Seibold, B (2018-11-01)
      © 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 free-streaming 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 one-dimensional 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 identity

      Kaplan, Avi; Garner, Joanna K.; 0000-0002-2898-0085 (2017)
      Current prominent models of identity face challenges in bridging across divergent perspectives and apparent dichotomies such as personal or social-collective, conscious or unconscious, and epigenetic or discursive-relational, 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, self-perceptions and self-definitions, 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 of-analysis, across different developmental stages and contexts, and using quantitative and qualitative methodologies.
    • A Computation Offloading Incentive Mechanism with Delay and Cost Constraints under 5G Satellite-Ground IoV Architecture

      Liwang, M; Dai, S; Gao, Z; Du, X; Guizani, M; Dai, H; Du, Xiaojiang|0000-0003-4235-9671 (2019-08-01)
      © 2002-2012 IEEE. The 5G Internet of Vehicles has become a new paradigm alongside the growing popularity and variety of computation-intensive 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 cloud-enabled 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 satellite-ground framework, where a vehicular user can either be a service requestor allowed to offload workload to nearby vehicles via vehicle-to-vehicle channels while effectively controlling the cost, or a service provider who provides computing services while protecting profits. As the optimization problem is non-convex and NP-hard, simulated annealing based on the Markov Chain Monte Carlo as well as the metropolis algorithm is applied which can efficaciously obtain both high-quality and cost-effective 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 packing

      Beigel, R; Fu, B (2012-05-23)
      The 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 NP-hard for every b ∈ (0,1]. This implies a dense sublinear time hierarchy of approximation schemes for a class of NP-hard 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 NP-hard 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 Springer-Verlag.
    • A direct computation of the cohomology of the braces operad

      Dolgushev, V; Willwacher, T (2017-03-01)
      © 2017 by De Gruyter. We give a self-contained and purely combinatorial proof of the well-known fact that the cohomology of the braces operad is the operad Ger governing Gerstenhaber algebras.
    • A formality theorem for Hochschild chains

      Dolgushev, V (2006-02-15)
      We 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 quasi-isomorphism 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 gradient-augmented level set method with an optimally local, coherent advection scheme

      Nave, JC; Rosales, RR; Seibold, B (2010-04-20)
      The 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 phase-space-density gas of polar molecules

      Ni, KK; Ospelkaus, S; De Miranda, MHG; Pe'er, A; Neyenhuis, B; Zirbel, JJ; Kotochigova, S; Julienne, PS; Jin, DS; Ye, J (2008-10-10)
      A quantum gas of ultracold polar molecules, with long-range and anisotropic interactions, not only would enable explorations of a large class of many-body physics phenomena but also could be used for quantum information processing. We report on the creation of an ultracold dense gas of potassium-rubidium ( 40K87Rb) polar molecules. Using a single step of STIRAP (stimulated Raman adiabatic passage) with two-frequency 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 expansion-determined 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 × 10-30 coulomb-meters) for the triplet rovibrational ground state and 0.566(17) Debye for the singlet rovibrational ground state.
    • A high-performance virtual machine filesystem monitor in cloud-assisted cognitive IoT

      Zhan, D; Ye, L; Zhang, H; Fang, B; Li, H; Liu, Y; Du, X; Guizani, M; Du, Xiaojiang|0000-0003-4235-9671 (2018-11-01)
      © 2018 Elsevier B.V. Cloud-assisted 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 low-overhead 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 copy-on-write images, we leverage the copy-on-write 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 large-scale concurrent data anonymous batch verification scheme for mobile healthcare crowd sensing

      Liu, J; Cao, H; Li, Q; Cai, F; Du, X; Guizani, M; Du, Xiaojiang|0000-0003-4235-9671 (2019-04-01)
      © 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 bio-information uploaded by IoT terminals without revealing the owners' sensitive information. Therefore, we propose a large-scale concurrent data anonymous batch verification scheme for MHCS based on an improved certificateless aggregate signature. The proposed scheme can authenticate all sensing bio-information 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 Diffie-Hellman 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 Maximum-Caliber Approach to Predicting Perturbed Folding Kinetics Due to Mutations

      Wan, H; Zhou, G; Voelz, VA; Voelz, Vincent|0000-0002-1054-2124 (2016-12-13)
      © 2016 American Chemical Society. We present a maximum-caliber 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 non-native interactions play a significant role, including (1) tryptophan variants of the GB1 hairpin, (2) salt-bridge 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 maximum-caliber approaches to efficiently predict how mutations perturb protein conformational dynamics.
    • A step in the direction of resolving the paradox of Perdew-Zunger self-interaction correction. II. Gauge consistency of the energy density at three levels of approximation

      Bhattarai, P; Wagle, K; Shahi, C; Yamamoto, Y; Romero, S; Santra, B; Zope, RR; Peralta, JE; Jackson, KA; Perdew, JP; Santra, Biswajit|0000-0003-3609-2106; Perdew, John P|0000-0003-4237-824X (2020-06-07)
      The Perdew-Zunger (PZ) self-interaction correction (SIC) was designed to correct the one-electron limit of any approximate density functional for the exchange-correlation (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 many-electron regions, but then a spurious correction to the exact functional would be found unless the self-Hartree and exact self-xc terms of the PZ SIC energy density were expressed in the same gauge. Only the local density approximation satisfies the same-gauge condition for the energy density, which explains why the recent local-scaling 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 meta-GGAs, 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 scaled-down self-interaction 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

      Futer, D; Kalfagianni, E; Purcell, JS (2019-01-01)
      © 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 Meta-Generalized Gradient Approximation

      Furness, JW; Kaplan, AD; Ning, J; Perdew, JP; Sun, J; Perdew, John P|0000-0003-4237-824X (2020-10-01)
      Copyright © 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 exchange-correlation functional. We construct a new meta-generalized 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 non-intrusive load monitoring in smart grid: A fog computing approach

      Cao, H; Liu, S; Wu, L; Guan, Z; Du, X; Du, Xiaojiang|0000-0003-4235-9671 (2019-11-25)
      © 2018 John Wiley & Sons, Ltd. Fog computing, a non-trivial 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 fine-grained 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. Non-intrusive 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 privacy-preserving 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 trade-off between utility and privacy compared with other popular methods.
    • Adaptive Markov state model estimation using short reseeding trajectories

      Wan, H; Voelz, VA; Voelz, Vincent|0000-0002-1054-2124 (2020-01-14)
      © 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 mini-protein folding MSMs of WW domain and NTL9(1-39). 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 privacy-preserving algorithm based on randomized response in IoT-based smart grid

      Cao, H; Liu, S; Guan, Z; Wu, L; Deng, H; Du, X; Du, Xiaojiang|0000-0003-4235-9671 (2018-12-04)
      © 2018 IEEE. In this paper, we propose a new randomized response algorithm that can achieve differential-privacy and utility guarantees for consumer's behaviors, and process a batch of data at each time. Firstly, differing from traditional differential private approach-es, we add randomized response noise into the behavior signa-tures matrix to achieve an acceptable utility-privacy tradeoff. Secondly, a behavior signature modeling method based on sparse coding is proposed. After some lightweight trainings us-ing the energy consumption data, the dictionary will be associat-ed 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 Fine-Grained Access Control for Fog-Based Industrial Applications

      Yu, Y; Xue, L; Li, Y; Du, X; Guizani, M; Yang, B; Du, Xiaojiang|0000-0003-4235-9671 (2018-10-01)
      © 2005-2012 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 real-Time interaction with fog. The proposed protocol takes advantage of the attribute-based 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.